FAANG Interview Pattern Recognition

How to Use This Guide

Most interview failures come not from not knowing an algorithm, but from failing to recognise which pattern applies. This guide trains the recognition reflex: read the problem → spot the keyword cluster → map to a pattern → implement.

The Recognition Loop

Step 1: Read the problem statement. Underline the constraints (sorted? distinct? in-place? shortest? count?).

Step 2: Match keywords against the pattern table below.

Step 3: State the pattern out loud: "I think this is a [sliding window / BFS / DP] problem because..."

Step 4: Verify with a small example before coding. Write the template, then fill in problem-specific logic.

Master Pattern Table

                            
                                PatternKeywords in ProblemTimeKey Data Structure

                                Two Pointersorted array, pair sum, palindrome, in-place reverse\(O(n)\)Array (two indices)
Sliding Windowsubarray/substring, contiguous, longest/shortest, window\(O(n)\)Deque or hashmap
BFSshortest path, level-order, minimum steps, unweighted graph\(O(V + E)\)Queue (deque)
DFSall paths, connected components, cycle detection, count ways\(O(V + E)\)Stack / recursion
Backtrackingall combinations/permutations, generate, find all solutions\(O(2^n)\) or \(O(n!)\)Recursion + visited set
Binary Search on Answerminimum/maximum possible value, feasibility, "if you can do X"\(O(n \log n)\)Array (sorted answer space)
Monotonic Stacknext/previous greater/smaller, histogram, temperature\(O(n)\)Stack
Monotonic Dequesliding window max/min\(O(n)\)Deque
Heap (Top-K)K largest/smallest/closest, median, priorityO(n log K)Min/max heap
1D DPmaximize/minimize with 1 variable, climb stairs, coin change\(O(n)\)Array dp[n]
2D DPgrid path, edit distance, LCS, string comparison\(O(n \times m)\)Matrix dp[n][m]
Interval DPmerge intervals, burst balloons, matrix chain\(O(n^2)\) or \(O(n^3)\)dp[i][j]
Union-Findconnected components, merge groups, number of islands\(O(\alpha(n))\)DSU array
Trieprefix, autocomplete, word search, XOR\(O(L)\)Trie nodes

                            
                        

Pattern	Keywords in Problem	Time	Key Data Structure
Two Pointer	sorted array, pair sum, palindrome, in-place reverse	\(O(n)\)	Array (two indices)
Sliding Window	subarray/substring, contiguous, longest/shortest, window	\(O(n)\)	Deque or hashmap
BFS	shortest path, level-order, minimum steps, unweighted graph	\(O(V + E)\)	Queue (deque)
DFS	all paths, connected components, cycle detection, count ways	\(O(V + E)\)	Stack / recursion
Backtracking	all combinations/permutations, generate, find all solutions	\(O(2^n)\) or \(O(n!)\)	Recursion + visited set
Binary Search on Answer	minimum/maximum possible value, feasibility, "if you can do X"	\(O(n \log n)\)	Array (sorted answer space)
Monotonic Stack	next/previous greater/smaller, histogram, temperature	\(O(n)\)	Stack
Monotonic Deque	sliding window max/min	\(O(n)\)	Deque
Heap (Top-K)	K largest/smallest/closest, median, priority	O(n log K)	Min/max heap
1D DP	maximize/minimize with 1 variable, climb stairs, coin change	\(O(n)\)	Array dp[n]
2D DP	grid path, edit distance, LCS, string comparison	\(O(n \times m)\)	Matrix dp[n][m]
Interval DP	merge intervals, burst balloons, matrix chain	\(O(n^2)\) or \(O(n^3)\)	dp[i][j]
Union-Find	connected components, merge groups, number of islands	\(O(\alpha(n))\)	DSU array
Trie	prefix, autocomplete, word search, XOR	\(O(L)\)	Trie nodes

Two Pointer

Use two pointers when the array is sorted (or can be) and you're looking for pairs or palindromic properties. The pointers move toward each other or in the same direction (fast/slow).

Template: Two-Sum on Sorted Array

Keywords: sorted array, find pair with sum = target, no extra space.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# LeetCode 167: Two Sum II
print(two_sum_sorted([2,7,11,15], 9))  # [0,1]

// Two-Sum on Sorted Array — O(n) two pointer
#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int s = nums[left] + nums[right];
        if (s == target) return {left, right};
        else if (s < target) left++;
        else right--;
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    auto res = twoSumSorted(nums, 9);
    cout << "[" << res[0] << "," << res[1] << "]" << endl;  // [0,1]
}

// Two-Sum on Sorted Array — O(n) two pointer
import java.util.Arrays;

public class TwoSumSorted {
    public static int[] twoSumSorted(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int s = nums[left] + nums[right];
            if (s == target) return new int[]{left, right};
            else if (s < target) left++;
            else right--;
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] res = twoSumSorted(new int[]{2,7,11,15}, 9);
        System.out.println(Arrays.toString(res));  // [0, 1]
    }
}

Canonical problems: Two Sum II (167), Container With Most Water (11), 3Sum (15), Valid Palindrome (125), Trapping Rain Water (42).

Sliding Window

Sliding window solves "find longest/shortest subarray/substring satisfying condition X" in \(O(n)\). Expand right until condition violated; shrink left until condition restored.

Template: Longest Substring with At Most K Distinct Characters

from collections import defaultdict

def longest_substring_k_distinct(s, k):
    """O(n) sliding window with frequency map."""
    freq = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1                      # expand window
        while len(freq) > k:                     # shrink if constraint violated
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1) # update answer

    return max_len

print(longest_substring_k_distinct("araaci", 2))  # 4 ("araa")

// Sliding Window — Longest substring with at most K distinct chars
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int longestSubstringKDistinct(const string& s, int k) {
    unordered_map<char, int> freq;
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.size(); right++) {
        freq[s[right]]++;
        while (freq.size() > k) {
            if (--freq[s[left]] == 0) freq.erase(s[left]);
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    cout << longestSubstringKDistinct("araaci", 2) << endl;  // 4
}

// Sliding Window — Longest substring with at most K distinct chars
import java.util.HashMap;
import java.util.Map;

public class SlidingWindow {
    public static int longestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            freq.merge(s.charAt(right), 1, Integer::sum);
            while (freq.size() > k) {
                char c = s.charAt(left);
                freq.merge(c, -1, Integer::sum);
                if (freq.get(c) == 0) freq.remove(c);
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestSubstringKDistinct("araaci", 2));  // 4
    }
}

Canonical problems: Minimum Window Substring (76), Longest Substring Without Repeating Characters (3), Sliding Window Maximum (239), Permutation in String (567).

BFS vs DFS Decision

                            
                                QuestionUse BFSUse DFS

                                Shortest path (unweighted)?YesNo
Find if any path exists?EitherYes (simpler)
Count all paths?NoYes (backtracking)
Topological order?Kahn's (BFS)Post-order DFS
Detect cycle?EitherYes (DFS colors)
Tree level order?Yes (natural)Need explicit level tracking

Question	Use BFS	Use DFS
Shortest path (unweighted)?	Yes	No
Find if any path exists?	Either	Yes (simpler)
Count all paths?	No	Yes (backtracking)
Topological order?	Kahn's (BFS)	Post-order DFS
Detect cycle?	Either	Yes (DFS colors)
Tree level order?	Yes (natural)	Need explicit level tracking

Backtracking Template

Universal Backtracking Template

def backtrack(result, current, remaining_choices, ...):
    # Base case: if current is a complete solution
    if is_complete(current):
        result.append(current[:])  # copy!
        return

    for choice in remaining_choices:
        if is_valid(choice, current):
            current.append(choice)           # CHOOSE
            backtrack(result, current, ...)  # EXPLORE
            current.pop()                    # UNCHOOSE (backtrack)


# Example: Generate all subsets (LeetCode 78)
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])   # every state is valid (power set)
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

// Backtracking — Generate all subsets (LeetCode 78)
#include <iostream>
#include <vector>
using namespace std;

void backtrack(vector<int>& nums, int start,
               vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current);  // every state is valid
    for (int i = start; i < nums.size(); i++) {
        current.push_back(nums[i]);       // CHOOSE
        backtrack(nums, i + 1, current, result);  // EXPLORE
        current.pop_back();               // UNCHOOSE
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    backtrack(nums, 0, current, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    auto res = subsets(nums);
    for (auto& s : res) {
        cout << "[";
        for (int i = 0; i < s.size(); i++)
            cout << (i ? "," : "") << s[i];
        cout << "] ";
    }  // [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]
}

// Backtracking — Generate all subsets (LeetCode 78)
import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int start,
            List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));  // every state valid
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);              // CHOOSE
            backtrack(nums, i + 1, current, result);  // EXPLORE
            current.remove(current.size() - 1); // UNCHOOSE
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
        // [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
    }
}

Canonical problems: Subsets (78), Permutations (46), Combination Sum (39), N-Queens (51), Word Search (79), Sudoku Solver (37).

Dynamic Programming Patterns

DP works when the problem has: (1) optimal substructure — optimal solution contains optimal solutions to subproblems, and (2) overlapping subproblems — same subproblems recur many times.

1D DP Template: Coin Change

def coin_change(coins, amount):
    """LeetCode 322. Minimum coins to make amount."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 11], 15))  # 3 (5+5+5=3 coins)

// LeetCode 322 — Coin Change. O(amount * coins)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int coin : coins)
            if (coin <= a)
                dp[a] = min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 5, 11};
    cout << coinChange(coins, 15) << endl;  // 3
}

// LeetCode 322 — Coin Change. O(amount * coins)
import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int coin : coins)
                if (coin <= a)
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 5, 11}, 15));  // 3
    }
}

2D DP: Edit Distance

2D DP problems have state defined by two variables — typically two indices into strings, or row/column in a grid. The canonical examples are Longest Common Subsequence (build up matching characters from two sequences) and Edit Distance (minimum insertions, deletions, or substitutions to transform one string into another). The recurrence relates \(dp[i][j]\) to its neighbors: \(dp[i-1][j]\), \(dp[i][j-1]\), and \(dp[i-1][j-1]\), corresponding to the three possible operations.

Longest Common Subsequence (LeetCode 1143)

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs("abcde", "ace"))  # 3 (a,c,e)

// LeetCode 1143 — Longest Common Subsequence. O(m*n)
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int lcs(const string& text1, const string& text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (text1[i-1] == text2[j-1])
                ? dp[i-1][j-1] + 1
                : max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

int main() {
    cout << lcs("abcde", "ace") << endl;  // 3
}

// LeetCode 1143 — Longest Common Subsequence. O(m*n)
public class LCS {
    public static int lcs(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = (text1.charAt(i-1) == text2.charAt(j-1))
                    ? dp[i-1][j-1] + 1
                    : Math.max(dp[i-1][j], dp[i][j-1]);
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));  // 3
    }
}

Interval DP: Burst Balloons

Burst Balloons (LeetCode 312)

Think: which balloon is burst last in a range [i, j]? dp[i][j] = max coins from range i..j.

def maxCoins(nums):
    nums = [1] + nums + [1]  # pad with boundary 1s
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):          # window size
        for left in range(0, n - length):
            right = left + length
            for k in range(left+1, right):  # k = last balloon to burst
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]

print(maxCoins([3, 1, 5, 8]))  # 167

// LeetCode 312 — Burst Balloons. Interval DP O(n^3)
#include <iostream>
#include <vector>
using namespace std;

int maxCoins(vector<int>& nums) {
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int len = 2; len < n; len++)
        for (int left = 0; left < n - len; left++) {
            int right = left + len;
            for (int k = left+1; k < right; k++)
                dp[left][right] = max(dp[left][right],
                    nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right]);
        }
    return dp[0][n-1];
}

int main() {
    vector<int> nums = {3, 1, 5, 8};
    cout << maxCoins(nums) << endl;  // 167
}

// LeetCode 312 — Burst Balloons. Interval DP O(n^3)
public class BurstBalloons {
    public static int maxCoins(int[] nums) {
        int[] arr = new int[nums.length + 2];
        arr[0] = arr[arr.length - 1] = 1;
        System.arraycopy(nums, 0, arr, 1, nums.length);
        int n = arr.length;
        int[][] dp = new int[n][n];

        for (int len = 2; len < n; len++)
            for (int left = 0; left < n - len; left++) {
                int right = left + len;
                for (int k = left+1; k < right; k++)
                    dp[left][right] = Math.max(dp[left][right],
                        arr[left]*arr[k]*arr[right] + dp[left][k] + dp[k][right]);
            }
        return dp[0][n-1];
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));  // 167
    }
}

Monotonic Stack

Use when the problem asks: "for each element, find the nearest element to the left/right that is greater/smaller." Every element enters and exits the stack exactly once — \(O(n)\) total.

Next Greater Element (LeetCode 496)

def next_greater_element(nums1, nums2):
    """For each num in nums1, find the next greater element in nums2. O(n)."""
    next_greater = {}
    stack = []  # monotonically decreasing

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num  # found next greater
        stack.append(num)

    while stack:
        next_greater[stack.pop()] = -1  # no next greater

    return [next_greater[n] for n in nums1]

print(next_greater_element([4,1,2], [1,3,4,2]))  # [-1, 3, -1]

// LeetCode 496 — Next Greater Element. O(n) monotonic stack
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> nextGreater;
    stack<int> stk;

    for (int num : nums2) {
        while (!stk.empty() && stk.top() < num) {
            nextGreater[stk.top()] = num;
            stk.pop();
        }
        stk.push(num);
    }
    while (!stk.empty()) { nextGreater[stk.top()] = -1; stk.pop(); }

    vector<int> result;
    for (int n : nums1) result.push_back(nextGreater[n]);
    return result;
}

int main() {
    vector<int> n1 = {4,1,2}, n2 = {1,3,4,2};
    auto res = nextGreaterElement(n1, n2);
    for (int x : res) cout << x << " ";  // -1 3 -1
}

// LeetCode 496 — Next Greater Element. O(n) monotonic stack
import java.util.*;

public class NextGreater {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num)
                nextGreater.put(stack.pop(), num);
            stack.push(num);
        }
        while (!stack.isEmpty()) nextGreater.put(stack.pop(), -1);

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++)
            result[i] = nextGreater.get(nums1[i]);
        return result;
    }

    public static void main(String[] args) {
        int[] res = nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res));  // [-1, 3, -1]
    }
}

Canonical problems: Next Greater Element (496, 503), Daily Temperatures (739), Largest Rectangle in Histogram (84), Trapping Rain Water (42).

Binary Search on Answer

Use when the problem asks for "minimum/maximum value such that a condition holds". Binary search the answer space, check feasibility with a helper function.

Koko Eating Bananas (LeetCode 875)

import math

def min_eating_speed(piles, h):
    """Minimum speed k such that Koko finishes all piles in h hours."""
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid     # try smaller speed
        else:
            left = mid + 1  # need faster speed
    return left

print(min_eating_speed([3,6,7,11], 8))  # 4

// LeetCode 875 — Binary Search on Answer. O(n log max)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minEatingSpeed(vector<int>& piles, int h) {
    auto canFinish = [&](int k) {
        long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;  // ceil division
        return hours <= h;
    };

    int left = 1, right = *max_element(piles.begin(), piles.end());
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    cout << minEatingSpeed(piles, 8) << endl;  // 4
}

// LeetCode 875 — Binary Search on Answer. O(n log max)
import java.util.Arrays;

public class KokoEatingBananas {
    public static int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, mid, h)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    private static boolean canFinish(int[] piles, int k, int h) {
        long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;
        return hours <= h;
    }

    public static void main(String[] args) {
        System.out.println(minEatingSpeed(new int[]{3,6,7,11}, 8));  // 4
    }
}

Canonical problems: Search Insert Position (35), Find Peak Element (162), Koko Eating Bananas (875), Split Array Largest Sum (410), Capacity to Ship (1011).

Heap — Top-K Pattern

Any problem asking for the "K largest", "K closest", "K most frequent", or "Kth element" maps to a heap of size K. The strategy: maintain a min-heap of size K — when a new element is larger than the heap's minimum, replace it. After processing all elements, the heap contains the top-K. This gives \(O(n \log k)\) time, which is optimal when \(k \ll n\) since you avoid fully sorting the entire array.

K Closest Points to Origin (LeetCode 973)

import heapq

def k_closest(points, k):
    """O(n log k) — min-heap of size k (negate distance for max-heap)."""
    heap = []  # (-dist, x, y)

    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove the farthest

    return [[x, y] for (_, x, y) in heap]

print(k_closest([[1,3],[-2,2],[5,8],[0,1]], 2))  # [[0,1],[-2,2]]

// LeetCode 973 — K Closest Points. O(n log k) max-heap
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // Max-heap: largest distance at top
    auto cmp = [](vector<int>& a, vector<int>& b) {
        return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);

    for (auto& p : points) {
        pq.push(p);
        if (pq.size() > k) pq.pop();
    }

    vector<vector<int>> result;
    while (!pq.empty()) { result.push_back(pq.top()); pq.pop(); }
    return result;
}

int main() {
    vector<vector<int>> pts = {{1,3},{-2,2},{5,8},{0,1}};
    auto res = kClosest(pts, 2);
    for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
    // [0,1] [-2,2]
}

// LeetCode 973 — K Closest Points. O(n log k) max-heap
import java.util.*;

public class KClosest {
    public static int[][] kClosest(int[][] points, int k) {
        // Max-heap by distance
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
            (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1]));

        for (int[] p : points) {
            pq.offer(p);
            if (pq.size() > k) pq.poll();
        }

        int[][] result = new int[k][2];
        int i = 0;
        while (!pq.isEmpty()) result[i++] = pq.poll();
        return result;
    }

    public static void main(String[] args) {
        int[][] pts = {{1,3},{-2,2},{5,8},{0,1}};
        int[][] res = kClosest(pts, 2);
        for (int[] p : res)
            System.out.print(Arrays.toString(p) + " ");
        // [0, 1] [-2, 2]
    }
}

Canonical problems: K Closest Points (973), Top K Frequent Elements (347), Kth Largest Element (215), Merge K Sorted Lists (23), Median from Data Stream (295).

The 45-Minute Interview Framework

                            Time Budget
                            
                                TimeActivityWhat to Say

                                0–5 minClarify constraints"Is the array sorted? Can it have duplicates? What's the expected input size?"
5–10 minPattern recognition + brute force"My first thought is \(O(n^2)\) brute force... but I recognise this as a [pattern] problem, which should give \(O(n)\)."
10–12 minVerify approach with small exampleTrace through 3–4 elements manually. Catch edge cases.
12–35 minCodeWrite clean code with meaningful variable names. Talk through each step.
35–40 minTestRun through your example, then edge cases: empty input, single element, all same, sorted, reverse-sorted.
40–45 minComplexity analysis"Time: \(O(n \log n)\) because... Space: \(O(n)\) because... Could we reduce space to \(O(1)\) by...?"

                            
                        

Time	Activity	What to Say
0–5 min	Clarify constraints	"Is the array sorted? Can it have duplicates? What's the expected input size?"
5–10 min	Pattern recognition + brute force	"My first thought is \(O(n^2)\) brute force... but I recognise this as a [pattern] problem, which should give \(O(n)\)."
10–12 min	Verify approach with small example	Trace through 3–4 elements manually. Catch edge cases.
12–35 min	Code	Write clean code with meaningful variable names. Talk through each step.
35–40 min	Test	Run through your example, then edge cases: empty input, single element, all same, sorted, reverse-sorted.
40–45 min	Complexity analysis	"Time: \(O(n \log n)\) because... Space: \(O(n)\) because... Could we reduce space to \(O(1)\) by...?"

                            Common Interview Mistakes
                            Coding without clarifying: Always ask about constraints before touching the keyboard.
Jumping to optimal immediately: State brute force first, then optimise. Interviewers want to see your reasoning process.
Silent coding: Think out loud. If you're stuck, say "I'm thinking about whether I can use X here..."
Forgetting edge cases: Always test empty input and single-element input.
Wrong complexity claim: If you say \(O(n)\), know exactly why. Interviewers probe this.

                        

Table of Contents