LeetCode 75: Two Pointers, Sliding Window & Binary Search with Pattern Recognition

The Pattern-Based Approach to LeetCode

There are ~3,000 LeetCode problems. You cannot memorise them all. But there are only ~10 core patterns that power the majority of solutions. Once you internalize each pattern, you can solve novel problems you have never seen before.

Pattern 1: Two Pointers

When to use: Sorted input, find a pair/triplet that satisfies a condition. Nested loops would be O(n^2) — two pointers brings it to O(n).

Problem: Two Sum II (Sorted Input)

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    # Time: O(n), Space: O(1)
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]   # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

Problem: 3Sum

def three_sum(nums: list[int]) -> list[list[int]]:
    # Time: O(n^2), Space: O(1) excluding output
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]: left += 1
                while left < right and nums[right] == nums[right - 1]: right -= 1
                left += 1; right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]

Pattern 2: Sliding Window

Problem: Longest Substring Without Repeating Characters

def length_of_longest_substring(s: str) -> int:
    # Time: O(n), Space: O(min(m,n))
    char_index: dict[str, int] = {}
    max_length = 0
    left = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("pwwkew"))    # 3

Problem: Minimum Window Substring (Hard)

from collections import Counter

def min_window(s: str, t: str) -> str:
    # Time: O(|s| + |t|), Space: O(|t|)
    if not t or not s:
        return ""

    need = Counter(t)
    missing = len(t)
    best = ""
    left = 0

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:
            window = s[left:right + 1]
            if not best or len(window) < len(best):
                best = window
            left_char = s[left]
            need[left_char] += 1
            if need[left_char] > 0:
                missing += 1
            left += 1

    return best

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

Pattern 3: Binary Search on Answer

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    # Find minimum k bananas/hour to eat all piles within h hours. | Time: O(n log m) where m = max(piles), Space: O(1)
    def can_finish(speed: int) -> bool:
        return sum(math.ceil(p / speed) for p in piles) <= h

    left, right = 1, max(piles)

    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1

    return left

print(min_eating_speed([3, 6, 7, 11], 8))       # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5)) # 30

Pattern 4: Prefix Sum

def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    # Count subarrays with sum = k. | Key insight: if prefix[j] - prefix[i] = k, subarray i..j sums to k | Time: O(n), Space: O(n)
    count = 0
    prefix_sum = 0
    seen: dict[int, int] = {0: 1}

    for num in nums:
        prefix_sum += num
        count += seen.get(prefix_sum - k, 0)
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1

    return count

print(subarray_sum_equals_k([1, 1, 1], 2))           # 2
print(subarray_sum_equals_k([1, 2, 3, -3, 3], 3))    # 3

Time Complexity Quick Reference