Two pointers and sliding window technique explained

What problem these techniques solve

Many array and string problems ask about pairs or contiguous ranges: two numbers that add up to a target, the longest substring without repeated characters, the shortest subarray with a sum of at least k. Checking every pair or every range costs O(n²) or more. Two pointers avoid this by using a property of the data, such as sorted order or the fact that a window only needs small updates, to rule out many candidates at once.

Opposite-end pointers: pair sum in a sorted array

Find two numbers in the sorted list [1, 3, 4, 6, 8, 11] whose sum is 10. Start with the smallest and largest. If the sum is too small, the only way to increase it is to move left right; if it is too large, move right left.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

Each step moves one pointer inward, so there are at most n − 1 steps: O(n) time and O(1) space. The same shape checks whether a string is a palindrome, reverses an array in place, and, inside an outer loop, solves 3Sum in O(n²) instead of O(n³).

Fast and slow pointers: in-place filtering

A slow pointer marks where the next kept element should go; a fast pointer scans every element. This removes duplicates from a sorted list without extra memory.

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

On linked lists, the fast pointer moves two nodes per step and the slow pointer one. If they ever meet, the list has a cycle (Floyd's cycle detection); when the fast pointer reaches the end, the slow one is at the middle.

Sliding window: longest substring without repeats

A sliding window keeps the range s[left:right + 1] valid. Move right forward one character at a time. When the new character breaks the rule, move left forward until the window is valid again. Record the best window as you go.

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

Windows come in two kinds. A fixed-size window of k elements adds the element entering on the right and removes the one leaving on the left, for example to compute a moving average. A variable-size window grows and shrinks to satisfy a condition, as above.

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

Time and space complexity

The reason a sliding window is O(n) even with a nested while loop: left and right each move forward at most n times in total, so the total work is at most 2n steps.

Common mistakes

• Using opposite-end pointers on unsorted data. The decision to move left or right is only correct because the array is sorted.
• Using a sum-based sliding window when numbers can be negative. Shrinking the window no longer always decreases the sum; use prefix sums with a hash map instead.
• Off-by-one window length: the window left..right inclusive has right - left + 1 elements.
• Forgetting to stop at left < right, which lets a single element pair with itself.
• Moving left backward. In the substring example, the check last_seen[ch] >= left prevents jumping back to an old position.

When to use them, and typical interview questions

Reach for two pointers when the input is sorted (or can be sorted cheaply) and you are looking for pairs, or when you need to modify an array in place. Reach for a sliding window when the question says contiguous subarray or substring and asks for a longest, shortest, maximum or count with a condition that changes predictably as the window grows. If the data is unsorted and you need a pair, a hash set is usually simpler and also O(n).

• Two Sum II (sorted input), 3Sum, Container With Most Water, Trapping Rain Water.
• Valid Palindrome, Reverse String, Move Zeroes, Remove Duplicates from Sorted Array.
• Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum (with a deque).
• Linked List Cycle, Middle of the Linked List.

Outside interviews, the same ideas appear in merging sorted files, network protocols that track a window of unacknowledged packets (TCP sliding window), rate limiters that count events in the last N seconds, and moving averages in time series.