Data Structures & Algorithms

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]).

This is a classic trap that catches even intermediate developers. Let’s see why two pointers collapse and why prefix math is the ultimate solution.

1. Why Two Pointers Fails on Negative Numbers

A sliding window relies on a fundamental monotonic invariant:

• If the current sum is too small, expanding the right pointer will increase the sum.
• If the current sum is too large, contracting the left pointer will decrease the sum.

The moment you introduce negative numbers, this invariant is destroyed! Expanding the right pointer might add -10, making the sum smaller. Shrinking the left pointer might drop -5, making the sum larger. You can no longer make greedy left/right decisions!

2. The Prefix Sum Invariant

Let prefix[i] be the cumulative sum from index 0 to i.

The sum of any contiguous subarray from index j + 1 to i is given by: sum(j+1 ... i) = prefix[i] - prefix[j].

We want this subarray sum to equal k:

prefix[i] - prefix[j] = k
prefix[j] = prefix[i] - k

The Breakthrough: As you iterate through the array maintaining a running prefix sum curr_sum, you simply ask the hash map: ‘How many times have we already seen a prefix sum equal to curr_sum - k in the past?’

Every time you find that value in the hash map, you have found a valid subarray that sums exactly to k!

Clean Python 3.12 Implementation

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    """Counts subarrays summing to k in O(N) time and O(N) space."""
    # Base case: A prefix sum of 0 has occurred once (an empty prefix)
    prefix_counts: dict[int, int] = defaultdict(int)
    prefix_counts[0] = 1

    curr_sum = 0
    total_subarrays = 0

    for x in nums:
        curr_sum += x
        target = curr_sum - k
        
        # Add all occurrences of the complementary prefix sum
        if target in prefix_counts:
            total_subarrays += prefix_counts[target]
            
        # Record current prefix sum
        prefix_counts[curr_sum] += 1

    return total_subarrays

Why prefix_counts[0] = 1 is Critical

If you forget prefix_counts[0] = 1, any subarray that starts at index 0 and sums to k (e.g. nums = [3, ...], k = 3) will produce curr_sum = 3, and look for curr_sum - k = 0 in the map. Without the base case, it would fail to count that valid subarray!

Complexity Breakdown

• Time Complexity: O(N). Single pass through the array with O(1) hash map lookups.
• Space Complexity: O(N) to store prefix sum frequencies.

This problem is a masterpiece of digital circuit design translated into software code. Let’s design the state machine from first principles.

1. The Three States of a Bit

For any bit position, as we scan numbers in the array, how many times can we see a 1?

• Seen 0 times → Count = 0
• Seen 1 time → Count = 1
• Seen 2 times → Count = 2
• Seen 3 times → Resets back to 0!

To represent 3 distinct states (0, 1, and 2), we need 2 bits of memory! Let’s name them:

• twos (the high bit)
• ones (the low bit)

2. The Truth Table

When a new bit x arrives from the current number:

3. Deriving the Logic Gates

From the truth table:

• ones = (ones ^ x) & (~twos)
• twos = (twos ^ x) & (~ones)

When the full array has been scanned:

• Every element that appeared 3 times completed the full cycle $(0 o 1 o 2 o 0)$ and returned both bits to 0.
• The single element that appeared 1 time transitioned from $0 o 1$. Its bits are left recorded inside ones!

Clean Python 3.12 Implementation

def single_number(nums: list[int]) -> int:
    """Finds element appearing once while others appear 3 times in O(N) time and O(1) space."""
    ones = 0
    twos = 0

    for x in nums:
        # Update ones: XOR with x, but clear if twos already holds this bit
        ones = (ones ^ x) & ~twos
        # Update twos: XOR with x, but clear if ones now holds this bit
        twos = (twos ^ x) & ~ones

    return ones

Complexity Breakdown

• Time Complexity: O(N). We touch each number once with 4 single-cycle bitwise operations.
• Space Complexity: O(1). Exactly two integer variables living in registers.