Lesson 3 of 6

Two pointers, sliding window and binary search

2 min read

Two pointers

On a sorted array, move pointers inward based on the comparison.

python

def pair_with_sum(sorted_nums, target):
    l, r = 0, len(sorted_nums) - 1
    while l < r:
        s = sorted_nums[l] + sorted_nums[r]
        if s == target: return [l, r]
        if s < target: l += 1      # need bigger
        else: r -= 1               # need smaller
    return []

Also: removing duplicates in place, reversing, Container With Most Water, 3Sum (sort, fix one, two-pointer the rest: O(n²)).

Sliding window

For contiguous subarrays/substrings. Expand the right edge; shrink the left while the window is invalid.

Longest substring without repeating characters:

python

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

Template for "smallest window with sum ≥ target" (positives only):

python

def min_window_len(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]; left += 1
    return 0 if best == float("inf") else best

Binary search

Halve the search space each step: O(log n). The safe template:

python

def lower_bound(nums, target):     # first index with nums[i] >= target
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target: lo = mid + 1
        else: hi = mid
    return lo

Binary search on the answer: when you can check "is X enough?" and the answer is monotonic (if X works, X+1 works). Examples: minimum ship capacity to deliver in D days, Koko eating bananas, minimum time to finish tasks.

Watch for: rotated sorted arrays (decide which half is sorted), off-by-one errors (< vs <=, mid + 1), and overflow in Java/C++ (mid = lo + (hi - lo) / 2).

Problems to practise

Valid Palindrome, 3Sum, Container With Most Water, Best Time to Buy and Sell Stock, Longest Repeating Character Replacement, Minimum Window Substring, Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas.

← Previous Next →