DSA Notes

Techniques

Two Pointers

Two indices that only ever move forward.

The idea

Many brute-force solutions try every start l and every end r: O(n²). If moving l to the right never forces r to move back, both pointers sweep the array once and the work drops to O(n).

Two common shapes: a sliding window (both pointers move the same way) for the longest or shortest subarray under a constraint, and two ends moving inward on a sorted array for pair sums.

The technique is valid only when the condition is monotone: for example, with non-negative values, a longer window never has a smaller sum.

Sample problem

209. Minimum Size Subarray Sum ↗ Medium

Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is at least the target, or 0 if there is none.

target = 7, nums = [2,3,1,2,4,3]
output = 2   ([4,3])

Why the solution works

All numbers are positive, so a window’s sum grows when it is extended and falls when it is shrunk. That monotonicity is what two pointers need.

Move r one step at a time. Whenever the window reaches the target, record its length and shrink from the left while it still qualifies: a shorter valid window ending at r can only start further right.

l never moves back, because a start that was too far left for an earlier r is also too far left for a later one.

Complexity: O(n) time: l and r each move at most n steps. O(1) memory.

Watch out

  • Check monotonicity first. With negative numbers a sum window is not monotone and the method breaks.
  • Update the answer at the right moment: after extending, before shrinking.
  • Handle the case where a single item does not fit, so l does not overtake r incorrectly.
Watch it run

Try your own input

Practise on LeetCode