This problem is the cleanest introductory template for the Monotonic Decreasing Stack pattern. Let’s look at why storing indices unlocks the distance calculation.

1. The Mental Model

Imagine people waiting in line holding temperature tickets. If temperatures are dropping: [73, 71, 69], nobody has found a warmer day yet! So everyone has to stay waiting in line.

Now, a warm day arrives: 72!

• The person holding 69 sees 72 > 69. Their wait is over! They step out of line.
• The person holding 71 sees 72 > 71. Their wait is over! They step out of line.
• The person holding 73 sees 72 < 73. 72 is not warm enough for them! The person with 73 stays waiting in line, and the day with 72 joins the line behind them.

2. Why Store Indices Instead of Values?

If you only push temperature numbers (e.g. 69) onto the stack, when a warmer day 72 pops 69, you know that a warmer day happened, but you don’t know how many days elapsed!

By pushing the array index prev_day onto the stack:

days_waited = current_day - prev_day
answer[prev_day] = days_waited

You calculate the exact time difference in $O(1)$ and write directly to the output array!

Clean Python 3.12 Implementation

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """Finds wait time until warmer day in O(N) time and O(N) auxiliary space."""
    n = len(temperatures)
    ans = [0] * n
    stack: list[int] = [] # Stores indices of previous cooler days

    for curr_day, temp in enumerate(temperatures):
        # Pop all previous days that are strictly cooler than today
        while stack and temperatures[stack[-1]] < temp:
            prev_day = stack.pop()
            ans[prev_day] = curr_day - prev_day

        stack.append(curr_day)

    return ans

Complexity Breakdown

• Time Complexity: O(N). Every index is pushed onto the stack once and popped at most once. Total operations: $le 2N$.
• Space Complexity: O(N) for the stack in the worst-case of strictly decreasing temperatures (e.g. [100, 90, 80, 70]).

Minimum Window Substring is the crown jewel of sliding window problems. The difference between a junior solution and a staff engineer solution comes down to how window validation is tracked.

1. The Trap: Comparing Two Hash Maps

In naive implementations, developers maintain two hash maps: target_counts and window_counts. Whenever the window slides, they loop through the keys of target_counts to see if the window is valid. That turns an $O(N)$ algorithm into $O(N cdot |Sigma|)$ with heavy hash table overhead!

2. The Staff Engineer Pattern: Single Vector + Deficit Counter

We can optimize this down to bare metal with two simple tricks:

1. Fixed 128-integer Array: Standard ASCII fits inside 128 indices. An array of 128 integers takes 512 bytes, fitting completely inside an L1 data cache line.
2. A Single Deficit Counter (required): We set required = len(t). When expanding the window with pointer r, if counts[s[r]] > 0, that character was actively needed, so we decrement required--. When required == 0, the window is 100% valid! We don’t have to check any other variables!

Clean Python 3.12 Implementation

def min_window(s: str, t: str) -> str:
    """Finds minimum window substring in strict O(|s| + |t|) time and O(1) space."""
    if not s or not t or len(s) < len(t):
        return ""

    # Frequency map using fixed 128 ASCII array
    freq = [0] * 128
    for char in t:
        freq[ord(char)] += 1

    required = len(t)
    min_len = float('inf')
    start_idx = 0
    left = 0

    for right in range(len(s)):
        r_char = ord(s[right])
        
        # If this character was still needed by t
        if freq[r_char] > 0:
            required -= 1
            
        freq[r_char] -= 1

        # While window satisfies all characters in t -> contract left boundary
        while required == 0:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start_idx = left

            l_char = ord(s[left])
            freq[l_char] += 1
            
            # If removing this character breaks the required quota
            if freq[l_char] > 0:
                required += 1
                
            left += 1

    return "" if min_len == float('inf') else s[start_idx : start_idx + min_len]

Complexity Breakdown

• Time Complexity: O(|s| + |t|). The right pointer advances |s| times. The left pointer advances at most |s| times. Total pointer advances = 2|s|.
• Space Complexity: O(1) auxiliary space. Exactly 128 integers on the stack.

The Fenwick Tree (invented by Peter Fenwick in 1994) is one of the most compact data structures ever devised. It gives you the full power of a dynamic segment tree in just one flat array of size N with 10 lines of code.

1. The Secret: Powers of 2 Range Decomposition

Any positive integer can be uniquely represented as a sum of powers of 2. For example: 13 = 8 + 4 + 1.

Fenwick took this idea and applied it to prefix ranges: instead of storing every single element, tree[i] stores the sum of a contiguous range of length equal to its lowest set bit!

The length of the range responsible by index i is given by: lowbit(i) = i & (-i).

• If i = 12 (1100_2): lowbit(12) = 4. So tree[12] stores the sum of 4 elements: indices [9, 10, 11, 12]!
• If i = 8 (1000_2): lowbit(8) = 8. So tree[8] stores the sum of the first 8 elements: [1 ... 8]!

2. The Two Operations

A. Prefix Sum Query: `i -= (i & -i)`

To calculate the prefix sum up to index 13:

1. Read tree[13] (covers index 13). 13 - lowbit(13) = 13 - 1 = 12.
2. Read tree[12] (covers indices 9 through 12). 12 - lowbit(12) = 12 - 4 = 8.
3. Read tree[8] (covers indices 1 through 8). 8 - lowbit(8) = 8 - 8 = 0 (Done!).

Total reads: only 3 steps to sum 13 numbers! At each step, you strip off one binary bit, taking at most O(log N) operations.

B. Point Update: `i += (i & -i)`

When you add delta to element i, which parent ranges need to be updated? Every index whose range covers i! You navigate up the tree simply by adding the lowest set bit: i += (i & -i)!

Clean C++20 Implementation

#include <vector>
#include <cstdint>

class FenwickTree {
    std::vector<int64_t> tree;
    int n;

    static inline int lowbit(int x) {
        return x & (-x);
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // Adds delta to index i (1-indexed) in O(log N)
    void update(int i, int64_t delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    // Computes sum of prefix [1 ... i] in O(log N)
    int64_t query(int i) const {
        int64_t sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    // Computes range sum [l ... r] in O(log N)
    int64_t queryRange(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

Why Fenwick Beats Segment Trees in Production

The Dutch National Flag algorithm (invented by Edsger W. Dijkstra) is the secret weapon that makes 3-way QuickSort resilient against duplicate keys.

1. The 3 Pointer Invariant

We divide the array into 4 distinct regions using 3 pointers: low, mid, and high:

[ 0 ... low-1 ]  -> All elements strictly 0
[ low ... mid-1 ] -> All elements strictly 1
[ mid ... high ]  -> UNKNOWN (yet to be inspected)
[ high+1 ... n-1] -> All elements strictly 2

Initially, low = 0, mid = 0, and high = n - 1. The entire array is initially inside the UNKNOWN region.

2. The 3 State Transitions

While mid <= high, inspect nums[mid]:

1. If nums[mid] == 0: Swap nums[low] with nums[mid]. Increment BOTH low++ and mid++.
   Why can we increment mid here? Because whatever was sitting at low was already processed (it was guaranteed to be a 1).
2. If nums[mid] == 1: It’s already in the right spot! Just increment mid++.
3. If nums[mid] == 2: Swap nums[mid] with nums[high]. Decrement high--.
   THE CRITICAL CATCH: Do NOT increment mid here! Whatever came from high was unknown—it might be a 0, a 1, or another 2! We must inspect it on the next loop iteration!

Clean Python 3.12 Implementation

def sort_colors(nums: list[int]) -> None:
    """In-place 3-way partition in O(N) time and O(1) memory."""
    low = 0
    mid = 0
    high = len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else: # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Note: mid is intentionally NOT incremented here!

Complexity Breakdown

• Time Complexity: O(N). In every single step, either mid increases or high decreases. The unknown window (high - mid) strictly shrinks to zero in at most N steps.
• Space Complexity: O(1). No extra memory allocated.

The Maximum XOR problem is the ultimate showcase of how bit manipulation and trees blend together. Once you see the greedy nature of binary numbers, the Binary Trie solution becomes second nature.

1. The Greedy Bit Principle

In binary numbers, the Most Significant Bit (MSB) has more numerical value than all lower bits combined! For example, bit 30 ($2^{30} pprox 1.07 imes 10^9$) is strictly greater than the sum of all bits from 0 to 29 combined ($2^{30} – 1$).

Therefore, to maximize an XOR sum, you must be greedy from left to right (MSB down to LSB):

• If the current bit of number num is 1, you desperately want to pair it with a number whose corresponding bit is 0 (because 1 ^ 0 = 1).
• If the current bit of num is 0, you want to pair it with a number whose corresponding bit is 1 (because 0 ^ 1 = 1).

2. Why a Binary Trie?

A Binary Trie is just a tree where every node has at most two children: 0 (left) and 1 (right).

1. Insert: You insert each number into the Trie as a 31-bit or 32-bit string of binary digits, from bit 31 down to bit 0.
2. Query: For each number x, you walk down the Trie. At each bit b, you ask: ‘Does the opposite branch (1 - b) exist?’
   • If YES: Take that branch! That bit in your XOR result becomes 1.
   • If NO: You’re forced to take the same branch (b), so that bit in your XOR result becomes 0.

Because you made the best possible choice at every single bit position starting from the highest power of 2, the final accumulated number is mathematically guaranteed to be the global maximum XOR!

Clean Python 3.12 Implementation

class TrieNode:
    __slots__ = ('children',)
    def __init__(self):
        self.children: list[TrieNode | None] = [None, None]

class Solution:
    def find_maximum_xor(self, nums: list[int]) -> int:
        root = TrieNode()

        # Step 1: Insert all numbers into the 31-bit binary trie
        for num in nums:
            curr = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if not curr.children[bit]:
                    curr.children[bit] = TrieNode()
                curr = curr.children[bit]

        # Step 2: Query each number against the trie
        max_xor = 0
        for num in nums:
            curr = root
            current_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                opposite_bit = 1 - bit
                
                # Greedily check if the complementary bit exists
                if curr.children[opposite_bit]:
                    current_xor |= (1 << i)
                    curr = curr.children[opposite_bit]
                else:
                    curr = curr.children[bit]
                    
            max_xor = max(max_xor, current_xor)

        return max_xor

Complexity Breakdown

• Time Complexity: O(31 * N) = O(N). Inserting N numbers takes 31 * N operations. Querying N numbers takes 31 * N operations. Total time is strictly linear in the number of elements.
• Space Complexity: O(31 * N) worst-case node allocations. In practice, prefix branches overlap heavily, keeping memory around a few megabytes.