Pick the right tool
- Two pointers on sorted data — pair sum, remove duplicates, opposite ends.
- Fast/slow — cycle detection, middle of list (same idea, different structure).
- Variable window — longest/shortest subarray/substring with a constraint.
- Fixed window — always size k (max sum of k, anagrams of length k).
Analogy: conveyor + stretchy frame
Two pointers on a sorted array are two fingers walking toward a target. A sliding window is a stretchy picture frame on a conveyor belt: expand the right edge to include more, shrink the left when the constraint breaks. Each item enters and leaves the frame at most once — that’s why it’s O(n).
Two pointers — traced
Sorted array pair sum to target: start left at start, right at end. If sum too small, left++ (need bigger). If too big, right--. Each step discards an index — O(n).
def two_sum_sorted(a, target):
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
if s == target:
return i, j
if s < target:
i += 1
else:
j -= 1
return None
# a=[2,3,6,8], target=9 → (0,2) because 2+6? wait 2+8=10→j-- → 2+6=8→i++ → 3+6=9int[] twoSumSorted(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i < j) {
int s = a[i] + a[j];
if (s == target) return new int[]{i, j};
if (s < target) i++;
else j--;
}
return null;
}
// a=[2,3,6,8], target=9 → (0,2) because 2+6? wait 2+8=10→j-- → 2+6=8→i++ → 3+6=9Variable window — traced
Longest substring with ≤ k distinct characters. Expand right, count frequencies. While constraint broken, advance left and decrement. Track best length. The ‘why’: each index enters/leaves the window at most once → O(n).
from collections import defaultdict
def longest_at_most_k(s, k):
cnt = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
cnt[ch] += 1
while len(cnt) > k:
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
left += 1
best = max(best, right - left + 1)
return best
# s='aaba', k=2 → window grows a,aa,aab,aaba then shrinks when 3rd distinct appearsint longestAtMostK(String s, int k) {
Map<Character, Integer> cnt = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
cnt.merge(ch, 1, Integer::sum);
while (cnt.size() > k) {
char leftCh = s.charAt(left);
cnt.put(leftCh, cnt.get(leftCh) - 1);
if (cnt.get(leftCh) == 0) cnt.remove(leftCh);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// s='aaba', k=2 → window grows a,aa,aab,aaba then shrinks when 3rd distinct appearsWhat a good explanation sounds like
You: ‘I’ll keep a window [left,right] that always has at most k distinct chars. I expand right; when I break the rule I advance left until it’s valid again. Each index moves at most once, so O(n).’
When to reach for this pattern
Ask: Is the answer a pair of indices on sorted data, or a contiguous segment whose validity I can maintain while moving ends? If yes to the first, opposite ends. If yes to the second, window. If the array isn’t sorted and sorting destroys the answer (indices matter), don’t force two pointers.
Core template + worked trace
Variable window template. The window [left, right] is always a candidate substring; the map answers ‘is the constraint broken?’
from collections import defaultdict
def longest_at_most_k_distinct(s: str, k: int) -> int:
"""Longest substring with at most k distinct chars."""
cnt = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
cnt[ch] += 1 # expand
while len(cnt) > k: # shrink while invalid
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
left += 1
best = max(best, right - left + 1)
return best
# Trace: s='aaba', k=2
# right=0 'a' → {a:1} len=1 best=1
# right=1 'a' → {a:2} len=1 best=2
# right=2 'b' → {a:2,b:1} len=2 best=3
# right=3 'a' → {a:3,b:1} len=2 best=4
# (never needed shrink — only 2 distinct)
# Contrast s='abac', k=2 at right='c': shrink until len(cnt)<=2int longestAtMostKDistinct(String s, int k) {
// Longest substring with at most k distinct chars.
Map<Character, Integer> cnt = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
cnt.merge(ch, 1, Integer::sum); // expand
while (cnt.size() > k) { // shrink while invalid
char leftCh = s.charAt(left);
cnt.put(leftCh, cnt.get(leftCh) - 1);
if (cnt.get(leftCh) == 0) cnt.remove(leftCh);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// Trace: s='aaba', k=2
// right=0 'a' → {a:1} len=1 best=1
// right=1 'a' → {a:2} len=1 best=2
// right=2 'b' → {a:2,b:1} len=2 best=3
// right=3 'a' → {a:3,b:1} len=2 best=4
// (never needed shrink — only 2 distinct)
// Contrast s='abac', k=2 at right='c': shrink until len(cnt)<=2Opposite-end pair sum — each step discards an index, so O(n) after sort:
def two_sum_sorted(a: list[int], target: int):
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
if s == target:
return i, j
if s < target:
i += 1 # need a larger left
else:
j -= 1 # need a smaller right
return None
# a=[2,3,6,8], target=9
# (2,8)=10 → j-- ; (2,6)=8 → i++ ; (3,6)=9 → return (1,2)int[] twoSumSorted(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i < j) {
int s = a[i] + a[j];
if (s == target) return new int[]{i, j};
if (s < target) i++; // need a larger left
else j--; // need a smaller right
}
return null;
}
// a=[2,3,6,8], target=9
// (2,8)=10 → j-- ; (2,6)=8 → i++ ; (3,6)=9 → return (1,2)Edge cases & common bugs
Complexity — say it aloud
Each index moves at most once — that’s why windows beat nested loops. Say it before you code.
Interview talk track
You: ‘I’ll keep a window [left, right] that always represents a candidate substring with at most k distinct characters. I expand right; when the constraint breaks I advance left until it’s valid again. I maintain a frequency map so the check is O(1). Each index moves at most once → O(n).’
Practice set
- Two Sum II (sorted input)
- 3Sum (sort + two pointers)
- Container With Most Water
- Longest Substring Without Repeating Characters
- Longest Substring with At Most K Distinct Characters
- Minimum Window Substring
- Max Consecutive Ones III
- Permutation in String (fixed window / anagram)
Harder follow-up
Harder variant: Minimum Window Substring — now you need the shortest window that covers all chars of t (with frequencies), not ‘at most k distinct’. Same expand/shrink skeleton; change the validity check to have == need counters.
# Sketch — validity flips from "len(cnt) <= k" to "covered all required freqs"
# Expand right; while window valid, update best and shrink left.
# Speak: "valid means every char in t is satisfied; shrinking keeps it minimal." // Sketch — validity flips from "len(cnt) <= k" to "covered all required freqs"
// Expand right; while window valid, update best and shrink left.
// Speak: "valid means every char in t is satisfied; shrinking keeps it minimal." Pattern bank: more questions + efficient solutions
Five interview staples. Say the invariant before you code — ‘sorted ends discard’, ‘window always valid’, ‘height bottleneck’.
Q: 3Sum — given an integer array, return all unique triplets that sum to 0 (order of triplets does not matter; no duplicate triplets).
def three_sum(nums):
nums.sort()
n, out = len(nums), []
for i in range(n):
if i and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
out.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return out
# O(n^2) time, O(1) extra (excluding output)List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> out = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (s == 0) {
out.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
lo++; hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
} else if (s < 0) lo++;
else hi--;
}
}
return out;
}
// O(n^2) time, O(1) extra (excluding output)Q: Container With Most Water — heights form vertical lines; choose two indices to maximize area = min(height[i], height[j]) × (j − i).
def max_area(height):
lo, hi, best = 0, len(height) - 1, 0
while lo < hi:
best = max(best, min(height[lo], height[hi]) * (hi - lo))
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return best
# O(n) time, O(1) spaceint maxArea(int[] height) {
int lo = 0, hi = height.length - 1, best = 0;
while (lo < hi) {
best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));
if (height[lo] < height[hi]) lo++;
else hi--;
}
return best;
}
// O(n) time, O(1) spaceQ: Longest Substring Without Repeating Characters — return the length of the longest substring with all unique characters.
def length_of_longest_substring(s):
last = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return best
# O(n) time, O(min(n, alphabet)) spaceint lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (last.containsKey(ch) && last.get(ch) >= left)
left = last.get(ch) + 1;
last.put(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}
// O(n) time, O(min(n, alphabet)) spaceQ: Minimum Window Substring — given s and t, find the smallest substring of s that covers every character in t (including duplicates). Return "" if impossible.
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = best_l = 0
best_len = float("inf")
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left + 1 < best_len:
best_l, best_len = left, right - left + 1
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best_len == float("inf") else s[best_l:best_l + best_len]
# O(|s|+|t|) time, O(|Σ|) spaceString minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), left = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (need[ch] > 0) missing--;
need[ch]--;
while (missing == 0) {
if (right - left + 1 < bestLen) {
bestL = left;
bestLen = right - left + 1;
}
char leftCh = s.charAt(left);
need[leftCh]++;
if (need[leftCh] > 0) missing++;
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}
// O(|s|+|t|) time, O(|Σ|) spaceQ: Trapping Rain Water — elevation map; how much water can be trapped between bars (two-pointer / height-bottleneck solution preferred).
def trap(height):
lo, hi = 0, len(height) - 1
left_max = right_max = water = 0
while lo < hi:
if height[lo] < height[hi]:
left_max = max(left_max, height[lo])
water += left_max - height[lo]
lo += 1
else:
right_max = max(right_max, height[hi])
water += right_max - height[hi]
hi -= 1
return water
# O(n) time, O(1) spaceint trap(int[] height) {
int lo = 0, hi = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (lo < hi) {
if (height[lo] < height[hi]) {
leftMax = Math.max(leftMax, height[lo]);
water += leftMax - height[lo];
lo++;
} else {
rightMax = Math.max(rightMax, height[hi]);
water += rightMax - height[hi];
hi--;
}
}
return water;
}
// O(n) time, O(1) space