Patterns

Pick the pattern from the problem

Most array and string problems use one of five patterns. Look for these hints:

Hint in the problem	Pattern	Typical time
Sorted array, find a pair or a triplet	Two pointers	O(n)
"Longest / shortest contiguous subarray or substring that..."	Sliding window	O(n)
"Have we seen it before?", counts, unsorted pairs	Hashing	O(n)
Sorted data, or "find the smallest X that works"	Binary search	O(log n) or O(n log M)
Many range sums, "subarray sum equals k"	Prefix sums	O(n)

Say the pattern out loud: "The array is sorted and we need a pair, so I'll use two pointers." This shows you are not guessing.

Two pointers

Opposite ends

Start one pointer at each end. Move the one that brings you closer to the goal.

// Sorted array: return the indices of two numbers that add up to target.
func pairWithSum(_ nums: [Int], _ target: Int) -> (Int, Int)? {
    var left = 0
    var right = nums.count - 1
    while left < right {
        let sum = nums[left] + nums[right]
        if sum == target { return (left, right) }
        if sum < target {
            left += 1     // need a bigger sum
        } else {
            right -= 1    // need a smaller sum
        }
    }
    return nil
}

print(pairWithSum([1, 3, 4, 6, 9], 10)!)   // (0, 4): 1 + 9 = 10

Why it works: the array is sorted. Moving left can only make the sum bigger. Moving right can only make it smaller. So you never skip the answer.

Same direction (read and write)

One pointer reads every element. The other marks where to write the next kept element.

// Remove duplicates from a sorted array in place. Return the new length.
func removeDuplicates(_ nums: inout [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    var write = 1
    for read in 1..<nums.count where nums[read] != nums[write - 1] {
        nums[write] = nums[read]
        write += 1
    }
    return write
}

var sortedNums = [1, 1, 2, 3, 3]
let length = removeDuplicates(&sortedNums)
print(length, sortedNums.prefix(length))   // 3 [1, 2, 3]

Arrays are values in Swift. To change the caller's array, the parameter must be inout, and the call needs &.

Sliding window

A window is a range start...end. Move end forward every step. Move start forward only when the window breaks the rule.

Variable size

// Longest subarray with sum <= limit. All numbers are >= 0.
func longestWindow(_ nums: [Int], limit: Int) -> Int {
    var start = 0
    var sum = 0
    var best = 0
    for end in nums.indices {
        sum += nums[end]                     // 1. grow: take the new element
        while sum > limit {                  // 2. shrink until the window is valid
            sum -= nums[start]
            start += 1
        }
        best = max(best, end - start + 1)    // 3. record the answer
    }
    return best
}

print(longestWindow([2, 1, 3, 1, 1, 4], limit: 5))   // 3: for example [1, 3, 1]

The same shape on a string, with a dictionary that remembers the last position of each character:

// Longest substring without repeating characters.
func lengthOfLongestSubstring(_ s: String) -> Int {
    var lastSeen: [Character: Int] = [:]
    var start = 0
    var best = 0
    for (end, c) in Array(s).enumerated() {
        if let previous = lastSeen[c], previous >= start {
            start = previous + 1             // jump past the repeated character
        }
        lastSeen[c] = end
        best = max(best, end - start + 1)
    }
    return best
}

print(lengthOfLongestSubstring("abcabcbb"))   // 3: "abc"

Each element enters and leaves the window at most once, so the total time is O(n), even with the inner while.

Fixed size

Add the new element, drop the old one:

func maxSum(_ nums: [Int], k: Int) -> Int? {
    guard k > 0, nums.count >= k else { return nil }
    var window = nums[0..<k].reduce(0, +)
    var best = window
    for i in k..<nums.count {
        window += nums[i] - nums[i - k]
        best = max(best, window)
    }
    return best
}

print(maxSum([1, 4, 2, 10, 2, 3], k: 2)!)   // 12: 2 + 10

Watch out: a sum-based window needs numbers that are not negative. With negative numbers, shrinking does not always make the sum smaller. Use prefix sums with hashing instead (below).

Hashing

Trade memory for speed. A Set or Dictionary answers "have I seen this?" in O(1) on average.

// Is there a duplicate at most k positions apart?
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
    var lastIndex: [Int: Int] = [:]
    for (i, n) in nums.enumerated() {
        if let j = lastIndex[n], i - j <= k { return true }
        lastIndex[n] = i
    }
    return false
}

print(containsNearbyDuplicate([1, 2, 3, 1], 3))   // true

Group items by a key that is the same for items that belong together:

// Group anagrams: words with the same letter counts get the same key.
func groupAnagrams(_ words: [String]) -> [[String]] {
    var groups: [[Int]: [String]] = [:]
    let a = UInt8(ascii: "a")
    for word in words {
        var key = Array(repeating: 0, count: 26)
        for byte in word.utf8 { key[Int(byte - a)] += 1 }
        groups[key, default: []].append(word)
    }
    return Array(groups.values)
}

print(groupAnagrams(["eat", "tea", "tan", "ate", "nat"]).count)   // 2 groups

Time O(n · L), where L is the word length. Sorting each word as the key also works, but costs O(n · L log L).

Binary search

Classic: find a value

func binarySearch(_ nums: [Int], _ target: Int) -> Int? {
    var low = 0
    var high = nums.count - 1
    while low <= high {
        let mid = low + (high - low) / 2
        if nums[mid] == target { return mid }
        if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

print(binarySearch([1, 3, 5, 7, 9], 7)!)   // 3

Lower bound: the first index where value >= target

This template avoids most off-by-one bugs. Learn this one well.

func lowerBound(_ nums: [Int], _ target: Int) -> Int {
    var low = 0
    var high = nums.count               // the answer is in low...high
    while low < high {
        let mid = low + (high - low) / 2
        if nums[mid] < target {
            low = mid + 1               // mid is too small: the answer is to the right
        } else {
            high = mid                  // mid could be the answer: keep it
        }
    }
    return low                          // nums.count if every value is smaller
}

print(lowerBound([1, 3, 3, 5], 3))   // 1
print(lowerBound([1, 3, 3, 5], 4))   // 3
print(lowerBound([1, 3, 3, 5], 9))   // 4

Binary search on the answer

Use it when the question is "find the smallest X that works". "Works" must be monotonic: if X works, every bigger X works too.

// Smallest eating speed so that all piles are eaten within `hours` hours.
func minEatingSpeed(_ piles: [Int], _ hours: Int) -> Int {
    func canFinish(atSpeed speed: Int) -> Bool {
        let needed = piles.reduce(0) { $0 + ($1 + speed - 1) / speed }   // rounds up
        return needed <= hours
    }
    var low = 1
    var high = piles.max() ?? 1
    while low < high {
        let mid = low + (high - low) / 2
        if canFinish(atSpeed: mid) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

print(minEatingSpeed([3, 6, 7, 11], 8))   // 4

Time: O(n log M), where M is the largest pile.

The standard library has no binary search on arrays. You will write it yourself, so practice the lower bound template until it is automatic.

Prefix sums

prefix[i] is the sum of the first i numbers. Then the sum of any range is one subtraction.

func makePrefix(_ nums: [Int]) -> [Int] {
    var prefix = [0]
    for n in nums { prefix.append(prefix.last! + n) }
    return prefix
}

let prefix = makePrefix([2, 4, 1, 3])   // [0, 2, 6, 7, 10]
// Sum of nums[l...r] = prefix[r + 1] - prefix[l]
print(prefix[3] - prefix[1])            // 5: 4 + 1

Build once in O(n). Each range sum is then O(1).

Prefix sums + hashing

"How many subarrays sum to k?" This works with negative numbers, unlike the sliding window.

func subarraySum(_ nums: [Int], _ k: Int) -> Int {
    var prefixCount: [Int: Int] = [0: 1]   // the empty prefix
    var running = 0
    var total = 0
    for n in nums {
        running += n
        total += prefixCount[running - k, default: 0]   // earlier prefixes that leave exactly k
        prefixCount[running, default: 0] += 1
    }
    return total
}

print(subarraySum([1, 1, 1], 2))    // 2
print(subarraySum([1, -1, 0], 0))   // 3

The idea: if running - earlier == k, then the numbers between them sum to k. So count how many earlier prefixes equal running - k.

Summary

Pattern	Template in one line	Watch out for
Two pointers	`while left < right`, move one side	Needs sorted data (opposite ends)
Sliding window	grow `end`, shrink `start` while invalid	Sum windows need non-negative numbers
Hashing	`dict[key, default: 0] += 1`	Extra O(n) memory
Binary search	`low < high`, `high = mid` or `low = mid + 1`	Infinite loops from `low = mid`
Prefix sums	`prefix[r + 1] - prefix[l]`	Off by one: `prefix` has `n + 1` items

#Pick the pattern from the problem

#Two pointers

#Opposite ends

#Same direction (read and write)

#Sliding window

#Variable size

#Fixed size

#Hashing

#Binary search

#Classic: find a value

#Lower bound: the first index where value >= target

#Binary search on the answer

#Prefix sums

#Prefix sums + hashing

#Summary