Advanced Two Pointers & Sliding Window Patterns

Phase 2 is all about depth. Same patterns as Phase 1, but pushed to the harder versions. Starting with the two I use most: two pointers and the sliding window.

🪟 The variable-size window

Fixed windows are the easy case. The one that actually takes practice is the variable window: grow the right edge greedily, and shrink from the left the moment the window breaks a constraint.

def longest_valid_window(s):
    left = 0
    best = 0
    state = {}                       # whatever bookkeeping the window needs
    for right, ch in enumerate(s):
        state[ch] = state.get(ch, 0) + 1
        while is_invalid(state):     # shrink until it's valid again
            state[s[left]] -= 1
            if state[s[left]] == 0:
                del state[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

The reason this is O(n) despite the nested while: every element enters the window once (via right) and leaves at most once (via left). The window only shrinks when it has to, which is what keeps the total work linear instead of quadratic.

🔢 The “at most K” to “exactly K” trick

Counting subarrays with exactly K of something is annoying to do directly. But there’s a clean identity:

exactly(K) = atMost(K) - atMost(K - 1)

atMost(K) is a nice tidy sliding-window count, so you just run it twice. This is how Subarrays with K Different Integers and Binary Subarrays With Sum become manageable.

def subarrays_with_k_distinct(nums, k):
    def at_most(k):
        count = {}
        left = res = 0
        for right, n in enumerate(nums):
            count[n] = count.get(n, 0) + 1
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            res += right - left + 1          # windows ending at right
        return res
    return at_most(k) - at_most(k - 1)

🎯 More than two pointers

Two pointers isn’t always a left/right pair. Dutch National Flag uses three pointers to sort 0/1/2 in one pass, and 3Sum fixes one index and squeezes the other two:

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                          # skip a duplicate anchor
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0: lo += 1
            elif s > 0: hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1; hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
    return res

The duplicate-skipping is the part I always forget, and it’s the part that makes 3Sum actually correct.

⚠️ Things that bit me

Shrinking with if when I needed while. Sometimes you have to shrink several times in a row.
Duplicate results in 3Sum, from not skipping equal values at every pointer.
The window size formula. A window [left, right] holds right - left + 1 elements, and I’ve gotten that off by one more than once.

🏋️ Problems I did this week

Longest Substring Without Repeating Characters, Medium
Minimum Window Substring, Hard
3Sum, Medium
Subarrays with K Different Integers, Hard
Sort Colors, Medium

📝 What I want to remember