Data structures and patterns · Question 39 of 50

When do you use two pointers or a sliding window?

What they're checking

Pattern recognition: the most common array and string pattern.

The answer

When a question asks about a contiguous subarray or substring (the longest, the shortest, how many have some property), a sliding window often turns O(n²) into O(n): grow the window with the right pointer, shrink it from the left while it breaks the rule, and track the best as you go.

Two pointers from both ends work on sorted arrays: a pair with a target sum, the container with the most water. Signals in the question: "contiguous", "at most k", "longest", "shortest", "sorted".

// the longest substring without repeating characters
function longest(s) {
  const last = new Map()
  let start = 0, best = 0
  for (let i = 0; i < s.length; i++) {
    if (last.get(s[i]) >= start) start = last.get(s[i]) + 1
    last.set(s[i], i)
    best = Math.max(best, i - start + 1)
  }
  return best
}

The picture

"a b c a b c b b"
 [a b c]              length 3
   [b c a]            'a' again: move the start past the old 'a'
each character enters and leaves the window once: O(n)
The follow-up they'll ask

Why does it fail for "subarray sum equals k" with negative numbers?

Show the answer

Shrinking the window no longer always lowers the sum. Use prefix sums with a hash map instead.

Your progress stays on this device.