Chapter 7: DSA Pattern Mastery: The 14 Patterns That Solve 90% of Problems
If you're memorizing solutions, you've already lost.
The candidates cracking Rs 1 Cr packages don't memorize -- they pattern-match. They walk into the interview, hear the problem statement, and within thirty seconds they know which bucket it falls into. They're not smarter than you. They just built a different mental model.
You've felt this. You've solved 200 LeetCode problems and still freeze when the interviewer twists the problem by 10%. You've stayed up until 2 AM grinding "Top Interview 150" lists, only to blank on a medium-level graph problem because it was phrased differently than the one you memorized. The frustration is real. You know the syntax. You know the data structures. But when the problem doesn't match your flashcard, your brain goes empty.
Here's the truth nobody tells you about DSA interviews at Rs 60L+ companies: the interviewer is not testing whether you've seen the problem before. They're testing whether you can recognize the underlying pattern and adapt it. If you solve it from memory, they'll tweak one constraint and watch you crumble. If you solve it from first principles, they'll push you to the next round.
This chapter will rewire how you approach DSA. You will learn the 14 universal patterns that underlie 90% of interview problems. For each pattern, you'll get the tell-tale signs that scream "use me," a reusable template, and real problems solved step by step. By the end, you won't see 200 disconnected problems. You'll see 14 families, and every new problem will just be a cousin of one you already know.
The Pattern-Matching Mindset
Before we dive into the patterns, let's fix the mental model.
When Arjun, a backend engineer at a Bengaluru fintech startup, started interviewing for staff roles, he had solved exactly 87 LeetCode problems. Not 300. Not 500. Eighty-seven. But he had solved them differently. For each problem, he asked three questions:
- What is the smallest hint that tells me which pattern this is?
- What is the invariant -- the thing that stays true throughout the algorithm?
- How would I mutate this problem to make it unsolvable with this pattern?
He didn't count problems. He counted patterns. He got offers from Uber, Stripe, and a Rs 85 LPA staff role at a Series D startup. He picked the startup.
The difference between Arjun and the engineer who grinds 300 problems is not talent. It's categorization. Your brain retains information in chunks. A chess grandmaster doesn't memorize individual board positions -- they recognize patterns of pieces. A senior engineer doesn't memorize solutions -- they recognize problem structures.
Here's how you build that skill.
The Three-Second Rule
When you read a problem statement, you have three seconds to name the pattern. Not solve it. Just name it. If you can't, you don't understand the pattern well enough yet.
This sounds aggressive. It is. But the Rs 1 Cr interview loop at companies like Uber, Atlassian, and Stripe India moves fast. You don't get ten minutes to stare at the problem and try approaches. You get maybe sixty seconds of thinking out loud before the interviewer expects you to start coding. The three-second rule trains your pattern-recognition speed.
For the rest of this chapter, after each pattern, I'll give you a "Spot the Pattern" exercise. Read the problem statement. Three seconds. Name the pattern. Then check the answer. Do this until it's automatic.
The 14 Patterns
Here they are. These are not "tricks" or "hacks." They are the fundamental algorithmic strategies that appear in virtually every coding interview, from Swiggy's SDE-2 loop to Google India's L5 bar.
- Sliding Window -- Contiguous subarrays/substrings with a constraint
- Two Pointers -- Sorted arrays, pairs, triplets
- Fast & Slow Pointers -- Cycle detection, middle of linked list
- Merge Intervals -- Overlapping intervals, meeting rooms
- Cyclic Sort -- Numbers 1 to N, find missing/duplicate
- In-place Reversal of LinkedList -- Reverse sublists, rotate
- Tree BFS -- Level-order, shortest path in unweighted graphs
- Tree DFS -- Path sum, LCA, diameter
- Two Heaps -- Median of stream, sliding window median
- Subsets -- Permutations, combinations, subsets
- Modified Binary Search -- Search in rotated array, bitonic array
- Top K Elements -- K largest, K frequent, K closest
- K-way Merge -- Merge K sorted lists, Kth smallest in sorted matrix
- Topological Sort -- Task scheduling, course prerequisites, dependency resolution
Let's go through each one. I'll give you the tell-tale signs first -- because pattern recognition starts with the problem statement, not the solution.
Pattern 1: Sliding Window
Tell-tale signs:
- The input is an array, string, or linked list
- You're asked for a contiguous subarray/substring
- There's a constraint: max sum, longest substring with K distinct chars, smallest subarray with sum >= S
- Keywords: "subarray," "substring," "contiguous," "window," "consecutive"
If you see "contiguous" and a constraint, your brain should scream "Sliding Window" before you finish reading the sentence.
The Template:
function slidingWindow(arr, k) {
let windowStart = 0;
let windowState = 0; // sum, frequency map, whatever tracks the window
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
// 1. Add arr[windowEnd] to window state
windowState += arr[windowEnd];
// 2. Shrink window while constraint is violated
while (constraintViolated(windowState)) {
windowState -= arr[windowStart];
windowStart++;
}
// 3. Update result based on current valid window
updateResult(windowStart, windowEnd, windowState);
}
return result;
}
The genius of this pattern is that it turns an O(N squared) brute force into O(N). You never recompute the entire window from scratch. You slide -- add the new element, remove the old one. Each element enters and leaves the window exactly once.
Example 1: Maximum Sum Subarray of Size K (LeetCode 643 -- variant)
Problem: Given an array of positive integers and a number K, find the maximum sum of any contiguous subarray of size K.
This is the "hello world" of sliding window. Fixed-size window. No shrinking condition.
function maxSumSubarray(arr, k) {
let windowSum = 0;
let maxSum = -Infinity;
let windowStart = 0;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
windowSum += arr[windowEnd];
// Window has reached size k
if (windowEnd >= k - 1) {
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[windowStart];
windowStart++;
}
}
return maxSum;
}
// maxSumSubarray([2, 1, 5, 1, 3, 2], 3) -> 9 (subarray [5, 1, 3])
Notice the structure: add right, check window size, update result, remove left. This exact skeleton appears in dozens of problems.
Example 2: Longest Substring with K Distinct Characters
Problem: Given a string, find the length of the longest substring with no more than K distinct characters.
Now the window size is dynamic. We shrink when we exceed K distinct characters.
function longestSubstringKDistinct(str, k) {
const charFreq = new Map();
let windowStart = 0;
let maxLength = 0;
for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
const rightChar = str[windowEnd];
charFreq.set(rightChar, (charFreq.get(rightChar) || 0) + 1);
// Shrink: too many distinct characters
while (charFreq.size > k) {
const leftChar = str[windowStart];
charFreq.set(leftChar, charFreq.get(leftChar) - 1);
if (charFreq.get(leftChar) === 0) {
charFreq.delete(leftChar);
}
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
// longestSubstringKDistinct("araaci", 2) -> 4 ("araa")
// longestSubstringKDistinct("araaci", 1) -> 2 ("aa")
Same skeleton. Different constraint. The while loop is the key -- it shrinks the window until the constraint is satisfied again. Every element enters once, leaves at most once. O(N).
Example 3: Minimum Window Substring (LeetCode 76)
Problem: Given two strings s and t, find the minimum window in s that contains all characters of t (including duplicates).
This is the Sliding Window problem that appears in Staff and Principal-level interviews. It tests whether you truly understand the pattern or just memorized the easy variants.
function minWindow(s, t) {
if (t.length > s.length) return '';
const need = new Map();
for (const char of t) {
need.set(char, (need.get(char) || 0) + 1);
}
const have = new Map();
let windowStart = 0;
let minStart = 0;
let minLen = Infinity;
let matched = 0; // Count of characters with satisfied frequency
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const rightChar = s[windowEnd];
if (need.has(rightChar)) {
have.set(rightChar, (have.get(rightChar) || 0) + 1);
if (have.get(rightChar) === need.get(rightChar)) {
matched++;
}
}
// When all characters are satisfied, try to shrink from left
while (matched === need.size) {
// Update minimum window
const windowLen = windowEnd - windowStart + 1;
if (windowLen < minLen) {
minLen = windowLen;
minStart = windowStart;
}
const leftChar = s[windowStart];
if (need.has(leftChar)) {
if (have.get(leftChar) === need.get(leftChar)) {
matched--;
}
have.set(leftChar, have.get(leftChar) - 1);
}
windowStart++;
}
}
return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}
// minWindow("ADOBECODEBANC", "ABC") -> "BANC"
The twist here: the constraint is not a simple count. You need to track how many distinct required characters are fully satisfied. The matched counter lets you check the constraint in O(1) instead of scanning the entire need map every time. This is the difference between a working solution and an optimal one -- and it's exactly the kind of optimization an interviewer at Uber or Google will push you toward.
Spot the Pattern (3 seconds each):
- "Given an array of positive numbers and a positive number S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S."
- "Given a string, find the length of the longest substring without repeating characters."
Answers: Both are Sliding Window. Problem 1 uses a dynamic window that shrinks when sum >= S. Problem 2 shrinks when a duplicate appears.
Pattern 2: Two Pointers
Tell-tale signs:
- The input is sorted (or you can sort it without losing the answer)
- You're finding pairs, triplets, or comparing elements from both ends
- Keywords: "pair with target sum," "triplet sum to zero," "remove duplicates," "container with most water," "Dutch national flag"
Two Pointers is the simplest pattern and the most frequently underestimated. Engineers who skip it because "it's too basic" are the ones who fail the triplet-sum-to-zero problem because they can't handle duplicates correctly.
The Template:
function twoPointers(arr) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const current = compute(arr[left], arr[right]);
if (current === target) {
// Found it -- record result, then move BOTH pointers
left++;
right--;
} else if (current < target) {
left++; // Need a larger value
} else {
right--; // Need a smaller value
}
}
}
The invariant: at every step, the answer is either at left, at right, or somewhere between them. You never skip past the answer because the array is sorted.
Example 1: Triplet Sum to Zero (LeetCode 15)
Problem: Given an unsorted array, find all unique triplets that sum to zero.
This is the problem that separates pattern-matchers from memorizers. The memorizer tries three nested loops. The pattern-matcher sees "triplets" -> "pairs with a twist" -> Two Pointers.
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
// Skip duplicate first elements
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
// Skip duplicate second elements
while (left < right && nums[left] === nums[left - 1]) left++;
// Skip duplicate third elements
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
The duplicate-skipping logic is what trips people up. If you memorized the solution, you'll forget the left < right guard in the inner while loops and get an index-out-of-bounds. If you understand the pattern, you know why those guards exist: the pointers can cross after the outer left++/right--.
Example 2: Container With Most Water (LeetCode 11)
Problem: Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
const width = right - left;
const h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, width * h);
// Move the shorter line inward -- the taller one might still be useful
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
The insight: the area is limited by the shorter line. Moving the taller line inward can never increase the area (width decreases, height is still capped by the shorter line). So you always move the shorter one. This is not a trick -- it's a direct consequence of the two-pointer invariant.
Example 3: Trapping Rain Water (LeetCode 42)
Problem: Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
This is the Two Pointers problem that appears in Principal-level interviews. It looks like a dynamic programming problem at first glance. It's not. Two pointers solve it in O(N) time and O(1) space.
function trap(height) {
if (height.length === 0) return 0;
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
// The left side is the bottleneck
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
// The right side is the bottleneck
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
// trap([0,1,0,2,1,0,1,3,2,1,2,1]) -> 6
The insight: at any position, the water trapped is determined by the smaller of the maximum heights to the left and right. By moving the pointer at the shorter side inward, you always know one of the two boundaries (the taller side is at least as tall as the current max on that side). You don't need to precompute left-max and right-max arrays. Two pointers give you O(1) space.
This problem humbles engineers who think Two Pointers is "too easy." The pattern is simple. The application is not.
Spot the Pattern:
- "Given a sorted array, return the pair of numbers whose sum is closest to zero."
- "Given an array with 0s, 1s, and 2s, sort it in-place." (Dutch National Flag)
Answers: Both are Two Pointers. Problem 1 is classic two-pointer on sorted array. Problem 2 uses three pointers (low, mid, high) -- a variant of the same idea.
Pattern 3: Fast & Slow Pointers
Tell-tale signs:
- The data structure is a linked list (or an array treated as a linked list via index jumps)
- You need to detect a cycle, find the start of a cycle, or find the middle
- Keywords: "cycle," "loop," "happy number," "middle of linked list," "palindrome linked list"
This pattern is narrow but high-frequency. Every linked list problem that isn't a simple traversal probably uses fast and slow pointers.
The Template:
function fastSlow(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next; // One step
fast = fast.next.next; // Two steps
if (slow === fast) {
// Cycle detected -- or middle found
break;
}
}
}
The math: if fast moves twice as fast as slow, and there's a cycle, fast will lap slow within one cycle length. If there's no cycle, fast hits null and we know the list is acyclic.
Example 1: Linked List Cycle II (LeetCode 142)
Problem: Given the head of a linked list, return the node where the cycle begins. If no cycle, return null.
function detectCycle(head) {
let slow = head;
let fast = head;
// Phase 1: Find meeting point
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
// No cycle
if (fast === null || fast.next === null) return null;
// Phase 2: Find cycle start
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
Phase 2 is the part people memorize without understanding. Here's why it works: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going forward). So resetting one pointer to head and moving both at the same speed makes them meet at the cycle start. You don't need to memorize this proof -- you need to know that Phase 2 exists and when to use it.
Example 2: Find Middle of Linked List
function findMiddle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // When fast reaches end, slow is at middle
}
This is the building block for merge-sorting a linked list, checking palindrome linked lists, and reordering lists. Three problems, one pattern.
Example 3: Happy Number (LeetCode 202)
Problem: Write an algorithm to determine if a number n is "happy." Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (it will stay at 1), or it loops endlessly in a cycle that does not include 1. Return true if it reaches 1.
This problem does not look like a linked list problem. That's the point. The pattern-matcher sees "loops endlessly in a cycle" and thinks Fast & Slow Pointers. The sequence of numbers is an implicit linked list where each number points to the sum-of-squares of its digits.
function isHappy(n) {
function getNext(num) {
let sum = 0;
while (num > 0) {
const digit = num % 10;
sum += digit * digit;
num = Math.floor(num / 10);
}
return sum;
}
let slow = n;
let fast = getNext(n);
while (fast !== 1 && slow !== fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
}
// isHappy(19) -> true
// 1^2 + 9^2 = 82 -> 68 -> 100 -> 1
// isHappy(2) -> false (enters a cycle: 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4)
The key realization: if the number is happy, the sequence reaches 1 and stays there (fast hits 1). If it's unhappy, the sequence enters a cycle that does not include 1 (slow and fast meet somewhere in the cycle). The "linked list" is implicit -- each number's "next" pointer is getNext(num). This is the kind of lateral thinking that separates pattern-matchers from memorizers.
Spot the Pattern:
- "Write an algorithm to determine if a number is 'happy.' A happy number eventually reaches 1 when you repeatedly replace it with the sum of squares of its digits."
- "Given a linked list, reorder it to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2..."
Answers: Problem 1 is Fast & Slow Pointers (treat the sequence as an implicit linked list -- if it cycles, it's not happy). Problem 2 uses Find Middle + Reverse Second Half + Merge -- a composition of Fast & Slow and In-place Reversal.
Pattern 4: Merge Intervals
Tell-tale signs:
- You're given a collection of intervals (start, end)
- You need to merge overlapping intervals, find gaps, or count conflicts
- Keywords: "intervals," "overlapping," "meeting rooms," "merge," "conflicting," "free time"
The Template:
function mergeIntervals(intervals) {
// 1. Sort by start time
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const last = merged[merged.length - 1];
if (current[0] <= last[1]) {
// Overlap: merge by extending the end
last[1] = Math.max(last[1], current[1]);
} else {
// No overlap: add as new interval
merged.push(current);
}
}
return merged;
}
The sort is non-negotiable. Without sorting, you can't guarantee that overlapping intervals are adjacent. Every Merge Intervals problem starts with a sort.
Example 1: Meeting Rooms II (LeetCode 253)
Problem: Given an array of meeting time intervals, find the minimum number of conference rooms required.
function minMeetingRooms(intervals) {
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0;
let endPtr = 0;
for (let i = 0; i < starts.length; i++) {
if (starts[i] < ends[endPtr]) {
rooms++; // New meeting starts before earliest one ends -- need a room
} else {
endPtr++; // A meeting ended, reuse its room
}
}
return rooms;
}
This is a clever variant. Instead of maintaining a merged list, you track start and end times separately. When a meeting starts before the earliest-ending meeting finishes, you need a new room. Otherwise, you reuse a room. This is also a Two Heaps problem in disguise -- but the two-array approach is cleaner for this specific case.
Example 2: Insert Interval (LeetCode 57)
Problem: Given a sorted, non-overlapping list of intervals and a new interval, insert and merge.
function insert(intervals, newInterval) {
const result = [];
let i = 0;
// Add all intervals that end before newInterval starts
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge all overlapping intervals
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Add remaining intervals
while (i < intervals.length) {
result.push(intervals[i]);
i++;
}
return result;
}
Three phases: before overlap, during overlap, after overlap. Clean. Linear. No nested loops.
Example 3: Employee Free Time (LeetCode 759)
Problem: You are given a list of employee work schedules. Each employee has a list of non-overlapping intervals representing their working hours. Find the common free time intervals across all employees -- the time periods when all employees are free.
This is Merge Intervals applied to a different question. Instead of merging overlaps, you merge all intervals and then find the gaps between them.
function employeeFreeTime(schedules) {
// Flatten all schedules into a single list of intervals
const allIntervals = [];
for (const schedule of schedules) {
for (const interval of schedule) {
allIntervals.push(interval);
}
}
// Sort by start time
allIntervals.sort((a, b) => a[0] - b[0]);
// Merge all intervals
const merged = [allIntervals[0]];
for (let i = 1; i < allIntervals.length; i++) {
const last = merged[merged.length - 1];
if (allIntervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], allIntervals[i][1]);
} else {
merged.push(allIntervals[i]);
}
}
// Find gaps between merged intervals
const freeTime = [];
for (let i = 1; i < merged.length; i++) {
freeTime.push([merged[i - 1][1], merged[i][0]]);
}
return freeTime;
}
// employeeFreeTime([
// [[1, 2], [5, 6]],
// [[1, 3]],
// [[4, 10]]
// ]) -> [[3, 4]] (only gap where everyone is free)
The pattern is identical to basic Merge Intervals. The only difference is what you do after merging: instead of returning the merged list, you return the gaps. This is the kind of twist that interviewers love -- same core algorithm, different output. If you memorized the merge, you freeze. If you understand the pattern, you adapt.
Spot the Pattern:
- "Given a list of employee work schedules (each schedule is a list of intervals), find the common free time across all employees."
- "Given a set of intervals, find the interval that overlaps with the most other intervals."
Answers: Both are Merge Intervals. Problem 1 merges all schedules and finds gaps. Problem 2 uses a sweep line (sort all start and end points).
Pattern 5: Cyclic Sort
Tell-tale signs:
- The input is an array containing numbers in a known range (usually 1 to N)
- You need to find missing numbers, duplicates, or corrupt pairs
- Keywords: "numbers 1 to n," "find the missing number," "find all duplicates," "find the corrupt pair"
This pattern is deceptively simple. It sorts the array in O(N) time and O(1) space by placing each number at its correct index. No comparison-based sort can do this -- it works only because we know the exact range.
The Template:
function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const correctIndex = nums[i] - 1; // Number 3 belongs at index 2
if (nums[i] !== nums[correctIndex]) {
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
} else {
i++;
}
}
return nums;
}
Each swap places at least one number in its correct position. Maximum N swaps. O(N) time, O(1) space.
Example 1: Find the Missing Number (LeetCode 268)
function missingNumber(nums) {
let i = 0;
while (i < nums.length) {
const correctIndex = nums[i];
if (nums[i] < nums.length && nums[i] !== nums[correctIndex]) {
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
} else {
i++;
}
}
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== j) return j;
}
return nums.length;
}
After cyclic sort, every number is at its index. The first index where the number doesn't match is the missing one.
Example 2: Find All Duplicates in an Array (LeetCode 442)
function findDuplicates(nums) {
const duplicates = [];
let i = 0;
while (i < nums.length) {
const correctIndex = nums[i] - 1;
if (nums[i] !== nums[correctIndex]) {
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
} else {
i++;
}
}
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== j + 1) {
duplicates.push(nums[j]);
}
}
return duplicates;
}
Same sort. Different post-processing. The pattern is identical -- only the question you ask after sorting changes.
Example 3: Find the Corrupt Pair (LeetCode 645 -- Set Mismatch)
Problem: You have a set of integers 1 to N, but one number got duplicated and one number got lost. Find the duplicated number and the missing number.
This problem tests whether you can extract two pieces of information from the same cyclic sort.
function findErrorNums(nums) {
let i = 0;
while (i < nums.length) {
const correctIndex = nums[i] - 1;
if (nums[i] !== nums[correctIndex]) {
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
} else {
i++;
}
}
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== j + 1) {
// nums[j] is the duplicate, j + 1 is the missing number
return [nums[j], j + 1];
}
}
return [];
}
// findErrorNums([1, 2, 2, 4]) -> [2, 3]
// 2 is duplicated, 3 is missing
Same cyclic sort. Same post-processing scan. But now you return both the value at the wrong position (the duplicate) and the expected value (the missing number). Two answers from one pass. This is the elegance of Cyclic Sort -- once the array is arranged, all anomalies are visible in a single scan.
Spot the Pattern:
- "You are given an unsorted array containing numbers taken from the range 1 to n. The array can have duplicates. Find all the missing numbers."
- "Given an array containing n distinct numbers taken from 0 to n, find the one that is missing."
Answers: Both are Cyclic Sort. The range is known, the numbers are contiguous, and you need to find what's missing or duplicated.
Pattern 6: In-place Reversal of Linked List
Tell-tale signs:
- You're working with a singly linked list
- You need to reverse the entire list, a sublist, or every K-group
- Keywords: "reverse," "rotate," "reverse sublist," "reverse every k elements"
The Template:
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const next = current.next; // Save the next node
current.next = prev; // Reverse the pointer
prev = current; // Advance prev
current = next; // Advance current
}
return prev; // New head
}
Three pointers: prev, current, next. The dance is always the same: save next, reverse link, advance. If you can write this in your sleep, you can solve every reversal variant.
Example 1: Reverse a Sublist (LeetCode 92)
function reverseBetween(head, left, right) {
if (left === right) return head;
const dummy = { next: head, val: 0 };
let before = dummy;
// Move 'before' to the node just before the reversal starts
for (let i = 1; i < left; i++) {
before = before.next;
}
let prev = null;
let current = before.next;
for (let i = 0; i <= right - left; i++) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
// Reconnect: the original start now points to the node after reversal
before.next.next = current;
before.next = prev;
return dummy.next;
}
The dummy node trick is essential. It handles the edge case where left = 1 (reversal starts at head) without special-casing. Every linked list problem benefits from a dummy head.
Example 2: Reverse Nodes in K-Group (LeetCode 25)
Problem: Given a linked list, reverse the nodes of the list K at a time and return the modified list. If the number of nodes is not a multiple of K, the leftover nodes at the end should remain as they are.
This is the In-place Reversal problem that appears in Google and Microsoft interviews. It combines the basic reversal with group-boundary management.
function reverseKGroup(head, k) {
// Count total nodes
let count = 0;
let node = head;
while (node) {
count++;
node = node.next;
}
const dummy = { next: head, val: 0 };
let groupPrev = dummy;
while (count >= k) {
// Reverse K nodes starting from groupPrev.next
let prev = null;
let current = groupPrev.next;
for (let i = 0; i < k; i++) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
// Reconnect: the original first node of the group now points to current
const groupStart = groupPrev.next;
groupStart.next = current;
groupPrev.next = prev;
groupPrev = groupStart;
count -= k;
}
return dummy.next;
}
// Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2
// Output: 2 -> 1 -> 4 -> 3 -> 5
// Input: 1 -> 2 -> 3 -> 4 -> 5, k = 3
// Output: 3 -> 2 -> 1 -> 4 -> 5 (last 2 nodes unchanged)
The core reversal loop is identical to the basic template. What makes this problem hard is the reconnection logic: after reversing a group, you need to wire the previous group's tail to the new head of the reversed group, and the new tail (the original first node) to the start of the next group. The groupPrev pointer tracks the node just before the current group, and groupStart remembers the first node of the group (which becomes the last after reversal).
If you can solve this problem on a whiteboard without running the code, you understand In-place Reversal. If you can't, go back to the template and trace it on paper for K=2, K=3, and K=1 (edge case). The reconnection is the only new part.
Spot the Pattern:
- "Given a linked list, rotate it to the right by K places."
- "Given a linked list, reverse every K-group of nodes."
Answers: Both are In-place Reversal. Problem 1 finds the (length - K % length)th node, reverses the two halves, and reconnects. Problem 2 reverses in chunks of K.
Pattern 7: Tree BFS (Breadth-First Search)
Tell-tale signs:
- You're working with a tree (or a graph where BFS is appropriate)
- You need level-order traversal, or the problem involves processing level by level
- Keywords: "level order," "zigzag," "right side view," "minimum depth," "connect level order siblings"
The Template:
function bfs(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
The levelSize variable is the key. It captures how many nodes are in the current level before you start processing. Without it, you can't distinguish level boundaries.
Example 1: Binary Tree Right Side View (LeetCode 199)
function rightSideView(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
// Last node in the level = rightmost visible node
if (i === levelSize - 1) {
result.push(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
}
Same BFS skeleton. The only change: instead of collecting the entire level, you collect only the last node. The pattern is identical -- the output is what changes.
Example 2: Binary Tree Zigzag Level Order Traversal (LeetCode 103)
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (leftToRight) {
currentLevel.push(node.val);
} else {
currentLevel.unshift(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
leftToRight = !leftToRight;
}
return result;
}
Again, same skeleton. The toggle leftToRight controls whether we push or unshift. The BFS structure doesn't change -- only the per-level processing does.
Example 3: Populating Next Right Pointers in Each Node (LeetCode 116)
Problem: You are given a perfect binary tree where all leaves are on the same level. Populate each node's next pointer to point to its right sibling at the same level. If there is no right sibling, set next to null.
function connect(root) {
if (!root) return null;
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
let prev = null;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
// Connect previous node in this level to current node
if (prev) {
prev.next = node;
}
prev = node;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
// Last node in level already has next = null (default)
}
return root;
}
The BFS skeleton is unchanged. The only addition is a prev variable that tracks the previously processed node at the current level. At each step, you connect prev.next = node. The last node in each level keeps its default next = null. This is the same pattern that powers "right side view" and "zigzag" -- the BFS loop is identical, and only the per-node action changes.
Spot the Pattern:
- "Given a binary tree, connect each node to its right sibling at the same level."
- "Find the minimum depth of a binary tree -- the number of nodes along the shortest path from root to the nearest leaf."
Answers: Both are Tree BFS. Problem 1 connects nodes within the level loop. Problem 2 returns the depth as soon as you encounter a leaf node (no children).
Pattern 8: Tree DFS (Depth-First Search)
Tell-tale signs:
- You need to traverse all paths, compute something per-path, or find a specific path
- The answer depends on aggregating results from children
- Keywords: "path sum," "root to leaf," "diameter," "LCA," "max depth," "all paths"
The Template (Recursive):
function dfs(node) {
if (!node) return baseCase;
const leftResult = dfs(node.left);
const rightResult = dfs(node.right);
// Combine left and right results with current node
return combine(node, leftResult, rightResult);
}
Tree DFS is fundamentally recursive. The base case handles null nodes. The recursive calls handle subtrees. The combine step is where the problem-specific logic lives.
Example 1: Lowest Common Ancestor (LeetCode 236)
function lowestCommonAncestor(root, p, q) {
if (!root) return null;
if (root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// If both subtrees return non-null, current node is LCA
if (left && right) return root;
// Otherwise, propagate the non-null result upward
return left || right;
}
The logic is elegant: if p and q are in different subtrees, the current node is the LCA. If they're in the same subtree, the LCA is somewhere below, and we propagate it up. Four lines of actual logic.
Example 2: Diameter of Binary Tree (LeetCode 543)
function diameterOfBinaryTree(root) {
let maxDiameter = 0;
function height(node) {
if (!node) return 0;
const leftHeight = height(node.left);
const rightHeight = height(node.right);
// Diameter through this node = left height + right height
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// Return height of this subtree
return 1 + Math.max(leftHeight, rightHeight);
}
height(root);
return maxDiameter;
}
This is the classic "compute two things in one pass" pattern. The function returns height, but it also updates a closure variable for diameter. You can't compute diameter from height after the fact -- you need both simultaneously.
Example 3: Binary Tree Maximum Path Sum (LeetCode 124)
Problem: Given a binary tree, find the maximum path sum. A path may start and end at any node, and you can only go from parent to child (no backtracking up then down).
This is the Tree DFS problem that appears in Principal-level interviews. It's the diameter pattern applied to sums instead of edge counts, with the added twist that you can choose to not include a subtree if it contributes a negative sum.
function maxPathSum(root) {
let globalMax = -Infinity;
function maxGain(node) {
if (!node) return 0;
// Only include a subtree if it contributes positively
const leftGain = Math.max(maxGain(node.left), 0);
const rightGain = Math.max(maxGain(node.right), 0);
// Path that goes through this node (may be the final answer)
const pathThroughNode = node.val + leftGain + rightGain;
globalMax = Math.max(globalMax, pathThroughNode);
// Return the max single-branch gain (for the parent to use)
return node.val + Math.max(leftGain, rightGain);
}
maxGain(root);
return globalMax;
}
// For tree: [-10, 9, 20, null, null, 15, 7]
// maxPathSum -> 42 (path: 15 -> 20 -> 7)
The structure is identical to the diameter problem: a recursive helper that returns one value (max single-branch gain) while updating a closure variable (global max). The new element is the Math.max(..., 0) -- you can choose to abandon a subtree entirely if it would reduce the sum. This is the same DFS skeleton with one extra decision at the combine step.
Spot the Pattern:
- "Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum."
- "Given a binary tree, find the maximum path sum. The path may start and end at any node."
Answers: Both are Tree DFS. Problem 1 is a standard path-tracking DFS. Problem 2 is the diameter pattern applied to sums instead of edge counts.
Pattern 9: Two Heaps
Tell-tale signs:
- You need the median of a data stream
- You need the smallest/largest element that changes dynamically
- Keywords: "median," "sliding window median," "find median from data stream," "schedule tasks on CPUs"
The Template:
// MaxHeap for the smaller half, MinHeap for the larger half
class MedianFinder {
constructor() {
this.maxHeap = new MaxPriorityQueue(); // Lower half
this.minHeap = new MinPriorityQueue(); // Upper half
}
addNum(num) {
if (this.maxHeap.isEmpty() || num <= this.maxHeap.front()) {
this.maxHeap.enqueue(num);
} else {
this.minHeap.enqueue(num);
}
// Balance: maxHeap can have at most 1 more element than minHeap
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.enqueue(this.maxHeap.dequeue());
} else if (this.minHeap.size() > this.maxHeap.size()) {
this.maxHeap.enqueue(this.minHeap.dequeue());
}
}
findMedian() {
if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.front();
}
return (this.maxHeap.front() + this.minHeap.front()) / 2;
}
}
The invariant: maxHeap holds the smaller half of numbers, minHeap holds the larger half. The median is either the top of maxHeap (odd count) or the average of both tops (even count). Insertion is O(log N). Median lookup is O(1).
In JavaScript, there's no built-in heap. You'll need to implement one or use a known pattern. For interviews at Rs 60L+ companies, you're expected to be able to code a basic heap. Here's a minimal MaxHeap:
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const max = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._sinkDown(0);
}
return max;
}
peek() { return this.heap[0]; }
size() { return this.heap.length; }
_bubbleUp(idx) {
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (this.heap[parent] >= this.heap[idx]) break;
[this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
idx = parent;
}
}
_sinkDown(idx) {
const n = this.heap.length;
while (true) {
let largest = idx;
const left = 2 * idx + 1;
const right = 2 * idx + 2;
if (left < n && this.heap[left] > this.heap[largest]) largest = left;
if (right < n && this.heap[right] > this.heap[largest]) largest = right;
if (largest === idx) break;
[this.heap[idx], this.heap[largest]] = [this.heap[largest], this.heap[idx]];
idx = largest;
}
}
}
Yes, you need to know this. No, you don't need to memorize it character by character. Understand the heap property (parent >= children for max-heap), understand bubble-up and sink-down, and you can reconstruct it.
Example 1: Sliding Window Median (LeetCode 480)
This combines Sliding Window and Two Heaps. For each window, maintain two heaps and remove the outgoing element. The removal is the hard part -- you need lazy deletion (mark elements as removed and clean up when they reach the top).
Example 2: IPO / Maximize Capital (LeetCode 502)
Problem: You are starting a company with initial capital w. You can select at most k projects from a list. Each project i has a capital requirement capital[i] and a net profit profits[i]. You can only start a project if your current capital is at least its capital requirement. After completing a project, you keep the profit. Find the maximum final capital.
This problem uses Two Heaps in a completely different way -- not for medians, but for dynamically selecting the best available option.
function findMaximizedCapital(k, w, profits, capital) {
const n = profits.length;
// Min-heap of projects keyed by capital requirement (projects we can't afford yet)
const minCapitalHeap = new MinHeap((a, b) => a.capital - b.capital);
for (let i = 0; i < n; i++) {
minCapitalHeap.push({ capital: capital[i], profit: profits[i] });
}
// Max-heap of profits for projects we CAN afford
const maxProfitHeap = new MaxHeap((a, b) => a.profit - b.profit);
let currentCapital = w;
for (let i = 0; i < k; i++) {
// Move all affordable projects from minCapitalHeap to maxProfitHeap
while (minCapitalHeap.size() > 0 && minCapitalHeap.peek().capital <= currentCapital) {
maxProfitHeap.push(minCapitalHeap.pop());
}
// If no projects are affordable, we're done
if (maxProfitHeap.size() === 0) break;
// Pick the most profitable affordable project
currentCapital += maxProfitHeap.pop().profit;
}
return currentCapital;
}
// k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
// findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1]) -> 4
// Start with 0. Pick project 0 (capital 0, profit 1). Now have 1.
// Pick project 1 or 2 (capital 1, profit 2 or 3). Pick 2 (profit 3). Now have 4.
This is Two Heaps used for selection, not median tracking. The min-heap organizes projects by affordability threshold. The max-heap organizes affordable projects by profit. At each step, you transfer newly affordable projects from the min-heap to the max-heap, then pick the most profitable one. The two heaps work together like a funnel: the min-heap is the waiting room, the max-heap is the selection pool.
This problem teaches you that Two Heaps is not just about medians. It's about maintaining two collections with different ordering priorities and transferring elements between them as conditions change.
Spot the Pattern:
- "Design a class that supports adding numbers and finding the median of all numbers added so far."
- "Given a list of tasks with start times and durations, assign them to CPUs to minimize the number of CPUs used."
Answers: Problem 1 is Two Heaps (the classic). Problem 2 is Two Heaps combined with Merge Intervals -- use a min-heap to track CPU end times.
Pattern 10: Subsets
Tell-tale signs:
- You need all combinations, permutations, or subsets of a given set
- The input set may contain duplicates
- Keywords: "subsets," "permutations," "combinations," "letter case permutation," "generate parentheses," "all possible"
The Template (BFS approach):
function findSubsets(nums) {
const subsets = [[]]; // Start with empty set
for (const num of nums) {
const n = subsets.length;
for (let i = 0; i < n; i++) {
subsets.push([...subsets[i], num]);
}
}
return subsets;
}
The idea: start with the empty set. For each number, take every existing subset and create a new subset that includes the number. This generates all 2^N subsets.
Example 1: Permutations (LeetCode 46)
function permute(nums) {
const result = [];
function backtrack(current, used) {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
current.push(nums[i]);
backtrack(current, used);
current.pop();
used[i] = false;
}
}
backtrack([], new Array(nums.length).fill(false));
return result;
}
The backtracking skeleton: choose, explore, unchoose. The used array prevents reusing the same element. For permutations with duplicates, you'd sort first and skip consecutive identical elements.
Example 2: Generate Parentheses (LeetCode 22)
function generateParenthesis(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack('', 0, 0);
return result;
}
This is Subsets in disguise. Instead of choosing to include/exclude numbers, you choose to add '(' or ')' -- with constraints. The backtracking structure is identical.
Example 3: Subsets II (LeetCode 90)
Problem: Given an integer array that may contain duplicates, return all possible unique subsets. The solution set must not contain duplicate subsets.
This is the variant that tests whether you understand why the BFS approach works, not just the template.
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b); // Sort to group duplicates together
const subsets = [[]];
let startIndex = 0;
let endIndex = 0;
for (let i = 0; i < nums.length; i++) {
startIndex = 0;
// If current number is a duplicate, only add it to subsets
// that were created in the previous step (to avoid duplicates)
if (i > 0 && nums[i] === nums[i - 1]) {
startIndex = endIndex;
}
endIndex = subsets.length;
for (let j = startIndex; j < endIndex; j++) {
subsets.push([...subsets[j], nums[i]]);
}
}
return subsets;
}
// subsetsWithDup([1, 2, 2]) -> [[], [1], [2], [1,2], [2,2], [1,2,2]]
The key insight: when you encounter a duplicate number, you should only add it to the subsets that were created in the immediately previous step. If you add it to all existing subsets, you'll create duplicate subsets. The startIndex and endIndex variables track which subsets are "new" and eligible for the duplicate.
This is the kind of detail that separates pattern-matchers from memorizers. The BFS template is the same. The duplicate-handling logic is what you need to reason about in the interview.
Spot the Pattern:
- "Given a string, find all of its distinct permutations."
- "Given a set of distinct numbers, find all unique subsets. The solution set must not contain duplicate subsets."
Answers: Both are Subsets. Problem 1 is permutations with backtracking. Problem 2 is the classic subset generation -- but if the input has duplicates, you need to sort and skip.
Pattern 11: Modified Binary Search
Tell-tale signs:
- The input is sorted (or nearly sorted -- rotated, bitonic)
- You're searching for an element, a boundary, or a peak
- Keywords: "search in rotated sorted array," "find peak element," "search in bitonic array," "ceiling of a number," "next letter"
Standard binary search is easy. Modified binary search is where the Rs 1 Cr bar lives -- because it tests whether you understand why binary search works, not just the template.
The Template:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // Or left, if you're searching for an insertion point
}
The left + (right - left) / 2 formula avoids integer overflow. In JavaScript, Number.MAX_SAFE_INTEGER is large enough that overflow is unlikely, but it's a good habit for languages like Java and C++.
Example 1: Search in Rotated Sorted Array (LeetCode 33)
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) return mid;
// Check which half is sorted
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target is in left half
} else {
left = mid + 1; // Target is in right half
}
} else {
// Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target is in right half
} else {
right = mid - 1; // Target is in left half
}
}
}
return -1;
}
The key insight: in a rotated sorted array, at least one half is always sorted. Determine which half is sorted, check if the target falls in that half's range, and eliminate the other half. Same O(log N), same binary search skeleton -- just a more complex decision at each step.
Example 2: Find Peak Element (LeetCode 162)
function findPeakElement(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] > nums[mid + 1]) {
// We're on the descending slope -- peak is to the left (or at mid)
right = mid;
} else {
// We're on the ascending slope -- peak is to the right
left = mid + 1;
}
}
return left;
}
This is beautiful. You don't need to find the peak -- any peak works. By comparing nums[mid] with nums[mid + 1], you determine which direction is uphill and move that way. The array doesn't even need to be sorted -- you just need the guarantee that a peak exists (which it does, because nums[-1] = nums[n] = -Infinity).
Example 3: Search in a Sorted Infinite Array (LeetCode 702 -- variant)
Problem: You are given an infinite sorted array (or an array where you don't know the size) and a target. Find the index of the target, or return -1 if it doesn't exist. You cannot use arr.length.
This problem tests whether you understand the search space concept of binary search, not just the template. Since you don't know the right boundary, you need to find it first -- using exponential search.
function searchInfinite(arr, target) {
// Step 1: Find the search boundaries
let left = 0;
let right = 1;
// Exponentially expand right boundary until we pass the target
while (arr[right] !== undefined && arr[right] < target) {
left = right;
right *= 2;
}
// Step 2: Standard binary search within [left, right]
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
// Treat out-of-bounds as Infinity (target is to the left)
if (arr[mid] === undefined) {
right = mid - 1;
continue;
}
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Imagine arr = [1, 3, 5, 7, 9, 11, 13, 15, ...] (infinite)
// searchInfinite(arr, 7) -> 3
// Step 1: right goes 1 -> 2 -> 4 -> 8 (arr[8] = 17 > 7, stop)
// Step 2: binary search in [4, 8], find 7 at index 3
This is Modified Binary Search applied to the setup phase, not the search itself. The core binary search is standard. The modification is in how you establish the search boundaries. This pattern -- exponential expansion followed by binary search -- appears in problems involving unknown-size datasets, stream processing, and system design (like finding the right shard in a distributed key-value store).
Spot the Pattern:
- "Given a sorted array of numbers, find the range of indices where a given target appears."
- "Given a bitonic array (increasing then decreasing), find the maximum element."
Answers: Both are Modified Binary Search. Problem 1 runs binary search twice -- once for the first occurrence, once for the last. Problem 2 is essentially Find Peak Element on a bitonic array.
Pattern 12: Top K Elements
Tell-tale signs:
- You need the K largest, K smallest, K most frequent, or K closest elements
- Sorting the entire input is unnecessary or too expensive
- Keywords: "top K," "K largest," "K smallest," "K most frequent," "K closest," "Kth largest"
The Template:
function topKElements(nums, k) {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // Remove smallest -- keep only K largest
}
}
return minHeap.toArray(); // The K largest elements
}
The trick: use a min-heap of size K to track the K largest elements. When the heap exceeds size K, pop the smallest. After processing all elements, the heap contains the K largest. Time: O(N log K) instead of O(N log N) for full sort.
Example 1: K Most Frequent Elements (LeetCode 347)
function topKFrequent(nums, k) {
// Step 1: Build frequency map
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// Step 2: Min-heap of size K, keyed by frequency
const minHeap = new MinHeap((a, b) => freq.get(a) - freq.get(b));
for (const num of freq.keys()) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.toArray();
}
Two steps: count frequencies, then find the K most frequent using a min-heap. The heap comparator uses frequency, not the number itself.
Example 2: Kth Largest Element in an Array (LeetCode 215)
function findKthLargest(nums, k) {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.peek(); // The Kth largest is the smallest in the heap
}
After processing all elements, the min-heap contains the K largest elements. The smallest among them is the Kth largest. This is O(N log K) -- better than sorting's O(N log N) when K << N.
Example 3: K Closest Points to Origin (LeetCode 973)
Problem: Given an array of points on a 2D plane, find the K closest points to the origin (0, 0). The distance is Euclidean distance.
This problem tests whether you can adapt the Top K pattern to a custom ordering criterion.
function kClosest(points, k) {
// Max-heap of size K, keyed by distance (keep K closest = K smallest distances)
// Use a max-heap so we can pop the farthest among the K closest
const maxHeap = new MaxHeap((a, b) => a.dist - b.dist);
for (const [x, y] of points) {
const dist = x * x + y * y; // No need for sqrt -- comparison is the same
maxHeap.push({ point: [x, y], dist });
if (maxHeap.size() > k) {
maxHeap.pop(); // Remove the farthest among the K closest
}
}
return maxHeap.toArray().map(item => item.point);
}
// kClosest([[1,3],[-2,2],[5,8],[0,1]], 2) -> [[-2,2], [0,1]] or [[0,1], [-2,2]]
The decision: use a max-heap (not min-heap) when you want the K smallest elements. Why? Because you want to evict the largest among your K candidates. When the heap exceeds size K, you pop the maximum (the farthest point), leaving the K closest. This is the inverse of the K largest problem, and it's the most common mistake engineers make with this pattern -- using the wrong heap type.
Also note: you compare squared distances (x*x + y*y), not actual Euclidean distances. The square root is monotonic, so it doesn't change the ordering, and you save a Math.sqrt() call per point. This is the kind of micro-optimization that shows the interviewer you think about constant factors.
Spot the Pattern:
- "Given an array of points on a 2D plane, find the K closest points to the origin."
- "Given a string, sort characters by frequency in decreasing order."
Answers: Problem 1 is Top K Elements (use a max-heap of size K, keyed by distance -- or a min-heap and keep K largest distances, then reverse). Problem 2 is Top K Elements combined with a frequency map.
Pattern 13: K-way Merge
Tell-tale signs:
- You have K sorted arrays, lists, or streams
- You need to merge them into a single sorted result
- Keywords: "merge K sorted lists," "Kth smallest in sorted matrix," "smallest range covering elements from K lists"
The Template:
function mergeKSortedLists(lists) {
const minHeap = new MinHeap((a, b) => a.val - b.val);
// Seed heap with the first element of each list
for (const list of lists) {
if (list) minHeap.push(list);
}
const dummy = { next: null, val: 0 };
let tail = dummy;
while (minHeap.size() > 0) {
const smallest = minHeap.pop();
tail.next = smallest;
tail = tail.next;
if (smallest.next) {
minHeap.push(smallest.next);
}
}
return dummy.next;
}
The algorithm: put the head of each list into a min-heap. Pop the smallest, add it to the result, then push the next node from that list into the heap. Repeat until the heap is empty. O(N log K) where N is total elements and K is number of lists.
Example 1: Kth Smallest Element in a Sorted Matrix (LeetCode 378)
function kthSmallest(matrix, k) {
const n = matrix.length;
const minHeap = new MinHeap((a, b) => a.val - b.val);
// Seed with first element of each row
for (let i = 0; i < Math.min(n, k); i++) {
minHeap.push({ val: matrix[i][0], row: i, col: 0 });
}
let count = 0;
while (minHeap.size() > 0) {
const { val, row, col } = minHeap.pop();
count++;
if (count === k) return val;
if (col + 1 < n) {
minHeap.push({ val: matrix[row][col + 1], row, col: col + 1 });
}
}
return -1;
}
Each row is sorted. We treat each row as a sorted list and K-way merge them. The Kth element popped is the answer. This is O(K log N) -- far better than flattening and sorting the entire matrix.
Example 2: Smallest Range Covering Elements from K Lists (LeetCode 632)
Problem: You have K lists of sorted integers. Find the smallest range [a, b] that includes at least one number from each of the K lists. If multiple ranges have the same length, return the one with the smallest a.
This is the K-way Merge problem that appears in Principal-level interviews. It tests whether you can maintain additional state (the current maximum) alongside the min-heap.
function smallestRange(nums) {
const minHeap = new MinHeap((a, b) => a.val - b.val);
let currentMax = -Infinity;
let rangeStart = 0;
let rangeEnd = Infinity;
// Seed heap with first element of each list; track the max among them
for (let i = 0; i < nums.length; i++) {
minHeap.push({ val: nums[i][0], list: i, idx: 0 });
currentMax = Math.max(currentMax, nums[i][0]);
}
while (minHeap.size() === nums.length) {
const { val, list, idx } = minHeap.pop();
// Check if current range [val, currentMax] is smaller
if (currentMax - val < rangeEnd - rangeStart) {
rangeStart = val;
rangeEnd = currentMax;
}
// Push next element from the same list
if (idx + 1 < nums[list].length) {
const nextVal = nums[list][idx + 1];
minHeap.push({ val: nextVal, list, idx: idx + 1 });
currentMax = Math.max(currentMax, nextVal);
}
}
return [rangeStart, rangeEnd];
}
// nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
// smallestRange(nums) -> [20, 24]
// Range [20,24] contains 24 from list 0, 20 from list 1, 22 from list 2
The algorithm: maintain a min-heap with one element from each list. The current range is [minHeap.peek().val, currentMax]. At each step, pop the minimum, update the range if it's smaller, and push the next element from the same list. The loop continues as long as all K lists are represented in the heap (when one list is exhausted, we can't cover all K lists anymore).
This is K-way Merge with a twist: instead of building a merged output, you're tracking the span between the current minimum and maximum across all lists. The min-heap gives you the minimum in O(log K). The currentMax variable tracks the maximum. The range is the difference between them. Same heap mechanics, different objective.
Spot the Pattern:
- "You are given K lists of sorted integers. Find the smallest range that includes at least one number from each of the K lists."
- "Merge K sorted linked lists and return it as one sorted list."
Answers: Both are K-way Merge. Problem 1 uses a min-heap to track the current minimum across all lists and a variable for the current maximum, shrinking the range as you go.
Pattern 14: Topological Sort
Tell-tale signs:
- You have a set of tasks with dependencies (A must come before B)
- You need to find a valid ordering, or detect if one exists
- Keywords: "course schedule," "task scheduling," "prerequisites," "build order," "dependency resolution," "alien dictionary"
This is the pattern that shows up in every staff-level interview. It's not hard -- but it requires you to think in graphs, and most Node.js engineers don't practice graph algorithms enough.
The Template:
function topologicalSort(vertices, edges) {
// 1. Build graph and in-degree map
const graph = new Map();
const inDegree = new Map();
for (let i = 0; i < vertices; i++) {
graph.set(i, []);
inDegree.set(i, 0);
}
for (const [parent, child] of edges) {
graph.get(parent).push(child);
inDegree.set(child, inDegree.get(child) + 1);
}
// 2. Find all sources (in-degree = 0)
const sources = [];
for (const [vertex, degree] of inDegree) {
if (degree === 0) sources.push(vertex);
}
// 3. Process sources, reducing in-degrees
const sortedOrder = [];
while (sources.length > 0) {
const vertex = sources.shift();
sortedOrder.push(vertex);
for (const child of graph.get(vertex)) {
inDegree.set(child, inDegree.get(child) - 1);
if (inDegree.get(child) === 0) {
sources.push(child);
}
}
}
// 4. Cycle detection
if (sortedOrder.length !== vertices) {
return []; // Cycle exists -- no valid ordering
}
return sortedOrder;
}
The algorithm: repeatedly remove nodes with no incoming edges (sources). Each removal may create new sources. If you can't remove all nodes, there's a cycle.
Example 1: Course Schedule (LeetCode 207)
Problem: There are N courses labeled 0 to N-1. Some courses have prerequisites. Determine if you can finish all courses.
function canFinish(numCourses, prerequisites) {
const sorted = topologicalSort(numCourses, prerequisites);
return sorted.length === numCourses;
}
That's it. The topological sort either produces a valid ordering (all courses can be finished) or detects a cycle (impossible). The entire problem reduces to one function call.
Example 2: Alien Dictionary (LeetCode 269)
Problem: Given a sorted dictionary of an alien language, find the order of characters.
function alienOrder(words) {
// Build graph from adjacent word pairs
const graph = new Map();
const inDegree = new Map();
// Initialize all unique characters
for (const word of words) {
for (const char of word) {
if (!graph.has(char)) {
graph.set(char, []);
inDegree.set(char, 0);
}
}
}
// Compare adjacent words to find ordering
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i];
const w2 = words[i + 1];
// Invalid case: prefix word comes after longer word
if (w1.length > w2.length && w1.startsWith(w2)) return '';
for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
if (w1[j] !== w2[j]) {
graph.get(w1[j]).push(w2[j]);
inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
break; // Only the first differing character gives ordering info
}
}
}
// Topological sort
const sources = [];
for (const [char, degree] of inDegree) {
if (degree === 0) sources.push(char);
}
let result = '';
while (sources.length > 0) {
const char = sources.shift();
result += char;
for (const child of graph.get(char)) {
inDegree.set(child, inDegree.get(child) - 1);
if (inDegree.get(child) === 0) sources.push(child);
}
}
return result.length === graph.size ? result : '';
}
This is the problem that separates pattern-matchers from memorizers. The memorizer sees "alien dictionary" and panics -- it's not a standard LeetCode problem they've drilled. The pattern-matcher sees "ordering from pairwise comparisons" and thinks "Topological Sort." The graph construction is the only novel part. The sort itself is the same template.
Example 3: Course Schedule II (LeetCode 210)
Problem: Same as Course Schedule, but return the actual ordering of courses. If there are multiple valid orderings, return any.
function findOrder(numCourses, prerequisites) {
// Build graph and in-degree map
const graph = new Map();
const inDegree = new Map();
for (let i = 0; i < numCourses; i++) {
graph.set(i, []);
inDegree.set(i, 0);
}
for (const [course, prereq] of prerequisites) {
graph.get(prereq).push(course);
inDegree.set(course, inDegree.get(course) + 1);
}
// Find all courses with no prerequisites
const queue = [];
for (const [course, degree] of inDegree) {
if (degree === 0) queue.push(course);
}
const order = [];
while (queue.length > 0) {
const course = queue.shift();
order.push(course);
for (const next of graph.get(course)) {
inDegree.set(next, inDegree.get(next) - 1);
if (inDegree.get(next) === 0) {
queue.push(next);
}
}
}
return order.length === numCourses ? order : [];
}
// numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
// findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) -> [0, 1, 2, 3] or [0, 2, 1, 3]
This is the same template as Course Schedule I, but instead of returning a boolean, you return the order array. The topological sort algorithm naturally produces a valid ordering -- you just need to collect it. The only difference between "can I finish?" and "in what order?" is whether you return a boolean or an array. Same pattern, different output.
Spot the Pattern:
- "You are given a list of projects and a list of dependencies. Find a build order that allows all projects to be built."
- "Given a directed graph, determine if it contains a cycle."
Answers: Both are Topological Sort. Problem 1 is the classic application. Problem 2 is the cycle-detection variant -- if the topological sort doesn't include all vertices, there's a cycle.
Pattern Recognition Drill
Knowing the 14 patterns is one thing. Recognizing them cold, under interview pressure, is another. This drill is designed to build that reflex. For each problem below, read the description and identify the pattern in three seconds. Don't solve it. Just name the pattern. Then check the answer.
Problem 1: You are given an array of integers and an integer K. Find the maximum sum of any contiguous subarray of size K.
Problem 2: You are given a linked list. Determine if it has a cycle. If it does, return the node where the cycle begins.
Problem 3: You are given a list of meeting time intervals. Determine the minimum number of conference rooms required to hold all meetings without conflicts.
Problem 4: You are given an unsorted array containing N numbers taken from the range 1 to N. Exactly one number is missing. Find it in O(N) time and O(1) space.
Problem 5: You are given a binary tree. Return the values of nodes visible from the right side when looking at the tree from the right.
Problem 6: You are given a stream of numbers. At any point, you need to be able to return the median of all numbers seen so far.
Problem 7: You are given a set of distinct integers. Return all possible subsets (the power set).
Problem 8: You are given a sorted array that has been rotated at an unknown pivot. Search for a target value in O(log N) time.
Problem 9: You are given K sorted linked lists. Merge them into a single sorted linked list.
Problem 10: You are given N courses labeled 0 to N-1 and a list of prerequisites where [a, b] means you must take course b before course a. Determine if it is possible to finish all courses.
Answers:
Problem 1: Sliding Window. The tell-tale sign is "contiguous subarray of size K." Fixed-size window. The word "contiguous" is the dead giveaway. You slide a window of size K across the array, maintaining the sum, and track the maximum.
Problem 2: Fast & Slow Pointers. The tell-tale sign is "linked list" + "cycle." This is the classic use case. Fast pointer moves two steps, slow moves one. If they meet, there's a cycle. Phase 2 finds the cycle start by resetting one pointer to head and moving both at the same speed.
Problem 3: Merge Intervals. The tell-tale sign is "meeting time intervals" + "minimum number of rooms." This is Meeting Rooms II -- the canonical Merge Intervals problem. Sort start and end times separately, then use a two-pointer approach to count concurrent meetings.
Problem 4: Cyclic Sort. The tell-tale sign is "numbers from 1 to N" + "find missing" + "O(N) time, O(1) space." The range is known and contiguous. You can place each number at its correct index in O(N) without comparisons. After sorting, the index where the number doesn't match is the answer.
Problem 5: Tree BFS. The tell-tale sign is "binary tree" + "right side view" + "level." This is level-order traversal where you collect only the last node of each level. BFS with a queue and levelSize tracking is the natural approach.
Problem 6: Two Heaps. The tell-tale sign is "stream of numbers" + "median." This is the canonical Two Heaps problem. A max-heap holds the smaller half, a min-heap holds the larger half. The median is either the top of the max-heap (odd count) or the average of both tops (even count).
Problem 7: Subsets. The tell-tale sign is "all possible subsets" + "power set." This is the classic Subsets pattern. Use the BFS approach (start with empty set, for each number, add it to all existing subsets) or backtracking.
Problem 8: Modified Binary Search. The tell-tale sign is "sorted array" + "rotated" + "O(log N)." Standard binary search doesn't work because the array isn't fully sorted. But at each step, one half is guaranteed to be sorted. Determine which half, check if the target is in its range, and eliminate the other half.
Problem 9: K-way Merge. The tell-tale sign is "K sorted linked lists" + "merge into single sorted list." Put the head of each list into a min-heap. Repeatedly pop the smallest, add it to the result, and push the next node from that list. O(N log K).
Problem 10: Topological Sort. The tell-tale sign is "courses" + "prerequisites" + "determine if possible." This is a dependency graph. If there's a cycle, it's impossible. Topological sort detects cycles: if the sorted order doesn't include all vertices, a cycle exists.
Pattern Composition: When One Pattern Isn't Enough
The problems that appear in Staff and Principal-level interviews rarely use a single pattern in isolation. They combine two patterns -- and the real test is whether you can decompose the problem into its constituent parts and apply each pattern at the right time.
Here are two problems that require pattern composition. These are the problems that separate the Rs 60 LPA candidates from the Rs 1 Cr candidates.
Composition 1: Sliding Window + Hash Map -- Minimum Window Substring (LeetCode 76)
Problem: Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string.
Why two patterns?
At first glance, this is a Sliding Window problem -- and it is. You expand the right pointer to include characters, and shrink the left pointer when all required characters are satisfied. But the constraint checking is non-trivial. You can't just count distinct characters. You need to know whether the current window contains at least the required frequency of each character in t. That's where the Hash Map pattern comes in.
The Hash Map is not just a data structure here -- it's a pattern for tracking multi-dimensional constraints. You maintain two maps: need (what characters and frequencies t requires) and have (what the current window contains). The matched counter tracks how many characters have fully satisfied their required frequency. This lets you check the constraint in O(1) instead of scanning both maps every time.
Full solution:
function minWindow(s, t) {
if (t.length > s.length) return '';
// Hash Map: track required character frequencies
const need = new Map();
for (const char of t) {
need.set(char, (need.get(char) || 0) + 1);
}
const have = new Map();
let windowStart = 0;
let minStart = 0;
let minLen = Infinity;
let matched = 0; // Characters with fully satisfied frequency
// Sliding Window
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const rightChar = s[windowEnd];
// Hash Map: update "have" state
if (need.has(rightChar)) {
have.set(rightChar, (have.get(rightChar) || 0) + 1);
if (have.get(rightChar) === need.get(rightChar)) {
matched++;
}
}
// Sliding Window: shrink when constraint is satisfied
while (matched === need.size) {
const windowLen = windowEnd - windowStart + 1;
if (windowLen < minLen) {
minLen = windowLen;
minStart = windowStart;
}
const leftChar = s[windowStart];
if (need.has(leftChar)) {
if (have.get(leftChar) === need.get(leftChar)) {
matched--;
}
have.set(leftChar, have.get(leftChar) - 1);
}
windowStart++;
}
}
return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}
// minWindow("ADOBECODEBANC", "ABC") -> "BANC"
How the patterns interact:
The Sliding Window controls the structure: expand right, shrink left, track the minimum. The Hash Map controls the constraint: what does "valid window" mean, and how do we check it efficiently? The matched counter is the bridge between them -- it translates the multi-dimensional map state into a single boolean condition (matched === need.size) that the sliding window can use.
If you try to solve this with Sliding Window alone, you'll end up scanning the entire need map on every iteration to check validity -- O(N * M) instead of O(N + M). If you try to solve it with Hash Map alone, you won't have the two-pointer structure to find the minimum window. You need both.
Composition 2: Topological Sort + BFS -- Parallel Courses (LeetCode 1136)
Problem: You are given an integer N representing the number of courses, and a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. In one semester, you can take any number of courses as long as all their prerequisites are satisfied. Return the minimum number of semesters required to complete all courses. If it's impossible, return -1.
Why two patterns?
Topological Sort gives you the ordering -- which courses depend on which. But the question asks for the minimum number of semesters (levels), not the order itself. This is where BFS comes in. The topological sort already processes nodes level by level (sources, then their children, then grandchildren). If you process it in BFS layers -- where each layer is one semester -- the number of layers is your answer.
The Topological Sort handles the dependency resolution and cycle detection. The BFS layer tracking handles the semester counting. Together, they solve a problem that neither pattern can solve alone.
Full solution:
function minimumSemesters(n, relations) {
// Topological Sort: build graph and in-degree map
const graph = new Map();
const inDegree = new Map();
for (let i = 1; i <= n; i++) {
graph.set(i, []);
inDegree.set(i, 0);
}
for (const [prereq, course] of relations) {
graph.get(prereq).push(course);
inDegree.set(course, inDegree.get(course) + 1);
}
// BFS: start with all courses that have no prerequisites (semester 1)
const queue = [];
for (const [course, degree] of inDegree) {
if (degree === 0) queue.push(course);
}
let semesters = 0;
let coursesTaken = 0;
// BFS level-by-level: each level = one semester
while (queue.length > 0) {
const levelSize = queue.length; // Courses available this semester
for (let i = 0; i < levelSize; i++) {
const course = queue.shift();
coursesTaken++;
for (const next of graph.get(course)) {
inDegree.set(next, inDegree.get(next) - 1);
if (inDegree.get(next) === 0) {
queue.push(next); // Available next semester
}
}
}
semesters++;
}
// Topological Sort: cycle detection
return coursesTaken === n ? semesters : -1;
}
// n = 3, relations = [[1,3],[2,3]]
// minimumSemesters(3, [[1,3],[2,3]]) -> 2
// Semester 1: take courses 1 and 2 (no prerequisites)
// Semester 2: take course 3 (prerequisites 1 and 2 are done)
How the patterns interact:
The Topological Sort provides the graph structure, the in-degree tracking, and the cycle detection (coursesTaken === n). The BFS provides the level-by-level processing: levelSize captures how many courses are available in the current semester, and each iteration of the outer while loop is one semester. The queue serves double duty -- it's both the sources list for topological sort and the BFS queue.
Notice the levelSize variable. This is the same BFS pattern from Tree BFS (Pattern 7), applied to a graph instead of a tree. The principle is identical: capture the queue length before processing the level, process exactly that many nodes, and increment the level counter. The only difference is that the "children" come from the adjacency list instead of node.left and node.right.
This problem is a perfect example of why pattern composition matters. If you only know Topological Sort, you can return the order but not the semester count. If you only know BFS, you can count levels but can't handle the dependency constraints. Together, they solve the problem cleanly in O(V + E) time.
How to Practice: The Pattern-First Method
Knowing the 14 patterns is step one. Building the reflex is step two. Here's the system that works.
Week 1-2: Pattern Isolation. Pick one pattern per day. Solve 5 problems that use that pattern. Don't mix patterns. Your goal is to see the same skeleton in five different costumes. By problem five, you should be able to write the template from memory and only think about the problem-specific logic.
Week 3-4: Pattern Mixing. Solve 3 problems per day from random patterns. Before you write a single line of code, say out loud: "This is [Pattern Name] because [tell-tale sign]." If you can't name the pattern in three seconds, you haven't internalized it yet. Go back to isolation for that pattern.
Week 5-6: Pattern Composition. The hardest interview problems combine two patterns. Triplet Sum to Zero = Sorting + Two Pointers. Sliding Window Median = Sliding Window + Two Heaps. Alien Dictionary = Graph Construction + Topological Sort. Solve 2-3 composition problems per day. For each one, identify both patterns before coding.
Week 7-8: Mock Interview Speed. Have a friend give you random LeetCode mediums. You have 25 minutes per problem. The three-second rule applies: name the pattern immediately, then code. Record yourself. Watch the recordings. Notice where you hesitate. Drill those patterns.
This is not a "solve 500 problems" plan. It's a "master 14 patterns" plan. The engineer who has truly internalized 14 patterns will outperform the engineer who has superficially solved 300 problems. Every time.
Priya, a backend engineer at a Pune-based SaaS company, followed exactly this system. She had 4.5 years of experience, mostly building REST APIs in Node.js. Her DSA was rusty -- she hadn't touched a binary tree since college. She spent 8 weeks on this plan: 2 weeks per phase, 2-3 hours per day after work. She solved roughly 120 problems total. But she solved them differently -- each one reinforced a pattern, not a standalone trick.
She interviewed at Microsoft India (Noida) for an SDE-2 role. The interviewer gave her a problem about finding the shortest subarray with a sum greater than K. She recognized it as Sliding Window within five seconds. She wrote the template, adapted the constraint, handled the edge case where no such subarray exists, and discussed the time complexity. The interviewer nodded and moved to the next question.
She got the offer. Rs 62 LPA. Not because she solved more problems than the other candidates. Because she solved them faster and with confidence -- and confidence comes from knowing the pattern before you write the first line.
The Pattern Cheat Sheet
Print this. Stick it on your wall. When you're solving a problem and you're stuck, look at this list and ask: which bucket does this fall into?
| Pattern | Tell-Tale Sign | Template Complexity |
|---|---|---|
| Sliding Window | "contiguous subarray/substring" + constraint | O(N) |
| Two Pointers | Sorted array, pairs/triplets | O(N) |
| Fast & Slow Pointers | Linked list, cycle/middle | O(N) |
| Merge Intervals | Overlapping intervals | O(N log N) |
| Cyclic Sort | Numbers 1 to N, missing/duplicate | O(N) |
| In-place Reversal | Reverse linked list/sublist | O(N) |
| Tree BFS | Level-order, shortest path | O(N) |
| Tree DFS | Path sum, LCA, diameter | O(N) |
| Two Heaps | Median of stream | O(log N) per op |
| Subsets | Permutations, combinations | O(2^N) |
| Modified Binary Search | Sorted/rotated array search | O(log N) |
| Top K Elements | K largest/frequent/closest | O(N log K) |
| K-way Merge | Merge K sorted lists | O(N log K) |
| Topological Sort | Task scheduling, dependencies | O(V + E) |
The Interview Day Playbook
When you're in the interview and the problem lands, here's your sequence:
-
Read the problem twice. The first read is for comprehension. The second read is for pattern detection. Look for the tell-tale keywords.
-
Name the pattern out loud. "This looks like a Sliding Window problem because we're looking for a contiguous subarray with a constraint." This shows the interviewer you're thinking structurally, not guessing.
-
State the time complexity you're targeting. "With Sliding Window, we can do this in O(N) time and O(1) space." This sets expectations and shows you understand the tradeoffs.
-
Write the template from memory. Don't think about the problem yet. Just write the skeleton. Get the loop structure, the pointers, the invariants on the screen.
-
Adapt the template to the problem. Now add the problem-specific logic: the constraint check, the result update, the edge cases.
-
Walk through a test case. Use the example input. Trace your code line by line. Catch bugs before the interviewer does.
-
Discuss edge cases. Empty input. Single element. All identical values. What happens at the boundaries? Show you've thought about it.
This sequence works because it separates structure from adaptation. You're not trying to invent an algorithm from scratch. You're recognizing a pattern and customizing it. That's what the interviewer wants to see.
DSA gets you the interview. System Design gets you the offer. And that's where most Node.js engineers fall apart completely -- not because they can't design systems, but because they've never been asked to think at the scale of millions of users. The next chapter fixes that.