Common Interview Patterns
Most array, string, and linked list interview questions are variations of a handful of patterns. Recognizing the pattern is usually the hard part; once you name it, the code almost writes itself. This doc walks through five patterns you will meet constantly, each with worked problems, complete solutions, and their complexity.
Two Pointers
Reach for two pointers when the input is sorted (or can be sorted) and you are looking for a pair, a triplet, or an in-place rearrangement. Instead of checking every pair with nested loops, you start one pointer at each end and move them toward each other based on what you see.
Problem: given a sorted array of integers and a target, return a pair of values that add up to the target, or null if none exists.
function pairWithSum(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) return [nums[left], nums[right]];
if (sum < target) left++;
else right--;
}
return null;
}
console.log(pairWithSum([1, 3, 4, 6, 8, 11], 10)); // [4, 6]
console.log(pairWithSum([2, 5, 9], 20)); // null
Why it works: because the array is sorted, a sum that is too small can only be fixed by moving left up, and a sum that is too large only by moving right down. No candidate pair is ever skipped.
Complexity: O(n) time — each pointer moves at most n steps — and O(1) extra space. The brute-force nested loop is O(n^2).
Sliding Window
Use a sliding window when the question mentions a contiguous subarray or substring: longest, shortest, or count of windows satisfying a condition. You grow the window from the right and shrink it from the left, so every element enters and leaves the window at most once.
The simplest form is a fixed-size window. Instead of re-summing k elements at every position — O(n * k) — subtract the element leaving the window and add the one entering:
function maxSumOfK(nums, k) {
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += nums[i];
let best = windowSum;
for (let i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k];
best = Math.max(best, windowSum);
}
return best;
}
console.log(maxSumOfK([2, 1, 5, 1, 3, 2], 3)); // 9 (5 + 1 + 3)
The harder — and more common — form is a variable-size window that grows and shrinks based on a condition.
Problem: find the length of the longest substring without repeating characters.
function longestUniqueSubstring(s) {
const lastSeen = new Map();
let start = 0;
let best = 0;
for (let end = 0; end < s.length; end++) {
const ch = s[end];
if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
start = lastSeen.get(ch) + 1;
}
lastSeen.set(ch, end);
best = Math.max(best, end - start + 1);
}
return best;
}
console.log(longestUniqueSubstring("abcabcbb")); // 3 ("abc")
console.log(longestUniqueSubstring("bbbbb")); // 1 ("b")
console.log(longestUniqueSubstring("pwwkew")); // 3 ("wke")
The window is always the range from start to end. When a repeat appears inside the window, start jumps just past the previous occurrence instead of resetting to zero — that jump is what keeps the algorithm linear.
Complexity: O(n) time, O(k) space where k is the size of the character set. The naive approach of checking every substring is O(n^3).
Frequency Counter
When a problem asks about frequencies — duplicates, anagrams, the first unique element, the most common element — count occurrences in a Map first, then answer the question with a second pass. Trading O(n) space for O(n) time is almost always the right deal in an interview.
Problem: return the index of the first non-repeating character in a string, or -1 if every character repeats.
function firstUniqueChar(s) {
const counts = new Map();
for (const ch of s) {
counts.set(ch, (counts.get(ch) || 0) + 1);
}
for (let i = 0; i < s.length; i++) {
if (counts.get(s[i]) === 1) return i;
}
return -1;
}
console.log(firstUniqueChar("leetcode")); // 0 ("l")
console.log(firstUniqueChar("loveleetcode")); // 2 ("v")
console.log(firstUniqueChar("aabbcc")); // -1
The same two-pass shape solves anagram checks (compare two count maps), finding the majority element, and grouping words by signature. If the keys are lowercase letters only, a 26-slot array works instead of a Map.
Complexity: O(n) time for two linear passes, O(k) space for the map where k is the number of distinct characters.
Fast and Slow Pointers
For linked lists — where you cannot index backwards or know the length up front — run two pointers at different speeds. The fast pointer moves two steps for every one step of the slow pointer. This detects cycles (the pointers meet) and finds the middle node (slow is halfway when fast reaches the end) without extra memory.
In a list like this, walking with a single pointer never terminates — node 4 points back to node 2. The fast pointer enters the loop first, and once both pointers are inside it, the gap closes by one node per step until they collide.
Problem: determine whether a linked list contains a cycle.
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
function middleNode(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
const a = new ListNode(1);
const b = new ListNode(2);
const c = new ListNode(3);
const d = new ListNode(4);
a.next = b;
b.next = c;
c.next = d;
console.log(hasCycle(a)); // false
console.log(middleNode(a).value); // 3
d.next = b; // create a cycle: 4 points back to 2
console.log(hasCycle(a)); // true
If there is a cycle, the fast pointer laps the slow pointer — the gap between them shrinks by one node per step, so they must meet. The obvious alternative, storing visited nodes in a Set, also works but costs O(n) memory; fast and slow pointers do it in constant space.
Complexity: O(n) time, O(1) space for both functions.
Recursion and Backtracking
When a problem asks for all combinations, permutations, subsets, or paths, no loop-based trick will save you — you need to explore a tree of choices. Backtracking is the disciplined way to do it: make a choice, recurse deeper, then undo the choice and try the next option.
Every recursive solution needs two parts:
- A base case — the input small enough to answer directly. Forget it and you recurse forever.
- A recursive case — reduce the problem one step and trust the function to handle the rest.
Problem: generate all subsets of an array. Each element poses one binary choice — in or out — which unfolds into a decision tree:
function subsets(nums) {
const result = [];
const current = [];
function backtrack(index) {
if (index === nums.length) {
result.push([...current]);
return;
}
current.push(nums[index]);
backtrack(index + 1);
current.pop();
backtrack(index + 1);
}
backtrack(0);
return result;
}
console.log(subsets([1, 2]));
// [[1, 2], [1], [2], []]
The push is the choice, the first recursive call explores everything that follows from it, and the pop is the backtrack — restoring state so the "skip it" branch starts clean. That push–recurse–pop rhythm is the entire pattern.
Problem: generate all permutations — same rhythm, but the choice at each step is which unused element comes next.
function permutations(items) {
const result = [];
const current = [];
const used = new Set();
function backtrack() {
if (current.length === items.length) {
result.push([...current]);
return;
}
for (const item of items) {
if (used.has(item)) continue;
used.add(item);
current.push(item);
backtrack();
current.pop();
used.delete(item);
}
}
backtrack();
return result;
}
console.log(permutations(["Rizwan", "Hafsa", "Ayesha"]).length); // 6
console.log(permutations(["Rizwan", "Hafsa", "Ayesha"])[0]);
// ["Rizwan", "Hafsa", "Ayesha"]
N-Queens, sudoku solvers, word search, and "restore valid IP addresses" are all this same skeleton with a stricter validity check before each recursive call — pruning branches that cannot lead to a solution.
Complexity: output-bound. There are 2^n subsets and n! permutations, so generating them costs O(2^n) and O(n * n!) respectively. Space is O(n) for the recursion depth, on top of whatever the output itself occupies. Exponential is unavoidable when the answer is exponential — the wins come from pruning.
Picking the Right Pattern
A quick mapping from problem wording to pattern:
| Signal in the problem statement | Pattern |
|---|---|
| Sorted array, find a pair or triplet with some property | Two pointers |
| Longest or shortest contiguous subarray or substring | Sliding window |
| Frequencies, duplicates, anagrams, first unique element | Frequency counter |
| Linked list cycle, middle node, or k-th node from the end | Fast and slow pointers |
| Generate all subsets, permutations, combinations, or paths | Recursion, backtracking |
When you practice, do not just solve the problem — write down which pattern it was and what wording gave it away. That recognition step is exactly what you have to do under interview pressure.