Home/Data Structures & Algorithms/Two Pointers & Sliding Window
  1. Asked: September 11, 2026In: ,

    Minimum Window Substring: Why an integer frequency array beats HashMap in low-latency parsers

    Abhay Tiwari
    Abhay Tiwari Begginer

    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_counRead more

    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.
    See less
    • 0
  2. Asked: September 11, 2026In: ,

    Why does the Two-Pointer approach beat Monotonic Stack for Trapping Rainwater in production?

    Abhay Tiwari
    Abhay Tiwari Begginer

    I see this question come up all the time in engineering interviews and production optimizations. The short answer is: memory allocations and CPU cache locality. On paper, both the Monotonic Stack and Two Pointers are O(N) time. But in reality: Monotonic Stack: Pushes and pops indices into a dynamicRead more

    I see this question come up all the time in engineering interviews and production optimizations. The short answer is: memory allocations and CPU cache locality.

    On paper, both the Monotonic Stack and Two Pointers are O(N) time. But in reality:

    • Monotonic Stack: Pushes and pops indices into a dynamic stack (like std::stack in C++ or a dynamic slice in Python/Go). That means repeated memory allocations, pointer indirection, and cache misses every time the stack resizes or wanders through heap memory.
    • Two-Pointer Approach: Uses just 4 integer variables (left, right, left_max, right_max). These variables stay entirely inside CPU registers. There is zero heap allocation, zero pointer chasing, and the CPU prefetcher streams the array from both ends sequentially at full hardware bus speed.

    The Plain English Intuition

    Think about standing at the edge of a swimming pool. The amount of water that can sit on top of any single column i is strictly decided by one thing: the shorter of the two tallest walls on its left and right.

    Mathematically: water[i] = max(0, min(max_left, max_right) - height[i]).

    Here is the genius of two pointers: you place one pointer at the start (left) and one at the end (right). At every step:

    1. If height[left] <= height[right], you know for certain that whatever tall wall exists on the far right is at least as tall as height[left]. So the bottleneck for the left side is only determined by left_max. You can safely calculate water at left and move left++.
    2. If height[right] < height[left], the exact opposite holds true. The bottleneck for right is determined purely by right_max. You calculate water at right and move right--.

    You never have to look back, and you never have to store past heights in a stack!

    Production-Ready Python 3.12 Implementation

    from typing import Sequence

def trap_rain_water(height: Sequence[int]) -> int:
    """Calculates total trapped water in O(N) time and O(1) extra space."""
    if len(height) < 3:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total_water = 0

    while left < right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]  # New wall found, no water trapped here
            else:
                total_water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right] # New wall found on right
            else:
                total_water += right_max - height[right]
            right -= 1

    return total_water

    Clean C++20 Version (Zero Allocations)

    #include <vector>
#include <cstdint>

int64_t trap(const std::vector<int32_t>& height) noexcept {
    const size_t n = height.size();
    if (n < 3) return 0;

    size_t left = 0;
    size_t right = n - 1;
    int32_t left_max = 0;
    int32_t right_max = 0;
    int64_t total_water = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                total_water += (left_max - height[left]);
            }
            ++left;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                total_water += (right_max - height[right]);
            }
            --right;
        }
    }
    return total_water;
}

    Complexity & Production Pitfalls

    • Time Complexity: O(N). Every element is visited exactly once. No nested loops.
    • Space Complexity: O(1). No auxiliary memory allocated.
    • 32-bit Integer Overflow: If you have an array of 100,000 elements, each with height 100,000, the total water can reach 10^10. A standard 32-bit signed integer will overflow and return a negative number! Always use a 64-bit integer (int64_t in C++ or long in Java) for the accumulator.
    See less
    • 0