Sliding Window & Two Pointers

DSA · Intermediate

Definition

Techniques that move one or two indexes across an array to examine sub-ranges without nested loops.

They reduce many O(n²) subarray/substring problems to O(n).

Diagram

Flowchart

Example: Longest substring without repeating characters

def longest(s):
    last, left, best = {}, 0, 0
    for r, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = r
        best = max(best, r - left + 1)
    return best
print(longest('abcabcbb'))

Output: 3

Complexity

O(n)

Key points

Fixed vs variable window
Two pointers on sorted arrays
Each index moves at most n times

Interview questions

Max sum subarray of size k?

Keep a running sum; add the new element and subtract the one leaving.

Pair with target sum in sorted array?

Move left/right pointers inward based on the current sum.