Implementing the Patterns

This chapter implements the three most common interview patterns in Python: two pointers, hash maps and sliding windows. The sliding window gets a line-by-line walkthrough and is then ported to C++, Java and TypeScript.

Two pointers: removing duplicates from a sorted array

Both pointers move in the same direction: read visits every element and write marks where the next kept value goes. Everything happens in place, so extra space is O(1).

def dedupe_sorted(nums: list[int]) -> int:
    """Dedupe sorted nums in place; return the new length."""
    write = 0
    for read in range(len(nums)):
        if read == 0 or nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write


data = [1, 1, 2, 3, 3, 3, 5]
count = dedupe_sorted(data)
print(count, data[:count])  # 4 [1, 2, 3, 5]

Hash map: indices of two values that sum to a target

In an unsorted array, find the indices of two elements that add up to the target. For the current value x the partner is target - x, so storing the index of every value seen so far lets one pass find the answer. Sorting would lose the original indices, so a hash map fits better than two pointers here.

def pair_indices(nums: list[int], target: int) -> tuple[int, int] | None:
    index_of: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in index_of:
            return index_of[need], i
        index_of[x] = i  # insert after the check so x never pairs with itself
    return None


print(pair_indices([8, 3, 5, 11, 2], 13))  # (0, 2)
print(pair_indices([1, 2], 10))            # None

Sliding window: the longest stretch without repeats

Find the length of the longest substring with no repeated character. Grow right one step at a time while keeping the invariant that the window [left, right] has no repeats.

def longest_unique_window(s: str) -> int:
    last_seen: dict[str, int] = {}   # character -> last index where it appeared
    left = best = 0
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:
            left = last_seen[ch] + 1  # jump past the repeat inside the window
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


for text in ["tastedev", "aaaa", "interview", ""]:
    print(repr(text), longest_unique_window(text))
# 'tastedev' 5 / 'aaaa' 1 / 'interview' 6 / '' 0

Line by line:

• last_seen stores the last index of each character, so the left edge can jump in one step instead of deleting characters one by one.
• last_seen.get(ch, -1) >= left means "this character is already inside the window". Positions left of the window must be ignored, hence the comparison with left.
• On a repeat, left moves just past the earlier occurrence. It only moves forward, so at most n times in total.
• Finally, the window length right - left + 1 updates the best answer.

Time is O(n) and space is O(min(n, σ)), where σ is the number of distinct characters. A classic bug is dropping the comparison with left, which lets the left edge move backwards on "abba"; the correct answer there is 2.

C++

An std::unordered_map holds the positions; cast the size_t length explicitly.

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

int longestUniqueWindow(const std::string& s) {
    std::unordered_map<char, int> lastSeen;
    int left = 0, best = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        auto it = lastSeen.find(s[right]);
        if (it != lastSeen.end() && it->second >= left) {
            left = it->second + 1;
        }
        lastSeen[s[right]] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::cout << longestUniqueWindow("tastedev") << '\n';  // 5
    std::cout << longestUniqueWindow("abba") << '\n';      // 2
}

Java

HashMap.get can return null, so read it into an Integer and check.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueWindow {
    static int longestUniqueWindow(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            Integer prev = lastSeen.get(ch);
            if (prev != null && prev >= left) {
                left = prev + 1;
            }
            lastSeen.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestUniqueWindow("tastedev")); // 5
        System.out.println(longestUniqueWindow("abba"));     // 2
    }
}

TypeScript

Array.from(s) keeps two-code-unit characters such as emoji whole.

function longestUniqueWindow(s: string): number {
  const lastSeen = new Map<string, number>();
  const chars = Array.from(s);
  let left = 0;
  let best = 0;
  for (let right = 0; right < chars.length; right++) {
    const prev = lastSeen.get(chars[right]);
    if (prev !== undefined && prev >= left) left = prev + 1;
    lastSeen.set(chars[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(longestUniqueWindow("tastedev")); // 5
console.log(longestUniqueWindow("abba")); // 2

C++ char and Java charAt work on bytes and UTF-16 code units; mention this for non-ASCII input. For lowercase or ASCII input, an array of size 26 or 128 can replace the map.

Summary

Two pointers suit sorted data and in-place cleanup, hash maps answer "have I seen this value?", and sliding windows find the best contiguous range. In each, decide which invariant the loop keeps and make sure the pointers only move forward. Across languages only the hash map API and the notion of a character change.