function maxSumFixedWindow(arr, k) { if (arr.length < k) return null; // Calculate first window sum let windowSum = 0; for (let i = 0; i < k; i++) { windowSum += arr[i]; } let maxSum = windowSum; // Slide window: add next, remove first for (let i = k; i < arr.length; i++) { windowSum += arr[i] - arr[i - k]; maxSum = Math.max(maxSum, windowSum); } return maxSum;}// Example usageconst arr = [2, 1, 5, 1, 3, 2];console.log(maxSumFixedWindow(arr, 3)); // Output: 9 (5+1+3)
1.2 Variable-size Window Optimization
Pattern
Strategy
When to Use
Complexity
Expand-Shrink
Expand right until condition fails, then shrink left
Find smallest/largest window meeting criteria
O(n)
Two Pointer
Left and right pointers move independently
Subarray sum equals target, substring problems
O(n)
HashMap Tracking
Track frequency/count in current window
Distinct elements, character frequency
O(n)
Condition Check
Validate window on each expansion/shrink
Complex constraints validation
O(n)
Example: Smallest subarray with sum ≥ target
function minSubArrayLen(target, nums) { let left = 0, sum = 0; let minLen = Infinity; for (let right = 0; right < nums.length; right++) { sum += nums[right]; // Expand window // Shrink window while condition met while (sum >= target) { minLen = Math.min(minLen, right - left + 1); sum -= nums[left]; left++; } } return minLen === Infinity ? 0 : minLen;}// Exampleconsole.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2 ([4,3])
1.3 Maximum/Minimum Subarray Problems
Problem Type
Approach
Data Structure
Example
Max Sum Subarray
Kadane's algorithm or sliding window
Variables for current/max sum
Maximum profit, maximum subarray sum
Min/Max in Window
Monotonic deque
Deque storing indices
Sliding window maximum/minimum
Product Maximum
Track both max and min (negative numbers)
Two variables for max/min product
Maximum product subarray
Fixed Length Max
Fixed window with running max/min
Window sum + comparison
Max average subarray of length k
Example: Sliding Window Maximum
function maxSlidingWindow(nums, k) { const result = []; const deque = []; // Store indices for (let i = 0; i < nums.length; i++) { // Remove indices outside window while (deque.length && deque[0] <= i - k) { deque.shift(); } // Remove smaller elements while (deque.length && nums[deque[deque.length-1]] < nums[i]) { deque.pop(); } deque.push(i); if (i >= k - 1) { result.push(nums[deque[0]]); } } return result;}
Example: Maximum Product Subarray
function maxProduct(nums) { let maxProd = nums[0]; let curMax = nums[0]; let curMin = nums[0]; for (let i = 1; i < nums.length; i++) { const num = nums[i]; // Swap if negative if (num < 0) { [curMax, curMin] = [curMin, curMax]; } curMax = Math.max(num, curMax * num); curMin = Math.min(num, curMin * num); maxProd = Math.max(maxProd, curMax); } return maxProd;}
1.4 Longest Substring/Sequence Patterns
Pattern
Key Technique
Tracking Method
Common Problems
Unique Characters
HashMap/Set for character tracking
Store last seen index of each character
Longest substring without repeating chars
K Distinct Elements
Expand until k+1 distinct, then shrink
HashMap with character frequency
Longest substring with k distinct chars
Character Replacement
Track most frequent + replacement count
Frequency map + max frequency variable
Longest repeating char replacement
Anagram Window
Character frequency matching
Two frequency maps comparison
Find all anagrams in string
Example: Longest substring without repeating characters
function lengthOfLongestSubstring(s) { const charMap = new Map(); let left = 0, maxLen = 0; for (let right = 0; right < s.length; right++) { const char = s[right]; // If duplicate found, move left pointer if (charMap.has(char)) { left = Math.max(left, charMap.get(char) + 1); } charMap.set(char, right); maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}// Exampleconsole.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3 ("abc")
Example: Longest substring with k distinct characters
function lengthOfLongestSubstringKDistinct(s, k) { const charCount = new Map(); let left = 0, maxLen = 0; for (let right = 0; right < s.length; right++) { const char = s[right]; charCount.set(char, (charCount.get(char) || 0) + 1); // Shrink window if more than k distinct while (charCount.size > k) { const leftChar = s[left]; charCount.set(leftChar, charCount.get(leftChar) - 1); if (charCount.get(leftChar) === 0) { charCount.delete(leftChar); } left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}
1.5 Two-pointer Sliding Window Hybrid
Variant
Pointer Movement
Use Case
Key Insight
Same Direction
Both pointers move left to right
Variable window size problems
Window expands/shrinks dynamically
Opposite Direction
Left moves right, right moves left
Palindrome check, two sum in sorted array
Converge towards middle or target
Fast-Slow Pattern
One pointer moves faster than other
Cycle detection, middle element
Speed differential reveals patterns
Partitioning
One pointer scans, other marks boundary
Dutch national flag, partition array
Maintain invariant between pointers
Example: Container with most water (opposite direction)
function maxArea(height) { let left = 0, right = height.length - 1; let maxArea = 0; while (left < right) { const width = right - left; const minHeight = Math.min(height[left], height[right]); const area = width * minHeight; maxArea = Math.max(maxArea, area); // Move pointer with smaller height if (height[left] < height[right]) { left++; } else { right--; } } return maxArea;}
1.6 Time Complexity Analysis O(n)
Aspect
Analysis
Explanation
Single Pass
O(n)
Each element visited at most once by right pointer
Left Pointer Movement
O(n) total
Left pointer moves at most n times across entire execution
Combined Movement
O(2n) = O(n)
Both pointers together traverse array once
Space Complexity
O(1) to O(k)
O(1) for counters, O(k) for HashMap with k unique elements
Note: Sliding window achieves O(n) time by ensuring each element is processed at most twice - once when entering window (right pointer) and once when leaving (left pointer). This is superior to naive nested loops O(n²).
Sliding Window Pattern Summary
Fixed Window: Calculate initial sum, slide by adding/removing elements
Variable Window: Expand until condition breaks, shrink until valid
Template: Use HashMap for tracking, two pointers for boundaries
Optimization: Amortized O(n) - each element touched maximum twice
Common Mistakes: Off-by-one errors, not updating window state correctly
Warning: Always verify window validity before updating result. Ensure left pointer doesn't exceed right pointer. Handle edge cases: empty array, k > array length, negative numbers in product problems.
2. Two Pointers
2.1 Opposite Ends Technique
Pattern
Initialization
Movement Rule
Use Case
Two Sum Sorted
left = 0, right = n-1
Move left if sum too small, right if too large
Find pair with target sum in sorted array
Palindrome Check
left = 0, right = n-1
Move both inward while characters match
Verify if string is palindrome
Container Most Water
left = 0, right = n-1
Move pointer with smaller height
Maximize area between two vertical lines
Reverse Array
left = 0, right = n-1
Swap and move both pointers inward
In-place array reversal
Example: Two sum in sorted array
function twoSum(numbers, target) { let left = 0; let right = numbers.length - 1; while (left < right) { const sum = numbers[left] + numbers[right]; if (sum === target) { return [left, right]; // or [left+1, right+1] for 1-indexed } else if (sum < target) { left++; // Need larger sum } else { right--; // Need smaller sum } } return [-1, -1]; // Not found}// Exampleconsole.log(twoSum([2, 7, 11, 15], 9)); // Output: [0, 1]
Example: Valid palindrome
function isPalindrome(s) { // Normalize: remove non-alphanumeric, lowercase s = s.toLowerCase().replace(/[^a-z0-9]/g, ''); let left = 0; let right = s.length - 1; while (left < right) { if (s[left] !== s[right]) { return false; } left++; right--; } return true;}// Exampleconsole.log(isPalindrome("A man, a plan, a canal: Panama")); // Output: true
2.2 Fast and Slow Pointers
Pattern
Speed Ratio
Detection
Application
Cycle Detection
Slow: +1, Fast: +2
Fast meets slow inside cycle
Detect loop in linked list (Floyd's algorithm)
Middle Element
Slow: +1, Fast: +2
When fast reaches end, slow at middle
Find middle node of linked list
Cycle Start
Reset one pointer to head after meeting
Both move at same speed, meet at cycle start
Find beginning of cycle in linked list
Happy Number
Fast computes twice per iteration
Converge to 1 or detect cycle
Determine if number is happy number
Example: Detect cycle in linked list
function hasCycle(head) { if (!head || !head.next) return false; let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; // Move 1 step fast = fast.next.next; // Move 2 steps if (slow === fast) { return true; // Cycle detected } } return false; // No cycle}
Example: Find middle of linked list
function middleNode(head) { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } // When fast reaches end, // slow is at middle return slow;}// For even length, returns // second middle node
Example: Find cycle start position
function detectCycle(head) { let slow = head, fast = head; // Phase 1: Detect if cycle exists while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { // Phase 2: Find cycle start slow = head; while (slow !== fast) { slow = slow.next; fast = fast.next; } return slow; // Cycle start } } return null; // No cycle}
2.3 In-place Array Manipulation
Technique
Pointer Strategy
Space
Common Problem
Remove Duplicates
Slow tracks unique position, fast scans
O(1)
Remove duplicates from sorted array
Move Zeros
Slow marks non-zero position, fast scans
O(1)
Move all zeros to end of array
Remove Element
Write pointer for valid elements
O(1)
Remove all instances of target value
Squares Sorted Array
Compare from both ends, fill from back
O(n)
Square sorted array with negatives
Example: Remove duplicates from sorted array
function removeDuplicates(nums) { if (nums.length === 0) return 0; let slow = 0; // Position for next unique for (let fast = 1; fast < nums.length; fast++) { if (nums[fast] !== nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; // New length}// [1,1,2,2,3] -> [1,2,3,_,_], return 3
Example: Move zeros to end
function moveZeroes(nums) { let slow = 0; // Next non-zero position // Move all non-zeros forward for (let fast = 0; fast < nums.length; fast++) { if (nums[fast] !== 0) { nums[slow] = nums[fast]; slow++; } } // Fill remaining with zeros while (slow < nums.length) { nums[slow] = 0; slow++; }}
Example: Sorted squares with negative numbers
function sortedSquares(nums) { const n = nums.length; const result = new Array(n); let left = 0, right = n - 1; let pos = n - 1; // Fill from back while (left <= right) { const leftSquare = nums[left] * nums[left]; const rightSquare = nums[right] * nums[right]; if (leftSquare > rightSquare) { result[pos] = leftSquare; left++; } else { result[pos] = rightSquare; right--; } pos--; } return result;}// [-4,-1,0,3,10] -> [0,1,9,16,100]
2.4 Partitioning and Sorting
Algorithm
Invariant
Partitions
Use Case
Dutch National Flag
[0..low-1]=0, [high+1..n-1]=2
Three partitions: 0s, 1s, 2s
Sort array with 3 distinct values
QuickSort Partition
Elements < pivot left, > pivot right
Two partitions around pivot
Partition step in quicksort
Partition Array
Reorder by condition
Elements meeting condition first
Separate even/odd, positive/negative
Kth Element
QuickSelect partition
Eliminate half each iteration
Find kth largest/smallest element
Example: Dutch National Flag (Sort colors)
function sortColors(nums) { let low = 0; // Boundary for 0s let mid = 0; // Current element let high = nums.length - 1; // Boundary for 2s while (mid <= high) { if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; } else if (nums[mid] === 1) { mid++; } else { // nums[mid] === 2 [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; // Don't increment mid - need to check swapped element } }}// [2,0,2,1,1,0] -> [0,0,1,1,2,2]
Example: Partition array around pivot
function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; // Index of smaller element for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } // Place pivot in correct position [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1; // Pivot index}
2.5 Collision Detection Patterns
Pattern
Scenario
Detection Method
Application
Meeting Point
Pointers converge from opposite ends
Check if pointers cross or meet
Binary search, palindrome validation
Circular Collision
Fast pointer catches slow in cycle
Fast laps slow pointer
Linked list cycle detection
Gap Closure
Distance between pointers decreases
Monitor pointer distance
Container with most water
Boundary Check
Pointers reach array bounds
Index validation before access
Prevent out-of-bounds errors
Example: Remove nth node from end of list
function removeNthFromEnd(head, n) { const dummy = { next: head }; let fast = dummy; let slow = dummy; // Move fast n+1 steps ahead for (let i = 0; i <= n; i++) { fast = fast.next; } // Move both until fast reaches end while (fast) { fast = fast.next; slow = slow.next; } // Remove nth node slow.next = slow.next.next; return dummy.next;}
2.6 Space Optimization Techniques
Technique
Space Saved
Trade-off
Example
In-place Modification
O(n) → O(1)
May modify input array
Remove duplicates, move zeros
Pointer Instead of Copy
Avoid array cloning
Need to track positions carefully
Reverse string, partition array
Overwrite Strategy
Reuse input array for output
Original data lost
Merge sorted arrays in-place
Cycle Detection Memory
O(n) → O(1)
Only works for cyclic structures
Floyd's algorithm vs HashSet
Example: Reverse string in-place
function reverseString(s) { let left = 0; let right = s.length - 1; while (left < right) { // Swap characters [s[left], s[right]] = [s[right], s[left]]; left++; right--; } // O(1) space - no extra array needed}// ['h','e','l','l','o'] -> ['o','l','l','e','h']
Note: Two pointers technique achieves O(1) space complexity for many problems that would otherwise require O(n) space. The key is recognizing when pointers can replace additional data structures like HashSets or extra arrays.
Two Pointers Pattern Summary
Opposite Ends: Start from both ends, move based on condition (sorted arrays)
Fast-Slow: Different speeds reveal patterns (cycle detection, middle element)
Same Direction: One tracks position, other scans (remove duplicates)
Partitioning: Maintain invariants between pointer regions (Dutch flag)
Key Benefit: O(n) time with O(1) space - optimal for in-place operations
Warning: Always validate pointer positions before dereferencing. In fast-slow patterns, check both fast and fast.next to prevent null pointer errors. For opposite-ends technique, ensure left < right condition is correct.
3. Prefix Sum and Cumulative Techniques
3.1 Basic Prefix Sum Implementation
Concept
Formula
Query Time
Use Case
Prefix Sum Array
prefix[i] = arr[0] + ... + arr[i]
O(1)
Range sum queries after O(n) preprocessing
Range Sum Query
sum[L,R] = prefix[R] - prefix[L-1]
O(1)
Get sum of elements from index L to R
Cumulative Sum
prefix[i] = prefix[i-1] + arr[i]
O(n) build
Progressive sum accumulation
Zero Initialization
prefix[0] = 0 or arr[0]
N/A
Simplifies boundary handling
Example: Range sum query using prefix sum
class NumArray { constructor(nums) { this.prefix = new Array(nums.length + 1).fill(0); // Build prefix sum array for (let i = 0; i < nums.length; i++) { this.prefix[i + 1] = this.prefix[i] + nums[i]; } } sumRange(left, right) { // Sum from left to right (inclusive) return this.prefix[right + 1] - this.prefix[left]; }}// Example usageconst numArray = new NumArray([-2, 0, 3, -5, 2, -1]);console.log(numArray.sumRange(0, 2)); // Output: 1 (-2+0+3)console.log(numArray.sumRange(2, 5)); // Output: -1 (3-5+2-1)
Example: Subarray sum equals k (prefix sum with HashMap)
function subarraySum(nums, k) { const prefixSumCount = new Map(); prefixSumCount.set(0, 1); // Base case let sum = 0; let count = 0; for (let num of nums) { sum += num; // Check if (sum - k) exists if (prefixSumCount.has(sum - k)) { count += prefixSumCount.get(sum - k); } // Add current sum to map prefixSumCount.set(sum, (prefixSumCount.get(sum) || 0) + 1); } return count;}// Example: [1,1,1], k=2 -> Output: 2 ([1,1] appears twice)
Sum = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]
O(1)
Query sum of submatrix in constant time
Inclusion-Exclusion
Add total, subtract overlaps, add back intersection
O(1)
Avoid double counting in 2D space
Padding Approach
Add extra row/column of zeros at index 0
Space: O(m×n)
Simplify boundary conditions
Example: 2D range sum query (immutable matrix)
class NumMatrix { constructor(matrix) { if (!matrix.length || !matrix[0].length) { this.prefix = []; return; } const m = matrix.length; const n = matrix[0].length; // Create prefix sum with padding this.prefix = Array(m + 1).fill(0) .map(() => Array(n + 1).fill(0)); // Build 2D prefix sum for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { this.prefix[i][j] = matrix[i-1][j-1] + this.prefix[i-1][j] + this.prefix[i][j-1] - this.prefix[i-1][j-1]; } } } sumRegion(row1, col1, row2, col2) { // Sum of rectangle from (row1,col1) to (row2,col2) return this.prefix[row2+1][col2+1] - this.prefix[row1][col2+1] - this.prefix[row2+1][col1] + this.prefix[row1][col1]; }}
3.3 Difference Array for Range Updates
Technique
Operation
Update Time
Application
Difference Array
diff[i] = arr[i] - arr[i-1]
O(1) per update
Efficient range increment/decrement
Range Update
diff[L] += val; diff[R+1] -= val
O(1)
Add value to range [L, R] efficiently
Reconstruct Array
arr[i] = arr[i-1] + diff[i]
O(n)
Build final array after all updates
Multiple Updates
Apply all updates, then reconstruct once
O(k + n)
k updates + n reconstruction
Example: Range addition using difference array
function getModifiedArray(length, updates) { const diff = new Array(length + 1).fill(0); // Apply all updates to difference array for (let [start, end, inc] of updates) { diff[start] += inc; diff[end + 1] -= inc; } // Reconstruct array using prefix sum const result = new Array(length); result[0] = diff[0]; for (let i = 1; i < length; i++) { result[i] = result[i-1] + diff[i]; } return result;}// Example: length=5, updates=[[1,3,2],[2,4,3],[0,2,-2]]// Output: [-2,0,3,5,3]
Example: Corporate flight bookings
function corpFlightBookings(bookings, n) { const diff = new Array(n + 1).fill(0); // Each booking adds seats to a range of flights for (let [first, last, seats] of bookings) { diff[first - 1] += seats; // 1-indexed diff[last] -= seats; } // Build result array const result = new Array(n); result[0] = diff[0]; for (let i = 1; i < n; i++) { result[i] = result[i-1] + diff[i]; } return result;}
3.4 Range Query Optimization
Strategy
Preprocessing
Query
Best For
Prefix Sum
O(n)
O(1)
Immutable arrays, frequent sum queries
Sparse Table
O(n log n)
O(1)
Range min/max queries, immutable data
Segment Tree
O(n)
O(log n)
Mutable arrays, range queries + updates
Fenwick Tree (BIT)
O(n log n)
O(log n)
Prefix sums with updates, space efficient
Immutable Range Queries
Query Type
Best Structure
Range Sum
Prefix Sum Array
Range Min/Max
Sparse Table
Range GCD
Sparse Table
Mutable Range Queries
Query Type
Best Structure
Point Update + Range Sum
Fenwick Tree
Range Update + Query
Segment Tree
Complex Aggregates
Segment Tree
Example: Product of array except self (prefix/suffix product)
function productExceptSelf(nums) { const n = nums.length; const result = new Array(n); // Build prefix products from left result[0] = 1; for (let i = 1; i < n; i++) { result[i] = result[i-1] * nums[i-1]; } // Build suffix products from right and combine let suffixProduct = 1; for (let i = n - 1; i >= 0; i--) { result[i] *= suffixProduct; suffixProduct *= nums[i]; } return result;}// [1,2,3,4] -> [24,12,8,6] (O(n) time, O(1) extra space)
3.5 Prefix XOR and Bitwise Operations
Operation
Property
Formula
Application
Prefix XOR
a ^ a = 0
xor[i] = xor[i-1] ^ arr[i]
Range XOR queries, finding unique elements
Range XOR
Self-inverse property
xor[L,R] = xor[R] ^ xor[L-1]
Cancel out common prefix
Single Number
XOR eliminates pairs
result = a[0] ^ ... ^ a[n]
Find element appearing odd times
Prefix OR/AND
Bitwise cumulation
Similar to prefix sum pattern
Aggregate bitwise operations
Example: XOR queries of a subarray
function xorQueries(arr, queries) { const n = arr.length; const prefixXor = new Array(n + 1).fill(0); // Build prefix XOR array for (let i = 0; i < n; i++) { prefixXor[i + 1] = prefixXor[i] ^ arr[i]; } // Answer queries const result = []; for (let [left, right] of queries) { // XOR of range [left, right] result.push(prefixXor[right + 1] ^ prefixXor[left]); } return result;}// arr=[1,3,4,8], queries=[[0,1],[1,2],[0,3],[3,3]]// Output: [2,7,14,8]
Example: Count triplets with XOR equal to zero
function countTriplets(arr) { const n = arr.length; let count = 0; // Build prefix XOR const prefixXor = new Array(n + 1).fill(0); for (let i = 0; i < n; i++) { prefixXor[i + 1] = prefixXor[i] ^ arr[i]; } // If prefixXor[i] === prefixXor[j], // XOR from i to j-1 is 0 for (let i = 0; i < n; i++) { for (let j = i + 1; j <= n; j++) { if (prefixXor[i] === prefixXor[j]) { // All subarrays in [i, j-1] work count += j - i - 1; } } } return count;}
3.6 Memory-efficient Prefix Calculations
Technique
Space Optimization
Trade-off
When to Use
Rolling Variables
O(n) → O(1)
Can only query current position
One-pass calculations, streaming data
In-place Modification
Reuse input array
Destroys original data
When input can be modified
On-demand Computation
No preprocessing storage
Higher query time
Few queries, large data
Compressed Storage
Store only key indices
More complex logic
Sparse arrays, many zeros
Example: Running sum with O(1) space
function runningSum(nums) { // Modify array in-place for (let i = 1; i < nums.length; i++) { nums[i] += nums[i - 1]; } return nums; // O(1) extra space}// Alternative: Using separate accumulatorfunction runningSumConstantSpace(nums) { const result = new Array(nums.length); let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; result[i] = sum; } return result;}
Example: Max sum with rolling variables
function maxSubArray(nums) { // Kadane's algorithm - O(1) space let maxSoFar = nums[0]; let maxEndingHere = nums[0]; for (let i = 1; i < nums.length; i++) { // Extend or restart subarray maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar;}// No array storage needed - just two variables
Note: Prefix sum transforms O(n) range queries into O(1) queries with O(n) preprocessing. The difference array technique enables O(1) range updates instead of O(n), crucial for multiple update operations.
Prefix Sum Pattern Summary
1D Prefix:prefix[i] = prefix[i-1] + arr[i] for O(1) range sums
2D Prefix: Inclusion-exclusion principle for rectangle queries
Difference Array: Range updates in O(1), reconstruct in O(n)
XOR Prefix: Use XOR properties: a ^ a = 0, a ^ 0 = a
Space Optimization: Rolling variables for one-pass, in-place when allowed
Warning: When using 1-indexed arrays or padding with zeros, ensure consistent indexing in both construction and queries. For 2D prefix sums, be careful with the inclusion-exclusion formula - subtract both sides then add back the intersection to avoid double counting.
4. Binary Search
4.1 Classic Binary Search Template
Template Type
Condition
Loop Invariant
Use Case
Standard Template
while (left <= right)
Search space includes both boundaries
Find exact target in sorted array
Left Bias
while (left < right)
Answer in [left, right), terminates at left
Find first position meeting condition
Right Bias
while (left < right) + mid = left + ⌊(right-left+1)/2⌋
function binarySearch(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { left = mid + 1; // Search right half } else { right = mid - 1; // Search left half } } return -1; // Target not found}// Time: O(log n), Space: O(1)
Example: Recursive binary search
function binarySearchRecursive(nums, target, left = 0, right = nums.length - 1) { if (left > right) return -1; const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) { return binarySearchRecursive(nums, target, mid + 1, right); } else { return binarySearchRecursive(nums, target, left, mid - 1); }}// Space: O(log n) due to recursion stack
4.2 Lower/Upper Bound Implementation
Bound Type
Definition
Template
Result
Lower Bound
First index where arr[i] >= target
while (left < right); if (arr[mid] < target) left = mid+1
Leftmost position to insert target
Upper Bound
First index where arr[i] > target
while (left < right); if (arr[mid] <= target) left = mid+1
Rightmost position to insert target
First Occurrence
Leftmost index of target value
Lower bound with equality check
Start of range of equal values
Last Occurrence
Rightmost index of target value
Upper bound - 1 with equality check
End of range of equal values
Example: Lower bound (first >= target)
function lowerBound(nums, target) { let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < target) { left = mid + 1; } else { right = mid; // Could be answer } } return left;}// [1,2,4,4,5], target=4 -> 2// [1,2,4,4,5], target=3 -> 2
Example: Upper bound (first > target)
function upperBound(nums, target) { let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] <= target) { left = mid + 1; } else { right = mid; } } return left;}// [1,2,4,4,5], target=4 -> 4// [1,2,4,4,5], target=3 -> 2
Example: Find first and last position of element
function searchRange(nums, target) { const findFirst = () => { let left = 0, right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; right = mid - 1; // Keep searching left } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }; const findLast = () => { let left = 0, right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; left = mid + 1; // Keep searching right } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }; return [findFirst(), findLast()];}
4.3 Search in Rotated Array Variants
Variant
Key Insight
Strategy
Complexity
Rotated Sorted Array
One half always sorted
Identify sorted half, check if target in range
O(log n)
With Duplicates
May need to skip duplicates
When arr[left]=arr[mid]=arr[right], shrink linearly
O(log n) avg, O(n) worst
Find Minimum
Minimum at rotation point
Compare mid with right, move towards unsorted half
O(log n)
Rotation Count
Index of minimum element
Same as find minimum, return index
O(log n)
Example: Search in rotated sorted array
function searchRotated(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; // Determine which half is sorted if (nums[left] <= nums[mid]) { // Left half is sorted if (nums[left] <= target && target < nums[mid]) { right = mid - 1; // Target in left half } else { left = mid + 1; // Target in right half } } else { // Right half is sorted if (nums[mid] < target && target <= nums[right]) { left = mid + 1; // Target in right half } else { right = mid - 1; // Target in left half } } } return -1;}// [4,5,6,7,0,1,2], target=0 -> 4
Example: Find minimum in rotated sorted array
function findMin(nums) { let left = 0; let right = nums.length - 1; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] > nums[right]) { // Minimum is in right half left = mid + 1; } else { // Minimum is in left half or at mid right = mid; } } return nums[left];}// [3,4,5,1,2] -> 1// [4,5,6,7,0,1,2] -> 0
4.4 Binary Search on Answer Space
Pattern
Problem Type
Search Space
Example Problems
Minimize Maximum
Find smallest value where condition holds
[min_possible, max_possible]
Split array largest sum, minimize max distance
Maximize Minimum
Find largest value where condition holds
[min_possible, max_possible]
Aggressive cows, maximize minimum distance
Feasibility Check
Binary search with validation function
Test if value is feasible
Koko eating bananas, capacity to ship packages
Monotonic Property
Answer space has monotone property
If k works, all values in direction also work
Essential for binary search applicability
Example: Koko eating bananas (minimize eating speed)
function minEatingSpeed(piles, h) { // Can Koko finish all piles in h hours at speed k? const canFinish = (k) => { let hours = 0; for (let pile of piles) { hours += Math.ceil(pile / k); } return hours <= h; }; let left = 1; // Minimum speed let right = Math.max(...piles); // Maximum speed needed while (left < right) { const mid = left + Math.floor((right - left) / 2); if (canFinish(mid)) { right = mid; // Try slower speed } else { left = mid + 1; // Need faster speed } } return left;}// piles=[3,6,7,11], h=8 -> 4
Example: Capacity to ship packages within D days
function shipWithinDays(weights, days) { // Can ship all packages in 'days' with capacity 'cap'? const canShip = (capacity) => { let daysNeeded = 1; let currentWeight = 0; for (let weight of weights) { if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = 0; } currentWeight += weight; } return daysNeeded <= days; }; let left = Math.max(...weights); // Min capacity = max weight let right = weights.reduce((a, b) => a + b); // Max = sum all while (left < right) { const mid = left + Math.floor((right - left) / 2); if (canShip(mid)) { right = mid; // Try smaller capacity } else { left = mid + 1; // Need larger capacity } } return left;}
4.5 Floating Point Binary Search
Aspect
Integer Binary Search
Floating Point Binary Search
Termination
left <= right
right - left > epsilon
Precision
Exact integer values
Threshold like 1e-6 or 1e-9
Iterations
log₂(n)
Fixed iterations (e.g., 100) or epsilon-based
Mid Update
mid = (left + right) / 2
mid = (left + right) / 2.0
Example: Square root with precision
function sqrt(x, precision = 1e-6) { if (x === 0) return 0; let left = 0; let right = x; // For x < 1, sqrt(x) > x if (x < 1) right = 1; while (right - left > precision) { const mid = (left + right) / 2; const square = mid * mid; if (square < x) { left = mid; } else { right = mid; } } return (left + right) / 2;}// sqrt(2) ≈ 1.414214// sqrt(0.25) ≈ 0.5
Example: Find peak element with fixed iterations
function findPeakElement(nums) { let left = 0; let right = nums.length - 1; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < nums[mid + 1]) { // Peak is on the right left = mid + 1; } else { // Peak is on the left or at mid right = mid; } } return left; // Peak index}// Works for integer arrays but demonstrates// the concept of moving towards increasing direction
4.6 Binary Search Debugging Tips
Common Bug
Symptom
Fix
Prevention
Infinite Loop
Loop never terminates
Check mid calculation, ensure progress
Use left + (right-left)/2, verify bounds update
Off-by-One
Missing boundary elements
Review < vs <=, mid±1
Test with arrays of size 1, 2, 3
Integer Overflow
Incorrect mid for large arrays
Never use (left+right)/2
Always: left + (right-left)/2
Wrong Condition
Returns incorrect result
Clarify what you're searching for
Write invariant: what does [left,right] contain?
Note: Common mistakes to avoid:
Using (left + right) / 2 - causes overflow
Not maintaining loop invariant
Incorrect boundary updates (infinite loop)
Forgetting edge cases (empty array, single element)
Warning: Debug checklist:
Does loop make progress every iteration?
Are boundaries updated correctly?
Is mid calculation overflow-safe?
Test with edge cases: [1], [1,2], [1,2,3]
Example: Debugging template with invariant comments
function binarySearchWithInvariant(nums, target) { let left = 0; let right = nums.length - 1; // Invariant: if target exists, it's in [left, right] while (left <= right) { // Prevent overflow const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { return mid; // Found } // Maintain invariant: eliminate half that can't contain target if (nums[mid] < target) { left = mid + 1; // Target must be in (mid, right] } else { right = mid - 1; // Target must be in [left, mid) } } // Invariant broken: target doesn't exist return -1;}
Lower Bound: First position >= target, while(left<right)
Answer Space: Binary search on result values with feasibility check
Rotated Array: Identify sorted half, check if target in range
Key Insight: Eliminate half of search space each iteration = O(log n)
Note: Binary search requires monotonic property - some characteristic that increases/decreases across the search space. This applies to sorted arrays (element values increase) and answer spaces (feasibility changes at a threshold).
5. Fast & Slow Pointers
5.1 Cycle Detection in Linked Lists
Algorithm
Approach
Time
Space
Floyd's Algorithm
Fast moves 2 steps, slow moves 1 step
O(n)
O(1)
HashSet Method
Store visited nodes in set
O(n)
O(n)
Collision Point
If cycle exists, fast catches slow
Within cycle length
Meeting point inside cycle
Why It Works
Distance closes by 1 each iteration in cycle
Guaranteed meeting
Fast gains 1 step per iteration on slow
Example: Floyd's cycle detection algorithm
function hasCycle(head) { if (!head || !head.next) return false; let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; // Move 1 step fast = fast.next.next; // Move 2 steps if (slow === fast) { return true; // Cycle detected } } return false; // No cycle}// Time: O(n), Space: O(1)// If cycle exists, they meet in at most n steps
Example: Alternative with HashSet (for comparison)
function hasCycleHashSet(head) { const visited = new Set(); let current = head; while (current) { if (visited.has(current)) { return true; // Found cycle } visited.add(current); current = current.next; } return false;}// Time: O(n), Space: O(n) - less efficient than Floyd's
5.2 Middle of Linked List Finding
Scenario
Technique
Result
Use Case
Odd Length List
When fast reaches end, slow at middle
Exact middle node
1→2→3→4→5, middle = 3
Even Length List
Slow at second middle
Right of two middle nodes
1→2→3→4, middle = 3
Single Node
Return head
Head itself is middle
Edge case handling
Two Nodes
Return second node
Fast reaches end, slow at 2nd
1→2, middle = 2
Example: Find middle node
function middleNode(head) { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow;}// Odd: 1→2→3→4→5 -> 3// Even: 1→2→3→4 -> 3// Returns second middle for even
Example: Delete middle node
function deleteMiddle(head) { if (!head || !head.next) return null; let slow = head; let fast = head; let prev = null; while (fast && fast.next) { prev = slow; slow = slow.next; fast = fast.next.next; } // Delete middle node prev.next = slow.next; return head;}
5.3 Palindrome Linked List Verification
Step
Operation
Complexity
Purpose
1. Find Middle
Use fast-slow pointers
O(n/2)
Locate midpoint of list
2. Reverse Second Half
Reverse from middle to end
O(n/2)
Prepare for comparison
3. Compare Halves
Compare first half with reversed second
O(n/2)
Check if values match
4. Restore (Optional)
Reverse second half back to original
O(n/2)
Restore input list structure
Example: Check if linked list is palindrome
function isPalindrome(head) { if (!head || !head.next) return true; // Step 1: Find middle using fast-slow pointers let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } // Step 2: Reverse second half let prev = null; while (slow) { const next = slow.next; slow.next = prev; prev = slow; slow = next; } // Step 3: Compare first and reversed second half let left = head; let right = prev; while (right) { // Right is shorter or equal if (left.val !== right.val) { return false; } left = left.next; right = right.next; } return true;}// 1→2→2→1 -> true// 1→2→3→2→1 -> true// 1→2→3 -> false
function getIntersectionNode(headA, headB) { if (!headA || !headB) return null; let pA = headA; let pB = headB; // Traverse both lists // When reaching end, switch to other list's head while (pA !== pB) { pA = pA ? pA.next : headB; pB = pB ? pB.next : headA; } return pA; // Either intersection node or null}// Why it works:// If intersection exists:// pA: a1→a2→c1→c2→c3→(switch)→b1→b2→b3→c1 (meet here)// pB: b1→b2→b3→c1→c2→c3→(switch)→a1→a2→c1 (meet here)// If no intersection:// Both reach null at same time
Example: Intersection with length calculation
function getIntersectionNodeByLength(headA, headB) { const getLength = (head) => { let len = 0; while (head) { len++; head = head.next; } return len; }; let lenA = getLength(headA); let lenB = getLength(headB); // Align starting points while (lenA > lenB) { headA = headA.next; lenA--; } while (lenB > lenA) { headB = headB.next; lenB--; } // Move together until intersection while (headA !== headB) { headA = headA.next; headB = headB.next; } return headA;}
5.5 Duplicate Detection in Arrays
Constraint
Technique
Complexity
Problem Type
Array [1, n]
Treat as linked list, values as indices
O(n), O(1)
Find duplicate in array of n+1 elements
Floyd's in Array
slow = arr[slow], fast = arr[arr[fast]]
O(n), O(1)
Cycle detection where duplicate creates cycle
No Constraints
HashSet to track seen elements
O(n), O(n)
General duplicate detection
Sorted Array
Adjacent comparison or binary search
O(n) or O(log n)
Duplicates are adjacent
Example: Find duplicate number using Floyd's algorithm
function findDuplicate(nums) { // Treat array as linked list: index -> value // Duplicate creates a cycle // Phase 1: Detect cycle let slow = nums[0]; let fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast); // Phase 2: Find cycle entrance (duplicate) slow = nums[0]; while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; } return slow;}// nums = [1,3,4,2,2]// Index: 0→1, 1→3, 2→4, 3→2, 4→2 (cycle: 2→4→2)// Output: 2
Note: The duplicate detection works because if nums[i] = nums[j] where i ≠ j, then following the "linked list" indices leads to a cycle. The entrance to this cycle is the duplicate value.
5.6 Starting Point of Cycle
Phase
Action
Mathematical Basis
Result
Phase 1: Detection
Fast-slow meet inside cycle
Distance from start to meeting = k × cycle_length
Confirm cycle exists
Phase 2: Find Start
Reset slow to head, both move at same speed
Distance from head to start = distance from meet to start
They meet at cycle start
Proof
Let L = dist to cycle, C = cycle length
When they meet: 2×slow = fast = L + kC
Remaining distance = L
Cycle Length
Keep one pointer fixed, count steps
Count iterations until pointers meet again
Optional: determine cycle size
Example: Find cycle start position
function detectCycleStart(head) { let slow = head; let fast = head; // Phase 1: Detect if cycle exists while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { // Cycle detected, find start // Phase 2: Find cycle entrance slow = head; while (slow !== fast) { slow = slow.next; fast = fast.next; } return slow; // Cycle start } } return null; // No cycle}// Mathematical proof:// Let L = distance from head to cycle start// Let C = cycle length// Let X = distance from cycle start to meeting point// When they meet: Fast traveled 2×distance of Slow// Fast: L + nC + X (n loops in cycle)// Slow: L + X// Therefore: 2(L + X) = L + nC + X// Simplify: L = nC - X// So distance from head to start = (cycle length - meeting distance)
Example: Find cycle length
function getCycleLength(head) { let slow = head; let fast = head; // Detect cycle while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { // Found cycle, now count length let count = 1; let current = slow.next; while (current !== slow) { count++; current = current.next; } return count; } } return 0; // No cycle}
Floyd's Algorithm Variations
Basic Cycle Detection: Check if slow === fast
Cycle Start: Reset one pointer, move both at same speed
Cycle Length: Keep one fixed, count until they meet
Note: Fast-slow pointer pattern achieves O(1) space complexity for problems that would otherwise require O(n) space with HashSet. The key insight is using speed differential to detect patterns like cycles and middle elements.
Warning: Always check both fast and fast.next before accessing fast.next.next to prevent null pointer errors. For array-based Floyd's, ensure array values are valid indices to avoid out-of-bounds access.
6. Merge Intervals
6.1 Merging Overlapping Intervals
Step
Operation
Condition
Action
1. Sort
Sort intervals by start time
intervals.sort((a,b) => a[0] - b[0])
Ensures sequential processing
2. Initialize
Start with first interval
merged = [intervals[0]]
Base case for merging
3. Check Overlap
Compare end with next start
if (last.end >= current.start)
Intervals overlap or touch
4. Merge or Add
Extend end or add new interval
last.end = max(last.end, current.end)
Update merged result
Example: Merge overlapping intervals
function merge(intervals) { if (intervals.length <= 1) return intervals; // 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 (last[1] >= current[0]) { // Overlapping - merge by extending end last[1] = Math.max(last[1], current[1]); } else { // No overlap - add as new interval merged.push(current); } } return merged;}// [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]// Time: O(n log n), Space: O(n)
Note: When merging, use Math.max(last[1], current[1]) for the end time because current interval might be completely contained within the last interval.
6.2 Insert Interval Optimization
Phase
Strategy
Condition
Complexity
Before Insert
Add intervals ending before new interval
interval[1] < newInterval[0]
No overlap, add as-is
Merge Phase
Merge all overlapping intervals
interval[0] <= newInterval[1]
Update start/end bounds
After Insert
Add remaining intervals
interval[0] > newInterval[1]
No more overlaps
Optimization
No sorting needed - already sorted
Input guaranteed sorted
O(n) linear time
Example: Insert interval into sorted intervals
function insert(intervals, newInterval) { const result = []; let i = 0; // Phase 1: Add all intervals before newInterval while (i < intervals.length && intervals[i][1] < newInterval[0]) { result.push(intervals[i]); i++; } // Phase 2: Merge 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); // Phase 3: Add remaining intervals while (i < intervals.length) { result.push(intervals[i]); i++; } return result;}// intervals = [[1,3],[6,9]], newInterval = [2,5]// Output: [[1,5],[6,9]]
6.3 Interval Intersection Logic
Relationship
Condition
Intersection
Visual
Overlap Exists
max(start1, start2) <= min(end1, end2)
[max(start1,start2), min(end1,end2)]
Intervals share common region
No Overlap
end1 < start2 || end2 < start1
Empty intersection
Completely separate intervals
One Contains Other
start1 <= start2 && end1 >= end2
Smaller interval is intersection
Nested intervals
Partial Overlap
Start of one < end of other
Overlapping region only
Crossing intervals
Example: Interval list intersections (two sorted lists)
function intervalIntersection(firstList, secondList) { const result = []; let i = 0, j = 0; while (i < firstList.length && j < secondList.length) { const [start1, end1] = firstList[i]; const [start2, end2] = secondList[j]; // Check if intervals overlap const start = Math.max(start1, start2); const end = Math.min(end1, end2); if (start <= end) { // Overlap exists result.push([start, end]); } // Move pointer of interval that ends first if (end1 < end2) { i++; } else { j++; } } return result;}// A = [[0,2],[5,10],[13,23],[24,25]]// B = [[1,5],[8,12],[15,24],[25,26]]// Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
6.4 Meeting Rooms Scheduling
Problem
Approach
Data Structure
Complexity
Can Attend All?
Sort by start, check if any overlap
Sorted array
O(n log n)
Min Meeting Rooms
Track concurrent meetings with heap
Min heap of end times
O(n log n)
Alternative: Sweep Line
Count +1 at start, -1 at end
Event array with timestamps
O(n log n)
Max Concurrent
Track maximum rooms in use at any time
Running count of active meetings
Peak value during sweep
Example: Can attend all meetings?
function canAttendMeetings(intervals) { if (intervals.length <= 1) return true; // Sort by start time intervals.sort((a, b) => a[0] - b[0]); // Check for any overlap for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] < intervals[i-1][1]) { return false; // Overlap found } } return true;}// [[0,30],[5,10],[15,20]] -> false// [[7,10],[2,4]] -> true
Example: Meeting rooms II with min heap (alternative)
function minMeetingRoomsHeap(intervals) { if (intervals.length === 0) return 0; // Sort by start time intervals.sort((a, b) => a[0] - b[0]); // Min heap to track end times of ongoing meetings const endTimes = [intervals[0][1]]; for (let i = 1; i < intervals.length; i++) { const [start, end] = intervals[i]; // If earliest ending meeting finished, reuse room if (endTimes[0] <= start) { endTimes.shift(); // Remove earliest end time } // Add current meeting's end time endTimes.push(end); endTimes.sort((a, b) => a - b); // Maintain min heap } return endTimes.length; // Number of rooms needed}// [[0,30],[5,10],[15,20]] -> 2
6.5 Non-overlapping Intervals Greedy
Strategy
Sort Key
Greedy Choice
Rationale
Max Non-overlapping
Sort by end time
Always pick interval ending earliest
Leaves most room for future intervals
Min Removals
Sort by end time
Keep intervals that end early
Removals = total - max non-overlapping
Interval Partitioning
Sort by start time
Assign to earliest available partition
Minimize number of partitions needed
Activity Selection
Sort by end time
Greedy end-time selection
Classic greedy algorithm proof
Example: Minimum number of intervals to remove
function eraseOverlapIntervals(intervals) { if (intervals.length <= 1) return 0; // Sort by end time (greedy choice) intervals.sort((a, b) => a[1] - b[1]); let count = 0; let end = intervals[0][1]; for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] < end) { // Overlaps with previous - remove this one count++; } else { // No overlap - update end time end = intervals[i][1]; } } return count;}// [[1,2],[2,3],[3,4],[1,3]] -> 1 (remove [1,3])// Greedy: Keep intervals ending earliest
Example: Maximum non-overlapping intervals (activity selection)
function maxNonOverlapping(intervals) { if (intervals.length === 0) return 0; // Sort by end time intervals.sort((a, b) => a[1] - b[1]); let count = 1; // First interval always included let end = intervals[0][1]; for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] >= end) { // No overlap - include this interval count++; end = intervals[i][1]; } } return count;}// Proof: Greedy choice optimal - interval ending earliest// leaves maximum space for remaining intervals
6.6 Timeline Event Processing
Pattern
Event Types
Processing Order
Use Case
Start/End Events
+1 for start, -1 for end
Sort by time, then type (end before start)
Count active intervals at any time
Sweep Line
Process events in chronological order
Maintain running state across timeline
Skyline problem, interval coverage
Employee Free Time
Flatten all schedules, find gaps
Merge busy intervals, return gaps
Common free time across people
Point vs Interval
Events at specific times
Discrete events vs continuous ranges
Different collision detection logic
Example: Employee free time (flatten and find gaps)
function employeeFreeTime(schedule) { // Flatten all intervals const allIntervals = []; for (let employee of schedule) { allIntervals.push(...employee); } // Sort by start time allIntervals.sort((a, b) => a[0] - b[0]); // Merge overlapping intervals const merged = [allIntervals[0]]; for (let i = 1; i < allIntervals.length; i++) { const last = merged[merged.length - 1]; const curr = allIntervals[i]; if (last[1] >= curr[0]) { last[1] = Math.max(last[1], curr[1]); } else { merged.push(curr); } } // 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;}// schedule = [[[1,3],[4,6]], [[2,4]], [[6,8]]]// Output: [[4,6]] is not available, [[6,6]] is gap -> No free time// Actual output: [] (no common free time)
Example: Sweep line for maximum concurrent events
function maxConcurrentEvents(intervals) { const events = []; // Create start and end events for (let [start, end] of intervals) { events.push([start, 1]); // Start event events.push([end, -1]); // End event } // Sort events: by time, end events before start events events.sort((a, b) => { if (a[0] !== b[0]) return a[0] - b[0]; return a[1] - b[1]; // End (-1) before start (1) }); let current = 0; let maxConcurrent = 0; for (let [time, type] of events) { current += type; maxConcurrent = Math.max(maxConcurrent, current); } return maxConcurrent;}// [[0,30],[5,10],[15,20]] -> 2 concurrent meetings max
Merge Intervals Pattern Summary
Standard Merge: Sort by start, merge overlapping by extending end
Insert Interval: Three phases - before, merge, after (O(n) no sort)
Intersection:max(start1,start2) <= min(end1,end2)
Meeting Rooms: Min heap of end times or sweep line with events
Greedy Selection: Sort by end time, pick earliest ending
Sweep Line: Process start/end events chronologically
Note: When sorting intervals for merging, always sort by start time. For greedy maximum selection problems, sort by end time. For sweep line, process events in chronological order with tie-breaking rules (end before start at same time).
Warning: Be careful with boundary conditions: use < vs <= consistently. For example, [1,2] and [2,3] might be considered overlapping or adjacent depending on problem definition. Always clarify if endpoints are inclusive or exclusive.
7. Cyclic Sort
7.1 Placing Elements in Correct Index
Concept
Rule
Invariant
Application
Index Mapping
For range [1,n]: place value k at index k-1
arr[i] = i+1 after sorting
Numbers 1 to n in array of size n
Zero-based Range
For range [0,n-1]: place value k at index k
arr[i] = i after sorting
Numbers 0 to n-1 in array of size n
Swap Until Correct
Keep swapping until element at correct position
Each swap places at least one element correctly
O(n) time - each element moved once
Detection Phase
After sorting, scan for missing/duplicate
Incorrect position indicates problem
Missing numbers, duplicates, corrupt pairs
Example: Cyclic sort for range [1, n]
function cyclicSort(nums) { let i = 0; while (i < nums.length) { const correctIndex = nums[i] - 1; // For range [1,n] if (nums[i] !== nums[correctIndex]) { // Swap to place element at correct position [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; // Element already at correct position } } return nums;}// [3, 1, 5, 4, 2] -> [1, 2, 3, 4, 5]// Time: O(n), Space: O(1)// Key insight: Each element swapped at most once
Example: Cyclic sort for range [0, n-1]
function cyclicSortZeroBased(nums) { let i = 0; while (i < nums.length) { const correctIndex = nums[i]; // For range [0,n-1] if (nums[i] < nums.length && nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } return nums;}// [2, 0, 3, 1] -> [0, 1, 2, 3]
7.2 Finding Missing Numbers Efficiently
Problem Variant
Approach
Complexity
Key Insight
Single Missing
Cyclic sort then find index where arr[i] ≠ i+1
O(n), O(1)
First incorrect position has missing number
All Missing
Cyclic sort then collect all incorrect positions
O(n), O(k)
k missing numbers at wrong indices
Missing in Range
Place elements, scan for gaps
O(n), O(1)
Expected value vs actual value mismatch
Without Modification
XOR or sum formula approach
O(n), O(1)
Alternative when can't modify array
Example: Find missing number (single)
function findMissingNumber(nums) { let i = 0; const n = nums.length; // Cyclic sort for range [0, n] while (i < n) { const correctIndex = nums[i]; if (nums[i] < n && nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } // Find missing number for (let i = 0; i < n; i++) { if (nums[i] !== i) { return i; // Missing number } } return n; // Missing number is n}// [3, 0, 1] -> 2// [0, 1] -> 2// [9,6,4,2,3,5,7,0,1] -> 8
Example: Find all missing numbers
function findDisappearedNumbers(nums) { let i = 0; // Cyclic sort for range [1, n] while (i < nums.length) { const correctIndex = nums[i] - 1; if (nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } // Find all missing numbers const missing = []; for (let i = 0; i < nums.length; i++) { if (nums[i] !== i + 1) { missing.push(i + 1); } } return missing;}// [4,3,2,7,8,2,3,1] -> [5,6]// After sort: [1,2,3,2,3,8,7,8], positions 4,5 have wrong values
7.3 Finding Duplicates O(1) Space
Detection Method
Strategy
Works For
Trade-off
Cyclic Sort Scan
After sorting, duplicate at wrong position
Range [1,n] with one duplicate
Modifies array
Swap Detection
During swap, if both same value = duplicate
Find during sort process
Early termination possible
Index Marking
Use sign to mark visited indices
Positive integers only
Reversible modification
Multiple Duplicates
Collect all positions with wrong values
Multiple duplicates present
Returns all duplicates
Example: Find duplicate number
function findDuplicate(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++; } } // Find duplicate for (let i = 0; i < nums.length; i++) { if (nums[i] !== i + 1) { return nums[i]; } } return -1;}// [1,3,4,2,2] -> 2
Example: Find all duplicates
function findDuplicates(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++; } } const duplicates = []; for (let i = 0; i < nums.length; i++) { if (nums[i] !== i + 1) { duplicates.push(nums[i]); } } return duplicates;}
Example: Find duplicates without modification (index marking)
function findDuplicatesIndexMarking(nums) { const duplicates = []; for (let i = 0; i < nums.length; i++) { const index = Math.abs(nums[i]) - 1; if (nums[index] < 0) { // Already negative - duplicate found duplicates.push(Math.abs(nums[i])); } else { // Mark as visited by negating nums[index] = -nums[index]; } } // Restore array (optional) for (let i = 0; i < nums.length; i++) { nums[i] = Math.abs(nums[i]); } return duplicates;}// [4,3,2,7,8,2,3,1] -> [2,3]
7.4 Corrupt Pairs Detection
Problem Type
Definition
Detection
Solution
Set Mismatch
One number duplicated, one missing
Find both using cyclic sort
[duplicate, missing]
Corrupt Pair
Two numbers swapped incorrectly
Both positions have wrong values
Return the swapped pair
XOR Technique
Use XOR to find different elements
XOR all elements with expected range
Result is duplicate XOR missing
Sum Difference
Compare actual sum vs expected sum
Difference reveals relationship
Combined with product or sum of squares
Example: Find corrupt pair (set mismatch)
function findErrorNums(nums) { let i = 0; // Cyclic sort while (i < nums.length) { const correctIndex = nums[i] - 1; if (nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } // Find duplicate and missing for (let i = 0; i < nums.length; i++) { if (nums[i] !== i + 1) { return [nums[i], i + 1]; // [duplicate, missing] } } return [-1, -1];}// [1,2,2,4] -> [2,3] (2 is duplicate, 3 is missing)// [1,1] -> [1,2]
7.5 First Missing Positive Integer
Challenge
Solution
Key Insight
Complexity
Range Constraint
Only care about positives in [1, n]
Answer must be in [1, n+1]
Ignore negatives and > n
Cyclic Sort Modified
Sort only valid range values
Skip out-of-range during swap
O(n), O(1)
First Gap
First index where arr[i] ≠ i+1
Missing positive at that index
Return index + 1
All Present Case
If [1..n] all present, answer is n+1
Perfect sequence means next is missing
Edge case handling
Example: First missing positive integer
function firstMissingPositive(nums) { let i = 0; const n = nums.length; // Cyclic sort - only for valid range [1, n] while (i < n) { const correctIndex = nums[i] - 1; // Only swap if value in valid range and not at correct position if (nums[i] > 0 && nums[i] <= n && nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } // Find first missing positive for (let i = 0; i < n; i++) { if (nums[i] !== i + 1) { return i + 1; } } // All [1..n] present, answer is n+1 return n + 1;}// [1,2,0] -> 3// [3,4,-1,1] -> 2// [7,8,9,11,12] -> 1
Note: This is one of the hardest cyclic sort problems. The key is recognizing that the first missing positive must be in range [1, n+1], so we only need to consider elements in [1, n] during sorting.
7.6 Range Validation Techniques
Validation Type
Check
Purpose
Example
Bounds Check
0 <= val < n or 1 <= val <= n
Prevent out-of-bounds access
Avoid array index errors
Duplicate Position
nums[i] === nums[correctIndex]
Detect when element already correct
Avoid infinite swap loops
Self-loop Prevention
i !== correctIndex
Don't swap element with itself
Optimization, not required
Valid Value Range
Filter out negatives, zeros, or too large
Skip irrelevant values
First missing positive problem
Example: Safe cyclic sort with validation
function safeCyclicSort(nums) { let i = 0; while (i < nums.length) { const val = nums[i]; const correctIndex = val - 1; // Comprehensive validation if (val >= 1 && // Lower bound val <= nums.length && // Upper bound val !== nums[correctIndex]) { // Not duplicate [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } return nums;}
Example: Validation for edge cases
function validateAndSort(nums) { // Handle edge cases if (!nums || nums.length === 0) { return []; } if (nums.length === 1) { return nums; } let i = 0; while (i < nums.length) { const correctIndex = nums[i] - 1; if (correctIndex >= 0 && correctIndex < nums.length && nums[i] !== nums[correctIndex]) { [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; } else { i++; } } return nums;}
Cyclic Sort Pattern Summary
When to Use: Array contains numbers in range [1,n] or [0,n-1]
Core Pattern: Swap elements until each is at correct index position
Time Complexity: O(n) - each element moved at most once
Key Validation: Check bounds and prevent duplicate swaps
Note: Cyclic sort achieves O(n) time with O(1) space by leveraging the property that array indices can store values. The pattern works because each swap places at least one element in its correct position, guaranteeing linear time.
Warning: Always validate before swapping: check nums[i] !== nums[correctIndex] to prevent infinite loops when duplicate exists. Ensure correctIndex is within bounds [0, n-1] to avoid out-of-bounds access. For first missing positive, skip values outside [1, n] range.
8. Top K Elements
8.1 Kth Largest/Smallest Element
Approach
Data Structure
Time Complexity
Space
Best For
Min Heap (K Largest)
Size-K min heap
O(n log k)
O(k)
K much smaller than n
Max Heap (K Smallest)
Size-K max heap
O(n log k)
O(k)
K much smaller than n
QuickSelect
In-place partition
O(n) avg, O(n²) worst
O(1)
Single query, can modify array
Full Sort
Native sort
O(n log n)
O(1) or O(n)
Need all elements sorted anyway
Example: Kth largest using min heap
class MinHeap { constructor() { this.heap = []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { if (this.heap.length === 0) return null; const min = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return min; } 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[idx] >= this.heap[parent]) break; [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]]; idx = parent; } } bubbleDown(idx) { while (true) { let smallest = idx; const left = 2 * idx + 1; const right = 2 * idx + 2; if (left < this.heap.length && this.heap[left] < this.heap[smallest]) { smallest = left; } if (right < this.heap.length && this.heap[right] < this.heap[smallest]) { smallest = right; } if (smallest === idx) break; [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]]; idx = smallest; } }}function findKthLargest(nums, k) { const minHeap = new MinHeap(); for (const num of nums) { minHeap.push(num); if (minHeap.size() > k) { minHeap.pop(); // Remove smallest } } return minHeap.peek();}// [3,2,1,5,6,4], k=2 -> 5
Example: Kth largest using QuickSelect
function findKthLargest(nums, k) { // Convert to kth smallest from end return quickSelect(nums, 0, nums.length - 1, nums.length - k);}function quickSelect(nums, left, right, k) { if (left === right) return nums[left]; // Random pivot for better average case const pivotIndex = left + Math.floor(Math.random() * (right - left + 1)); const partitionIdx = partition(nums, left, right, pivotIndex); if (k === partitionIdx) { return nums[k]; } else if (k < partitionIdx) { return quickSelect(nums, left, partitionIdx - 1, k); } else { return quickSelect(nums, partitionIdx + 1, right, k); }}function partition(nums, left, right, pivotIndex) { const pivotValue = nums[pivotIndex]; // Move pivot to end [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]]; let storeIndex = left; for (let i = left; i < right; i++) { if (nums[i] < pivotValue) { [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]]; storeIndex++; } } // Move pivot to final position [nums[right], nums[storeIndex]] = [nums[storeIndex], nums[right]]; return storeIndex;}// O(n) average, O(n²) worst case
8.2 K Closest Points Euclidean
Strategy
Implementation
Key Point
Optimization
Max Heap by Distance
Store K closest, evict farthest
Use max heap to track K smallest distances
Avoid sqrt - compare squared distances
QuickSelect on Distance
Partition by distance value
Find Kth closest, return all <= K
In-place, O(n) average
Custom Comparator
Define distance comparison function
Works with any distance metric
Reusable pattern
Distance Calculation
x² + y² (no sqrt needed)
Squared distance preserves ordering
Faster computation
Example: K closest points using max heap
class MaxHeap { constructor(compareFn) { this.heap = []; this.compare = compareFn || ((a, b) => a - b); } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { if (this.heap.length === 0) return null; const max = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(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.compare(this.heap[idx], this.heap[parent]) <= 0) break; [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]]; idx = parent; } } bubbleDown(idx) { while (true) { let largest = idx; const left = 2 * idx + 1; const right = 2 * idx + 2; if (left < this.heap.length && this.compare(this.heap[left], this.heap[largest]) > 0) { largest = left; } if (right < this.heap.length && this.compare(this.heap[right], this.heap[largest]) > 0) { largest = right; } if (largest === idx) break; [this.heap[idx], this.heap[largest]] = [this.heap[largest], this.heap[idx]]; idx = largest; } }}function kClosest(points, k) { const distanceSq = ([x, y]) => x * x + y * y; const maxHeap = new MaxHeap((a, b) => distanceSq(a) - distanceSq(b)); for (const point of points) { maxHeap.push(point); if (maxHeap.size() > k) { maxHeap.pop(); // Remove farthest } } return maxHeap.heap;}// [[1,3],[-2,2]], k=1 -> [[-2,2]]// Time: O(n log k), Space: O(k)
8.3 K Frequent Elements HashMap
Approach
Steps
Complexity
When to Use
HashMap + Min Heap
Count frequencies, maintain K-size heap
O(n log k)
K much smaller than unique elements
HashMap + Bucket Sort
Count, create frequency buckets
O(n)
Optimal time, more space
HashMap + QuickSelect
Count, partition by frequency
O(n) avg
One-time query, can modify
HashMap + Sort
Count, sort by frequency
O(n log n)
Simple implementation
Example: K frequent using min heap
function topKFrequent(nums, k) { // Count frequencies const freqMap = new Map(); for (const num of nums) { freqMap.set(num, (freqMap.get(num) || 0) + 1); } // Min heap by frequency const minHeap = new MinHeap(); for (const [num, freq] of freqMap.entries()) { minHeap.push({ num, freq }); if (minHeap.size() > k) { minHeap.pop(); } } return minHeap.heap.map(item => item.num);}// Custom MinHeap with frequency comparisonclass MinHeap { constructor() { this.heap = []; } push(item) { this.heap.push(item); this.bubbleUp(this.heap.length - 1); } pop() { if (this.heap.length === 0) return null; const min = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return min; } size() { return this.heap.length; } bubbleUp(idx) { while (idx > 0) { const parent = Math.floor((idx - 1) / 2); if (this.heap[idx].freq >= this.heap[parent].freq) break; [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]]; idx = parent; } } bubbleDown(idx) { while (true) { let smallest = idx; const left = 2 * idx + 1; const right = 2 * idx + 2; if (left < this.heap.length && this.heap[left].freq < this.heap[smallest].freq) { smallest = left; } if (right < this.heap.length && this.heap[right].freq < this.heap[smallest].freq) { smallest = right; } if (smallest === idx) break; [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]]; idx = smallest; } }}// [1,1,1,2,2,3], k=2 -> [1,2]
Example: K frequent using bucket sort
function topKFrequent(nums, k) { // Count frequencies const freqMap = new Map(); for (const num of nums) { freqMap.set(num, (freqMap.get(num) || 0) + 1); } // Create buckets: index = frequency const buckets = Array(nums.length + 1) .fill(null).map(() => []); for (const [num, freq] of freqMap.entries()) { buckets[freq].push(num); } // Collect top K from highest frequencies const result = []; for (let i = buckets.length - 1; i >= 0; i--) { for (const num of buckets[i]) { result.push(num); if (result.length === k) { return result; } } } return result;}// Time: O(n), Space: O(n)// Most efficient for large datasets
8.4 QuickSelect Partition Algorithm
Concept
Details
Optimization
Trade-off
Partition Logic
Choose pivot, partition around it
Lomuto vs Hoare partition schemes
Lomuto simpler, Hoare fewer swaps
Pivot Selection
Random, median-of-3, or first element
Random gives O(n) expected time
Deterministic can be O(n²) worst case
Recursive Strategy
Only recurse on one half
T(n) = T(n/2) + O(n) = O(n)
Binary search-like pruning
In-place Modification
Modifies original array
O(1) extra space
Array order changed
Example: QuickSelect with random pivot
function quickSelect(nums, k) { // Find kth smallest (0-indexed) return quickSelectHelper(nums, 0, nums.length - 1, k);}function quickSelectHelper(nums, left, right, k) { if (left === right) return nums[left]; // Random pivot for average O(n) const pivotIndex = left + Math.floor(Math.random() * (right - left + 1)); const partitionIdx = partition(nums, left, right, pivotIndex); if (k === partitionIdx) { return nums[k]; } else if (k < partitionIdx) { return quickSelectHelper(nums, left, partitionIdx - 1, k); } else { return quickSelectHelper(nums, partitionIdx + 1, right, k); }}function partition(nums, left, right, pivotIndex) { const pivotValue = nums[pivotIndex]; // Move pivot to end [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]]; let storeIndex = left; // Lomuto partition scheme for (let i = left; i < right; i++) { if (nums[i] < pivotValue) { [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]]; storeIndex++; } } // Move pivot to final position [nums[right], nums[storeIndex]] = [nums[storeIndex], nums[right]]; return storeIndex;}// Average: O(n), Worst: O(n²)// Space: O(1) if iterative, O(log n) recursion stack
Example: QuickSelect with median-of-3 pivot
function medianOf3Pivot(nums, left, right) { const mid = Math.floor((left + right) / 2); // Sort left, mid, right if (nums[left] > nums[mid]) { [nums[left], nums[mid]] = [nums[mid], nums[left]]; } if (nums[mid] > nums[right]) { [nums[mid], nums[right]] = [nums[right], nums[mid]]; } if (nums[left] > nums[mid]) { [nums[left], nums[mid]] = [nums[mid], nums[left]]; } return mid; // Median is at mid}function quickSelectMedian3(nums, k) { return helper(nums, 0, nums.length - 1, k); function helper(nums, left, right, k) { if (left === right) return nums[left]; const pivotIndex = medianOf3Pivot(nums, left, right); const partitionIdx = partition(nums, left, right, pivotIndex); if (k === partitionIdx) return nums[k]; else if (k < partitionIdx) { return helper(nums, left, partitionIdx - 1, k); } else { return helper(nums, partitionIdx + 1, right, k); } }}// Better worst-case performance than random pivot
8.5 Top K Merge Streams
Scenario
Approach
Complexity
Application
K Sorted Lists
Min heap with (value, listIndex, elementIndex)
O(n log k)
Merge K sorted arrays/streams
Smallest Range K Lists
Track max, min heap for min across lists
O(n log k)
Find smallest range covering K lists
K Pairs Smallest Sum
Min heap with pair sums
O(k log k)
Find K pairs with smallest sums
Stream Top K
Maintain size-K heap as stream flows
O(log k) per insert
Real-time top K tracking
Example: Merge K sorted lists
function mergeKLists(lists) { const minHeap = new MinHeap((a, b) => a.value - b.value); // Initialize heap with first element from each list for (let i = 0; i < lists.length; i++) { if (lists[i].length > 0) { minHeap.push({ value: lists[i][0], listIdx: i, elemIdx: 0 }); } } const result = []; while (minHeap.size() > 0) { const { value, listIdx, elemIdx } = minHeap.pop(); result.push(value); // Add next element from same list if (elemIdx + 1 < lists[listIdx].length) { minHeap.push({ value: lists[listIdx][elemIdx + 1], listIdx, elemIdx: elemIdx + 1 }); } } return result;}// [[1,4,5],[1,3,4],[2,6]]// -> [1,1,2,3,4,4,5,6]// Time: O(n log k), n = total elements, k = number of lists
Example: K pairs with smallest sums
function kSmallestPairs(nums1, nums2, k) { if (!nums1.length || !nums2.length) return []; const minHeap = new MinHeap((a, b) => a.sum - b.sum); const result = []; // Initialize with pairs (nums1[i], nums2[0]) for (let i = 0; i < Math.min(k, nums1.length); i++) { minHeap.push({ sum: nums1[i] + nums2[0], i, j: 0 }); } while (k > 0 && minHeap.size() > 0) { const { sum, i, j } = minHeap.pop(); result.push([nums1[i], nums2[j]]); k--; // Add next pair from same nums1 index if (j + 1 < nums2.length) { minHeap.push({ sum: nums1[i] + nums2[j + 1], i, j: j + 1 }); } } return result;}// nums1=[1,7,11], nums2=[2,4,6], k=3// -> [[1,2],[1,4],[1,6]]
8.6 Bucket Sort for Top K
Use Case
Implementation
Time
Constraint
Frequency-based Top K
Buckets indexed by frequency
O(n)
Frequency range known: [0, n]
Score-based Top K
Buckets for score ranges
O(n + range)
Discrete score values
Collect from Buckets
Iterate from highest to lowest
O(n)
Stop when K elements collected
Advantage
Linear time, no heap overhead
Fastest for Top K
Only works with bounded integer keys
Example: Top K frequent using bucket sort
function topKFrequentBucket(nums, k) { // Step 1: Count frequencies const freqMap = new Map(); for (const num of nums) { freqMap.set(num, (freqMap.get(num) || 0) + 1); } // Step 2: Create buckets (index = frequency) const buckets = Array(nums.length + 1).fill(null).map(() => []); for (const [num, freq] of freqMap.entries()) { buckets[freq].push(num); } // Step 3: Collect top K from highest frequencies const result = []; for (let freq = buckets.length - 1; freq >= 0 && result.length < k; freq--) { for (const num of buckets[freq]) { result.push(num); if (result.length === k) { return result; } } } return result;}// [1,1,1,2,2,3], k=2 -> [1,2]// Time: O(n), Space: O(n)// Key insight: Max frequency is n, so bucket array size is O(n)
Example: Sort characters by frequency using buckets
function frequencySort(s) { // Count frequencies const freqMap = new Map(); for (const char of s) { freqMap.set(char, (freqMap.get(char) || 0) + 1); } // Create frequency buckets const buckets = Array(s.length + 1).fill(null).map(() => []); for (const [char, freq] of freqMap.entries()) { buckets[freq].push(char); } // Build result from highest to lowest frequency let result = ''; for (let freq = buckets.length - 1; freq >= 0; freq--) { for (const char of buckets[freq]) { result += char.repeat(freq); } } return result;}// "tree" -> "eert" or "eetr"// "cccaaa" -> "cccaaa" or "aaaccc"
Top K Elements Pattern Summary
Heap Approach: O(n log k) time, O(k) space - best when K << n
QuickSelect: O(n) average time, O(1) space - modifies array
Bucket Sort: O(n) time, O(n) space - optimal for frequency problems
Min Heap for Top K Largest: Keep K largest by evicting smallest
Max Heap for Top K Smallest: Keep K smallest by evicting largest
K Sorted Lists Merge: Use min heap with (value, listIdx, elemIdx)
Note: Choose data structure based on constraints: Use heap when K is much smaller than n, QuickSelect for one-time queries with modifiable arrays, and bucket sort when dealing with frequencies or bounded integer ranges (O(n) time optimal).
Warning: QuickSelect has O(n²) worst case with poor pivot selection. Use random pivot or median-of-3 for better average performance. Bucket sort only works when key range is bounded - won't work for arbitrary real numbers or unbounded ranges.
9. BFS DFS Graph Traversal
9.1 Level Order Traversal Queue
Component
Implementation
Purpose
Complexity
Queue Structure
FIFO - process nodes level by level
Guarantees breadth-first order
O(1) enqueue/dequeue
Level Tracking
Record queue size at start of level
Process exactly one level at a time
Enables level-specific operations
Visited Set
Track processed nodes to avoid cycles
Prevent infinite loops in graphs
O(V) space for V vertices
Applications
Tree level order, graph BFS, shortest path
Layer-by-layer exploration
O(V + E) for graphs
Example: Binary tree level order traversal
function levelOrder(root) { if (!root) return []; const result = []; const queue = [root]; while (queue.length > 0) { const levelSize = queue.length; const currentLevel = []; // Process all nodes at current level 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;}// Tree: [3,9,20,null,null,15,7]// 3// / \// 9 20// / \// 15 7// Result: [[3],[9,20],[15,7]]// Time: O(n), Space: O(w) where w is max width
Example: Graph level order BFS
function bfsLevelOrder(graph, start) { const visited = new Set(); const queue = [start]; const levels = []; visited.add(start); while (queue.length > 0) { const levelSize = queue.length; const currentLevel = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift(); currentLevel.push(node); for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } levels.push(currentLevel); } return levels;}// Graph: {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}// BFS from 0: [[0], [1,2], [3]]
Example: Right side view of tree
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 level = rightmost if (i === levelSize - 1) { result.push(node.val); } if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return result;}// [1,2,3,null,5,null,4] -> [1,3,4]
9.2 Multi-source BFS Pattern
Concept
Strategy
Use Case
Advantage
Multiple Starting Points
Initialize queue with all sources
Rotten oranges, 0-1 matrix distance
Single pass instead of multiple BFS
Simultaneous Expansion
All sources expand outward together
Natural wave propagation simulation
Correct distance/time calculation
Level = Time/Distance
Each level represents one unit
Minimum time to reach all cells
Level count gives answer directly
Common Applications
Grid problems, nearest point queries
Walls and gates, forest fire spread
O(m*n) for grid
Example: Rotting oranges (multi-source BFS)
function orangesRotting(grid) { const rows = grid.length; const cols = grid[0].length; const queue = []; let fresh = 0; // Find all initially rotten oranges and count fresh for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) { queue.push([r, c, 0]); // [row, col, time] } else if (grid[r][c] === 1) { fresh++; } } } const directions = [[0,1], [1,0], [0,-1], [-1,0]]; let minutes = 0; while (queue.length > 0) { const [r, c, time] = queue.shift(); minutes = Math.max(minutes, time); for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) { grid[nr][nc] = 2; // Make rotten fresh--; queue.push([nr, nc, time + 1]); } } } return fresh === 0 ? minutes : -1;}// [[2,1,1],[1,1,0],[0,1,1]] -> 4// All oranges rot simultaneously from all rotten sources
Example: 0-1 matrix (distance to nearest 0)
function updateMatrix(mat) { const rows = mat.length; const cols = mat[0].length; const queue = []; const dist = Array(rows).fill(null) .map(() => Array(cols).fill(Infinity)); // Initialize with all 0s for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (mat[r][c] === 0) { queue.push([r, c]); dist[r][c] = 0; } } } const directions = [[0,1], [1,0], [0,-1], [-1,0]]; while (queue.length > 0) { const [r, c] = queue.shift(); for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] > dist[r][c] + 1) { dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]); } } } return dist;}// [[0,0,0],[0,1,0],[1,1,1]]// -> [[0,0,0],[0,1,0],[1,2,1]]
9.3 Shortest Path BFS Unweighted
Property
Details
Guarantee
Why It Works
Unweighted Graphs
All edges have weight 1
BFS finds shortest path
Level order = distance order
First Reach = Shortest
First time visiting a node is shortest
No need to revisit
BFS explores by increasing distance
Path Reconstruction
Store parent pointers during BFS
Backtrack from target to source
Parent map traces shortest path
Time Complexity
O(V + E) for adjacency list
Each vertex/edge visited once
Linear in graph size
Example: Shortest path in unweighted graph
function shortestPath(graph, start, target) { const queue = [[start, 0]]; // [node, distance] const visited = new Set([start]); const parent = new Map(); parent.set(start, null); while (queue.length > 0) { const [node, dist] = queue.shift(); if (node === target) { // Reconstruct path const path = []; let current = target; while (current !== null) { path.unshift(current); current = parent.get(current); } return { distance: dist, path }; } for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); parent.set(neighbor, node); queue.push([neighbor, dist + 1]); } } } return { distance: -1, path: [] }; // No path found}// Graph: {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}// shortestPath(graph, 0, 3) -> {distance: 2, path: [0,1,3]}
Example: Word ladder (shortest transformation)
function ladderLength(beginWord, endWord, wordList) { const wordSet = new Set(wordList); if (!wordSet.has(endWord)) return 0; const queue = [[beginWord, 1]]; // [word, level] const visited = new Set([beginWord]); while (queue.length > 0) { const [word, level] = queue.shift(); if (word === endWord) return level; // Try all possible one-letter changes for (let i = 0; i < word.length; i++) { for (let c = 97; c <= 122; c++) { // 'a' to 'z' const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1); if (wordSet.has(newWord) && !visited.has(newWord)) { visited.add(newWord); queue.push([newWord, level + 1]); } } } } return 0; // No transformation found}// beginWord="hit", endWord="cog"// wordList=["hot","dot","dog","lot","log","cog"]// -> 5 (hit -> hot -> dot -> dog -> cog)
9.4 Cycle Detection DFS Coloring
Color
Meaning
State
Detection Rule
White (0)
Not visited yet
Initial state
Start DFS from here
Gray (1)
Currently being processed
In DFS recursion stack
If we reach gray node = cycle!
Black (2)
Completely processed
All descendants visited
No cycle through this node
Cycle Detection
Edge to gray node during DFS
Back edge found
Indicates cycle in directed graph
Example: Detect cycle in directed graph (DFS coloring)
function hasCycle(graph) { const n = graph.length; const color = Array(n).fill(0); // 0=white, 1=gray, 2=black function dfs(node) { color[node] = 1; // Mark as being processed (gray) for (const neighbor of graph[node]) { if (color[neighbor] === 1) { // Back edge to gray node = cycle! return true; } if (color[neighbor] === 0) { if (dfs(neighbor)) return true; } // If black (2), skip - already processed } color[node] = 2; // Mark as completely processed (black) return false; } // Check all components for (let i = 0; i < n; i++) { if (color[i] === 0) { if (dfs(i)) return true; } } return false;}// Graph: [[1], [2], [0]] (0→1→2→0) -> true (cycle)// Graph: [[1], [2], []] (0→1→2) -> false (no cycle)
Example: Course schedule (cycle detection)
function canFinish(numCourses, prerequisites) { // Build adjacency list const graph = Array(numCourses).fill(null).map(() => []); for (const [course, prereq] of prerequisites) { graph[prereq].push(course); } const color = Array(numCourses).fill(0); function hasCycleDFS(node) { color[node] = 1; // Gray - in progress for (const neighbor of graph[node]) { if (color[neighbor] === 1) { return true; // Cycle detected } if (color[neighbor] === 0 && hasCycleDFS(neighbor)) { return true; } } color[node] = 2; // Black - completed return false; } for (let i = 0; i < numCourses; i++) { if (color[i] === 0 && hasCycleDFS(i)) { return false; // Cycle exists, can't finish } } return true; // No cycles, can finish all courses}// numCourses=2, prerequisites=[[1,0]]// -> true (take 0, then 1)// numCourses=2, prerequisites=[[1,0],[0,1]]// -> false (circular dependency)
9.5 Bidirectional BFS Optimization
Technique
Strategy
Benefit
Complexity
Two-ended Search
BFS from both start and end simultaneously
Meet in middle, reduces search space
O(b^(d/2)) vs O(b^d)
Alternating Expansion
Expand from smaller frontier each iteration
Balanced growth, better performance
Minimizes total nodes explored
Intersection Detection
Check if frontiers meet during expansion
Path found when they intersect
Sum of levels = shortest path length
Use Cases
Large graphs, long shortest paths
Exponential speedup possible
Best when branching factor is high
Example: Bidirectional BFS for shortest path
function bidirectionalBFS(graph, start, target) { if (start === target) return 0; const frontQueue = [start]; const backQueue = [target]; const frontVisited = new Map([[start, 0]]); const backVisited = new Map([[target, 0]]); let level = 0; while (frontQueue.length > 0 || backQueue.length > 0) { level++; // Expand from smaller frontier if (frontQueue.length <= backQueue.length) { // Expand forward const size = frontQueue.length; for (let i = 0; i < size; i++) { const node = frontQueue.shift(); for (const neighbor of graph[node]) { // Check if backward search reached this if (backVisited.has(neighbor)) { return frontVisited.get(node) + 1 + backVisited.get(neighbor); } if (!frontVisited.has(neighbor)) { frontVisited.set(neighbor, frontVisited.get(node) + 1); frontQueue.push(neighbor); } } } } else { // Expand backward const size = backQueue.length; for (let i = 0; i < size; i++) { const node = backQueue.shift(); for (const neighbor of graph[node]) { // Check if forward search reached this if (frontVisited.has(neighbor)) { return backVisited.get(node) + 1 + frontVisited.get(neighbor); } if (!backVisited.has(neighbor)) { backVisited.set(neighbor, backVisited.get(node) + 1); backQueue.push(neighbor); } } } } } return -1; // No path}// Reduces O(b^d) to O(b^(d/2)) where b=branching, d=depth
9.6 DFS Stack Iterative Implementation
Approach
Structure
Advantage
Drawback
Recursive DFS
Call stack (implicit stack)
Clean, intuitive code
Stack overflow risk for deep graphs
Iterative DFS
Explicit stack data structure
No stack overflow, controllable
More verbose, manual state management
Stack Operations
LIFO - push children, pop to visit
Mimics recursion behavior
O(V) space for stack
Visit Order
Depth-first, explores one path fully
Good for path-finding, topological sort
Not optimal for shortest path
Example: DFS recursive
function dfsRecursive(graph, start) { const visited = new Set(); const result = []; function dfs(node) { if (visited.has(node)) return; visited.add(node); result.push(node); for (const neighbor of graph[node]) { dfs(neighbor); } } dfs(start); return result;}// Clean and intuitive// Risk: Stack overflow for deep graphs
Example: DFS iterative with stack
function dfsIterative(graph, start) { const visited = new Set(); const stack = [start]; const result = []; while (stack.length > 0) { const node = stack.pop(); if (visited.has(node)) continue; visited.add(node); result.push(node); // Push neighbors in reverse order // to maintain left-to-right DFS for (let i = graph[node].length - 1; i >= 0; i--) { stack.push(graph[node][i]); } } return result;}// No recursion, no stack overflow
Example: DFS iterative with pre/post-order tracking
function dfsWithTimestamps(graph, start) { const visited = new Set(); const stack = [[start, 'pre']]; // [node, phase] const preOrder = []; const postOrder = []; while (stack.length > 0) { const [node, phase] = stack.pop(); if (phase === 'pre') { if (visited.has(node)) continue; visited.add(node); preOrder.push(node); // Push post-order marker stack.push([node, 'post']); // Push children for pre-order for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { stack.push([neighbor, 'pre']); } } } else { // Post-order - all children processed postOrder.push(node); } } return { preOrder, postOrder };}// Useful for topological sort (post-order reversed)
9.7 Flood Fill Pattern
Technique
Implementation
Use Case
Complexity
4-directional Fill
Up, down, left, right neighbors
Standard grid connectivity
4 neighbors per cell
8-directional Fill
Include diagonals
Chess king moves, island variants
8 neighbors per cell
DFS Approach
Recursively fill connected cells
Simple, clean code
O(m*n) time, O(m*n) stack worst case
BFS Approach
Queue-based level-by-level fill
Safer for large grids (no stack overflow)
O(m*n) time, O(min(m,n)) queue
Example: Flood fill DFS
function floodFill(image, sr, sc, color) { const originalColor = image[sr][sc]; if (originalColor === color) return image; const rows = image.length; const cols = image[0].length; function dfs(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== originalColor) { return; } image[r][c] = color; // 4-directional flood fill dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); } dfs(sr, sc); return image;}// image=[[1,1,1],[1,1,0],[1,0,1]]// sr=1, sc=1, color=2// -> [[2,2,2],[2,2,0],[2,0,1]]
Example: Flood fill BFS
function floodFillBFS(image, sr, sc, color) { const originalColor = image[sr][sc]; if (originalColor === color) return image; const rows = image.length; const cols = image[0].length; const queue = [[sr, sc]]; const directions = [[0,1],[1,0],[0,-1],[-1,0]]; image[sr][sc] = color; while (queue.length > 0) { const [r, c] = queue.shift(); for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) { image[nr][nc] = color; queue.push([nr, nc]); } } } return image;}// Safer for large grids
Example: Number of islands (flood fill variant)
function numIslands(grid) { if (!grid || grid.length === 0) return 0; const rows = grid.length; const cols = grid[0].length; let count = 0; function dfs(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') { return; } grid[r][c] = '0'; // Mark as visited dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === '1') { count++; dfs(r, c); // Flood fill entire island } } } return count;}// [["1","1","0"],// ["1","1","0"],// ["0","0","1"]]// -> 2 islands// Time: O(m*n), Space: O(m*n) recursion stack worst case
Multi-source BFS: Initialize queue with all sources, single pass
Shortest Path: BFS guarantees shortest in unweighted graphs
Cycle Detection: DFS with 3-color (white/gray/black) scheme
Bidirectional BFS: Search from both ends, O(b^(d/2)) speedup
DFS Iterative: Explicit stack, no recursion, no stack overflow
Flood Fill: DFS or BFS to fill connected regions
Note:BFS is optimal for shortest path in unweighted graphs and level-order traversal. DFS is better for topological sort, cycle detection, and path enumeration. For very large graphs or deep paths, use iterative DFS to avoid stack overflow.
Warning: Always track visited nodes in graphs to prevent infinite loops. For grids, either mark cells in-place or use a separate visited set. In DFS cycle detection, distinguish between gray (in current path) and black (fully processed) to correctly identify back edges.
10. Backtracking
10.1 Subsets Generation Bit Manipulation
Approach
Mechanism
Complexity
Advantage
Backtracking Recursive
Include/exclude each element
O(2^n * n)
Natural, easy to understand
Bit Manipulation
Each bit represents inclusion
O(2^n * n)
Iterative, no recursion stack
Total Subsets
2^n subsets for n elements
Powerset size
Each element: in or out
Iterative Building
Add each element to existing subsets
O(2^n * n)
Simple iteration pattern
Example: Subsets using backtracking
function subsets(nums) { const result = []; const current = []; function backtrack(index) { // Add current subset to result result.push([...current]); // Try adding each remaining element for (let i = index; i < nums.length; i++) { current.push(nums[i]); backtrack(i + 1); current.pop(); // Backtrack } } backtrack(0); return result;}// [1,2,3] -> [[],[1],[1,2],[1,2,3],// [1,3],[2],[2,3],[3]]// Time: O(2^n * n), Space: O(n) recursion
Example: Subsets using bit manipulation
function subsetsBitManipulation(nums) { const n = nums.length; const totalSubsets = 1 << n; // 2^n const result = []; for (let mask = 0; mask < totalSubsets; mask++) { const subset = []; for (let i = 0; i < n; i++) { // Check if i-th bit is set if (mask & (1 << i)) { subset.push(nums[i]); } } result.push(subset); } return result;}// [1,2,3] -> same result// No recursion, iterative approach
Example: Subsets with duplicates
function subsetsWithDup(nums) { nums.sort((a, b) => a - b); // Sort to group duplicates const result = []; const current = []; function backtrack(index) { result.push([...current]); for (let i = index; i < nums.length; i++) { // Skip duplicates at same level if (i > index && nums[i] === nums[i - 1]) { continue; } current.push(nums[i]); backtrack(i + 1); current.pop(); } } backtrack(0); return result;}// [1,2,2] -> [[],[1],[1,2],[1,2,2],[2],[2,2]]// Avoids duplicate subsets like [1,2] appearing twice
10.2 Permutations Next Lexicographic
Method
Strategy
Complexity
Use Case
Backtracking Swap
Swap elements, recurse, backtrack
O(n! * n)
Generate all permutations
Next Permutation Algorithm
Find pivot, swap, reverse suffix
O(n) per permutation
Lexicographic ordering
Used Array Tracking
Boolean array to mark used elements
O(n) extra space
Clearer logic, handles duplicates
Total Permutations
n! permutations for n distinct elements
Factorial growth
Combinatorial explosion
Example: Permutations using backtracking
function permute(nums) { const result = []; function backtrack(current, remaining) { if (remaining.length === 0) { result.push([...current]); return; } for (let i = 0; i < remaining.length; i++) { current.push(remaining[i]); // Create new remaining array without i-th element const newRemaining = [ ...remaining.slice(0, i), ...remaining.slice(i + 1) ]; backtrack(current, newRemaining); current.pop(); } } backtrack([], nums); return result;}// [1,2,3] -> [[1,2,3],[1,3,2],// [2,1,3],[2,3,1],// [3,1,2],[3,2,1]]
Example: Permutations with swap
function permuteSwap(nums) { const result = []; function backtrack(start) { if (start === nums.length) { result.push([...nums]); return; } for (let i = start; i < nums.length; i++) { // Swap current with start [nums[start], nums[i]] = [nums[i], nums[start]]; backtrack(start + 1); // Backtrack: swap back [nums[start], nums[i]] = [nums[i], nums[start]]; } } backtrack(0); return result;}// More efficient - O(1) space
Example: Next lexicographic permutation
function nextPermutation(nums) { // Step 1: Find rightmost pair where nums[i] < nums[i+1] let i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { // Step 2: Find rightmost element greater than nums[i] let j = nums.length - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } // Step 3: Swap [nums[i], nums[j]] = [nums[j], nums[i]]; } // Step 4: Reverse suffix from i+1 to end let left = i + 1; let right = nums.length - 1; while (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; } return nums; // Modified in-place}// [1,2,3] -> [1,3,2]// [3,2,1] -> [1,2,3] (wraps around)// Time: O(n), Space: O(1)
10.3 N-Queens Problem Constraint Propagation
Constraint
Check Method
Optimization
Data Structure
No Same Row
Place one queen per row
Implicit - iterate row by row
Guaranteed by iteration
No Same Column
Track used columns with set/array
O(1) lookup with set
Set or boolean array
No Same Diagonal
Track diagonals: row-col and row+col
O(1) lookup with sets
Two sets for both diagonals
Backtracking
Try each column, recurse, undo
Early pruning on conflicts
O(n!) time complexity
Example: N-Queens solution
function solveNQueens(n) { const result = []; const board = Array(n).fill(null).map(() => Array(n).fill('.')); const cols = new Set(); const diag1 = new Set(); // row - col const diag2 = new Set(); // row + col function backtrack(row) { if (row === n) { // Found valid solution result.push(board.map(r => r.join(''))); return; } for (let col = 0; col < n; col++) { // Check if position is safe if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) { continue; } // Place queen board[row][col] = 'Q'; cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(row + 1); // Backtrack board[row][col] = '.'; cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); } } backtrack(0); return result;}// n=4 -> [[".Q..","...Q","Q...","..Q."],// ["..Q.","Q...","...Q",".Q.."]]// Time: O(n!), Space: O(n)
Example: N-Queens count only
function totalNQueens(n) { let count = 0; const cols = new Set(); const diag1 = new Set(); const diag2 = new Set(); function backtrack(row) { if (row === n) { count++; return; } for (let col = 0; col < n; col++) { if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) { continue; } cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(row + 1); cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); } } backtrack(0); return count;}// More efficient - no board construction
10.4 Sudoku Solver Heuristic Optimization
Technique
Description
Impact
Complexity
Constraint Checking
Row, column, 3x3 box validation
Prune invalid choices early
O(1) with precomputed sets
Most Constrained First
Fill cells with fewest options first
Reduces branching factor
Heuristic optimization
Naked Singles
Cells with only one valid option
Deterministic placement
Preprocessing step
Backtracking
Try 1-9, recurse, undo on conflict
Exhaustive search with pruning
Worst case exponential
Example: Sudoku solver
function solveSudoku(board) { function isValid(board, row, col, num) { // Check row for (let c = 0; c < 9; c++) { if (board[row][c] === num) return false; } // Check column for (let r = 0; r < 9; r++) { if (board[r][col] === num) return false; } // Check 3x3 box const boxRow = Math.floor(row / 3) * 3; const boxCol = Math.floor(col / 3) * 3; for (let r = boxRow; r < boxRow + 3; r++) { for (let c = boxCol; c < boxCol + 3; c++) { if (board[r][c] === num) return false; } } return true; } function backtrack() { for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { if (board[row][col] === '.') { for (let num = 1; num <= 9; num++) { const char = num.toString(); if (isValid(board, row, col, char)) { board[row][col] = char; if (backtrack()) { return true; } board[row][col] = '.'; // Backtrack } } return false; // No valid number found } } } return true; // Board complete } backtrack(); return board;}// Modifies board in-place// Time: O(9^m) where m = empty cells
10.5 Combination Sum Target
Variant
Rule
Strategy
Optimization
Unlimited Reuse
Same element can be used multiple times
Don't increment index after use
Sort array, prune when exceeds target
Use Once
Each element used at most once
Increment index after use
Skip duplicates at same level
Fixed Length K
Combination must have exactly K elements
Track combination size
Prune when size exceeds K
Early Pruning
Stop when current sum > target
Requires sorted array
Dramatically reduces branches
Example: Combination sum (unlimited reuse)
function combinationSum(candidates, target) { const result = []; candidates.sort((a, b) => a - b); function backtrack(start, current, sum) { if (sum === target) { result.push([...current]); return; } if (sum > target) return; // Prune for (let i = start; i < candidates.length; i++) { // Prune: no point continuing if exceeds if (sum + candidates[i] > target) break; current.push(candidates[i]); // Can reuse same element: start at i backtrack(i, current, sum + candidates[i]); current.pop(); } } backtrack(0, [], 0); return result;}// [2,3,6,7], target=7// -> [[2,2,3],[7]]
Example: Combination sum II (use once)
function combinationSum2(candidates, target) { const result = []; candidates.sort((a, b) => a - b); function backtrack(start, current, sum) { if (sum === target) { result.push([...current]); return; } if (sum > target) return; for (let i = start; i < candidates.length; i++) { // Skip duplicates at same level if (i > start && candidates[i] === candidates[i - 1]) { continue; } if (sum + candidates[i] > target) break; current.push(candidates[i]); // Use once: start at i+1 backtrack(i + 1, current, sum + candidates[i]); current.pop(); } } backtrack(0, [], 0); return result;}// [10,1,2,7,6,1,5], target=8// -> [[1,1,6],[1,2,5],[1,7],[2,6]]
10.6 Word Search Board DFS
Component
Implementation
Purpose
Optimization
DFS from Each Cell
Try starting from every position
Find word starting point
Early exit on first match found
Path Tracking
Mark visited cells during DFS
Avoid revisiting in same path
Backtrack by unmarking
4-directional Search
Explore up, down, left, right
Find adjacent matching characters
Bounds checking required
Character Matching
Match current character with word[index]
Validate path correctness
Mismatch = immediate backtrack
Example: Word search in grid
function exist(board, word) { const rows = board.length; const cols = board[0].length; function dfs(row, col, index) { // Found complete word if (index === word.length) return true; // Out of bounds or mismatch if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[index]) { return false; } // Mark as visited const temp = board[row][col]; board[row][col] = '#'; // Explore all 4 directions const found = dfs(row + 1, col, index + 1) || dfs(row - 1, col, index + 1) || dfs(row, col + 1, index + 1) || dfs(row, col - 1, index + 1); // Backtrack board[row][col] = temp; return found; } // Try starting from each cell for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (dfs(r, c, 0)) return true; } } return false;}// board = [["A","B","C","E"],// ["S","F","C","S"],// ["A","D","E","E"]]// word = "ABCCED" -> true// Time: O(m*n*4^L) where L=word length
Example: Word search II (multiple words with Trie)
class TrieNode { constructor() { this.children = {}; this.word = null; }}function findWords(board, words) { // Build Trie const root = new TrieNode(); for (const word of words) { let node = root; for (const char of word) { if (!node.children[char]) { node.children[char] = new TrieNode(); } node = node.children[char]; } node.word = word; } const result = []; const rows = board.length; const cols = board[0].length; function dfs(row, col, node) { const char = board[row][col]; if (char === '#' || !node.children[char]) return; node = node.children[char]; if (node.word) { result.push(node.word); node.word = null; // Avoid duplicates } board[row][col] = '#'; if (row > 0) dfs(row - 1, col, node); if (row < rows - 1) dfs(row + 1, col, node); if (col > 0) dfs(row, col - 1, node); if (col < cols - 1) dfs(row, col + 1, node); board[row][col] = char; } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { dfs(r, c, root); } } return result;}// More efficient for multiple words
10.7 Palindrome Partitioning
Concept
Strategy
Optimization
Complexity
Partition Points
Try splitting at every position
Only split if prefix is palindrome
O(n) palindrome check per split
Backtracking
Build partition, recurse, backtrack
Exponential search space
O(2^n) partitions possible
DP Palindrome Check
Precompute all palindrome substrings
O(1) palindrome lookup
O(n²) preprocessing time/space
Expand Around Center
Check palindrome by expanding outward
O(n) per check, no extra space
Trade-off: time vs space
Example: Palindrome partitioning
function partition(s) { const result = []; function isPalindrome(str, left, right) { while (left < right) { if (str[left] !== str[right]) return false; left++; right--; } return true; } function backtrack(start, current) { if (start === s.length) { result.push([...current]); return; } for (let end = start; end < s.length; end++) { // Only proceed if substring is palindrome if (isPalindrome(s, start, end)) { current.push(s.substring(start, end + 1)); backtrack(end + 1, current); current.pop(); } } } backtrack(0, []); return result;}// "aab" -> [["a","a","b"],["aa","b"]]// "a" -> [["a"]]// Time: O(n * 2^n), Space: O(n)
Example: Palindrome partitioning with DP optimization
function partitionDP(s) { const n = s.length; // DP table: dp[i][j] = true if s[i..j] is palindrome const dp = Array(n).fill(null).map(() => Array(n).fill(false)); // Precompute all palindromes for (let len = 1; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (len === 1) { dp[i][j] = true; } else if (len === 2) { dp[i][j] = s[i] === s[j]; } else { dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1]; } } } const result = []; function backtrack(start, current) { if (start === n) { result.push([...current]); return; } for (let end = start; end < n; end++) { // O(1) palindrome check if (dp[start][end]) { current.push(s.substring(start, end + 1)); backtrack(end + 1, current); current.pop(); } } } backtrack(0, []); return result;}// Faster palindrome checks: O(1) instead of O(n)// Trade-off: O(n²) space for DP table
Subsets: Include/exclude decision tree, 2^n total subsets
Permutations: Swap-based or used-array approach, n! permutations
N-Queens: Constraint propagation with sets for O(1) conflict detection
Sudoku: Try 1-9, validate constraints, backtrack on conflict
Combination Sum: Sort array, prune when sum exceeds target
Word Search: DFS with visited marking, 4-directional exploration
Palindrome Partition: Try all splits, verify palindrome, recurse
Note: Backtracking is exhaustive search with pruning. Key optimizations: (1) Early termination when constraints violated, (2) Sort data for pruning opportunities, (3) Precompute expensive checks (like palindrome DP table), (4) Track state efficiently (sets for O(1) lookup vs arrays).
Warning: Backtracking has exponential time complexity in worst case. Always implement pruning strategies to reduce search space. For Sudoku/N-Queens, use sets for O(1) constraint checking instead of O(n) scans. Remember to backtrack properly - undo all state changes when returning from recursion.
11. Divide and Conquer
11.1 Merge Sort Pattern Application
Phase
Operation
Complexity
Key Insight
Divide
Split array into two halves
O(1)
Find middle index
Conquer
Recursively sort both halves
T(n/2) + T(n/2)
Two subproblems of size n/2
Combine
Merge two sorted arrays
O(n)
Linear scan with two pointers
Total Time
Master theorem analysis
O(n log n)
log n levels, O(n) work per level
Example: Merge sort implementation
function mergeSort(arr) { if (arr.length <= 1) return arr; // Divide const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); // Conquer const sortedLeft = mergeSort(left); const sortedRight = mergeSort(right); // Combine return merge(sortedLeft, sortedRight);}function merge(left, right) { const result = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } // Add remaining elements while (i < left.length) { result.push(left[i]); i++; } while (j < right.length) { result.push(right[j]); j++; } return result;}// [38,27,43,3,9,82,10] -> [3,9,10,27,38,43,82]// Time: O(n log n), Space: O(n)
Example: Count inversions using merge sort
function countInversions(arr) { if (arr.length <= 1) return { sorted: arr, count: 0 }; const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); const leftResult = countInversions(left); const rightResult = countInversions(right); const merged = mergeAndCount(leftResult.sorted, rightResult.sorted); return { sorted: merged.sorted, count: leftResult.count + rightResult.count + merged.count };}function mergeAndCount(left, right) { const result = []; let i = 0, j = 0, count = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; // All remaining elements in left are inversions count += left.length - i; } } while (i < left.length) result.push(left[i++]); while (j < right.length) result.push(right[j++]); return { sorted: result, count };}// [2,4,1,3,5] -> 3 inversions: (2,1), (4,1), (4,3)// Application: Measure of "sortedness"
11.2 Quick Sort Partition Strategy
Partition Scheme
Strategy
Swaps
Characteristics
Lomuto Partition
Single pointer, swap smaller elements to front
More swaps
Simpler, easier to understand
Hoare Partition
Two pointers from both ends
Fewer swaps
More efficient, trickier to implement
3-way Partition
Three regions: <pivot, =pivot, >pivot
Optimal for duplicates
Handles many equal elements well
Average Case
Random pivot selection
O(n log n)
Expected performance
Example: Quick sort with Lomuto partition
function quickSort(arr, left = 0, right = arr.length - 1) { if (left < right) { const pivotIndex = lomutoPartition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } return arr;}function lomutoPartition(arr, left, right) { const pivot = arr[right]; // Choose last as pivot let i = left; for (let j = left; j < right; j++) { if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; } } [arr[i], arr[right]] = [arr[right], arr[i]]; return i;}// Time: O(n log n) average, O(n²) worst// Space: O(log n) recursion stack
Example: Quick sort with Hoare partition
function quickSortHoare(arr, left = 0, right = arr.length - 1) { if (left < right) { const pivotIndex = hoarePartition(arr, left, right); quickSortHoare(arr, left, pivotIndex); quickSortHoare(arr, pivotIndex + 1, right); } return arr;}function hoarePartition(arr, left, right) { const pivot = arr[Math.floor((left + right) / 2)]; let i = left - 1; let j = right + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) return j; [arr[i], arr[j]] = [arr[j], arr[i]]; }}// Fewer swaps than Lomuto
Example: 3-way partition (Dutch National Flag)
function quickSort3Way(arr, left = 0, right = arr.length - 1) { if (left >= right) return arr; const pivot = arr[left]; let lt = left; // Elements < pivot let i = left + 1; // Current element let gt = right; // Elements > pivot while (i <= gt) { if (arr[i] < pivot) { [arr[lt], arr[i]] = [arr[i], arr[lt]]; lt++; i++; } else if (arr[i] > pivot) { [arr[i], arr[gt]] = [arr[gt], arr[i]]; gt--; } else { i++; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt + 1, right); return arr;}// [3,5,3,2,3,1,3,4,3] -> sorted efficiently// Optimal when many duplicates exist// Equal elements not recursed on
11.3 Binary Tree Divide Conquer
Pattern
Approach
Combine Step
Example Problem
Height/Depth
Recurse on children, return max + 1
max(left, right) + 1
Tree height, depth calculation
Path Sum
Recurse with remaining sum
Check if current + child paths work
Path sum, binary tree paths
Diameter
Track max path through each node
Max of left+right or child diameters
Longest path in tree
Balanced Check
Return height and balance status
Check |left.height - right.height| <= 1
Validate balanced tree
Example: Tree height/depth
function maxDepth(root) { // Base case if (!root) return 0; // Divide: recurse on children const leftDepth = maxDepth(root.left); const rightDepth = maxDepth(root.right); // Conquer: combine results return Math.max(leftDepth, rightDepth) + 1;}// Tree with 3 levels -> depth = 3// Time: O(n), Space: O(h) where h = height
Example: Balanced binary tree
function isBalanced(root) { function checkHeight(node) { if (!node) return 0; const leftHeight = checkHeight(node.left); if (leftHeight === -1) return -1; const rightHeight = checkHeight(node.right); if (rightHeight === -1) return -1; // Check balance condition if (Math.abs(leftHeight - rightHeight) > 1) { return -1; // Not balanced } return Math.max(leftHeight, rightHeight) + 1; } return checkHeight(root) !== -1;}// Returns true if balanced, false otherwise
Example: Binary tree diameter
function diameterOfBinaryTree(root) { let maxDiameter = 0; function height(node) { if (!node) return 0; const leftHeight = height(node.left); const rightHeight = height(node.right); // Update diameter: path through current node maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight); // Return height for parent return Math.max(leftHeight, rightHeight) + 1; } height(root); return maxDiameter;}// 1// / \// 2 3// / \// 4 5// Diameter = 3 (4-2-1-3 or 5-2-1-3)// Time: O(n), Space: O(h)
Example: Lowest common ancestor (LCA)
function lowestCommonAncestor(root, p, q) { // Base case if (!root || root === p || root === q) { return root; } // Divide: search in subtrees const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); // Conquer: combine results if (left && right) { // p and q on different sides return root; } // Both on same side or one not found return left || right;}// Finds the lowest node that has both p and q as descendants// Time: O(n), Space: O(h)
11.4 Closest Pair of Points
Step
Operation
Complexity
Purpose
Preprocessing
Sort points by x-coordinate
O(n log n)
Enable divide step
Divide
Split into left/right halves
O(1)
Find middle x-coordinate
Conquer
Find closest in each half recursively
T(n/2)
Solve subproblems
Combine
Check strip around midline
O(n)
Find cross-boundary pairs
Example: Closest pair of points
function closestPair(points) { // Sort by x-coordinate points.sort((a, b) => a.x - b.x); function distance(p1, p2) { const dx = p1.x - p2.x; const dy = p1.y - p2.y; return Math.sqrt(dx * dx + dy * dy); } function bruteForce(pts) { let minDist = Infinity; for (let i = 0; i < pts.length; i++) { for (let j = i + 1; j < pts.length; j++) { minDist = Math.min(minDist, distance(pts[i], pts[j])); } } return minDist; } function closestUtil(pts) { const n = pts.length; // Base case: brute force for small n if (n <= 3) return bruteForce(pts); // Divide const mid = Math.floor(n / 2); const midPoint = pts[mid]; const left = pts.slice(0, mid); const right = pts.slice(mid); // Conquer const dl = closestUtil(left); const dr = closestUtil(right); const d = Math.min(dl, dr); // Combine: check strip const strip = pts.filter(p => Math.abs(p.x - midPoint.x) < d); // Sort strip by y-coordinate strip.sort((a, b) => a.y - b.y); let minDist = d; for (let i = 0; i < strip.length; i++) { // Only check next 7 points (proven upper bound) for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < minDist; j++) { minDist = Math.min(minDist, distance(strip[i], strip[j])); } } return minDist; } return closestUtil(points);}// Points: [{x:2,y:3}, {x:12,y:30}, {x:40,y:50}, {x:5,y:1}]// Returns minimum distance between any two points// Time: O(n log² n), can be optimized to O(n log n)
11.5 Maximum Subarray Divide Conquer
Case
Location
Computation
Complexity
Left Half
Entirely in left subarray
Recursive call on left
T(n/2)
Right Half
Entirely in right subarray
Recursive call on right
T(n/2)
Crossing Middle
Spans across midpoint
Find max from mid to left + mid to right
O(n)
Total
Max of all three cases
max(left, right, cross)
O(n log n)
Example: Maximum subarray divide and conquer
function maxSubArrayDC(nums) { function maxCrossingSum(nums, left, mid, right) { // Left side of mid let leftSum = -Infinity; let sum = 0; for (let i = mid; i >= left; i--) { sum += nums[i]; leftSum = Math.max(leftSum, sum); } // Right side of mid let rightSum = -Infinity; sum = 0; for (let i = mid + 1; i <= right; i++) { sum += nums[i]; rightSum = Math.max(rightSum, sum); } return leftSum + rightSum; } function maxSubArrayHelper(nums, left, right) { // Base case: single element if (left === right) return nums[left]; const mid = Math.floor((left + right) / 2); // Divide const leftMax = maxSubArrayHelper(nums, left, mid); const rightMax = maxSubArrayHelper(nums, mid + 1, right); const crossMax = maxCrossingSum(nums, left, mid, right); // Conquer return Math.max(leftMax, rightMax, crossMax); } return maxSubArrayHelper(nums, 0, nums.length - 1);}// [-2,1,-3,4,-1,2,1,-5,4] -> 6 (subarray [4,-1,2,1])// Time: O(n log n), Space: O(log n)// Note: Kadane's algorithm is O(n), but this demonstrates D&C
11.6 Karatsuba Multiplication
Step
Formula
Multiplications
Insight
Standard Multiplication
Split into halves, 4 recursive mults
4
T(n) = 4T(n/2) + O(n) = O(n²)
Karatsuba Trick
Use (a+b)(c+d) to eliminate one mult
3
T(n) = 3T(n/2) + O(n) = O(n^1.58)
Key Formula
ac×10^n + ((a+b)(c+d) - ac - bd)×10^(n/2) + bd
3: ac, bd, (a+b)(c+d)
Trade multiplications for additions
Application
Large integer multiplication
Asymptotically faster
Used in cryptography, bignum libraries
Example: Karatsuba multiplication
function karatsuba(x, y) { // Base case: small numbers if (x < 10 || y < 10) { return x * y; } // Find the size of the numbers const n = Math.max(x.toString().length, y.toString().length); const half = Math.floor(n / 2); const divisor = Math.pow(10, half); // Split x and y const a = Math.floor(x / divisor); // High part of x const b = x % divisor; // Low part of x const c = Math.floor(y / divisor); // High part of y const d = y % divisor; // Low part of y // Three recursive multiplications (Karatsuba's trick) const ac = karatsuba(a, c); const bd = karatsuba(b, d); const ad_plus_bc = karatsuba(a + b, c + d) - ac - bd; // Combine results // x*y = ac*10^n + (ad+bc)*10^(n/2) + bd return ac * Math.pow(10, 2 * half) + ad_plus_bc * Math.pow(10, half) + bd;}// 1234 * 5678// Standard: 4 multiplications at each level// Karatsuba: 3 multiplications at each level// Result: 7006652// Time: O(n^log₂3) ≈ O(n^1.585) vs O(n²)
Example: String-based Karatsuba for very large numbers
function karatsubaString(x, y) { // Remove leading zeros x = x.replace(/^0+/, '') || '0'; y = y.replace(/^0+/, '') || '0'; // Base case if (x.length === 1 || y.length === 1) { return (parseInt(x) * parseInt(y)).toString(); } // Pad to same length const n = Math.max(x.length, y.length); x = x.padStart(n, '0'); y = y.padStart(n, '0'); const half = Math.floor(n / 2); // Split const a = x.slice(0, n - half); const b = x.slice(n - half); const c = y.slice(0, n - half); const d = y.slice(n - half); // Helper to add large numbers as strings function addStrings(num1, num2) { let result = ''; let carry = 0; let i = num1.length - 1; let j = num2.length - 1; while (i >= 0 || j >= 0 || carry) { const digit1 = i >= 0 ? parseInt(num1[i]) : 0; const digit2 = j >= 0 ? parseInt(num2[j]) : 0; const sum = digit1 + digit2 + carry; result = (sum % 10) + result; carry = Math.floor(sum / 10); i--; j--; } return result; } // Helper to subtract large numbers function subtractStrings(num1, num2) { // Simplified: assumes num1 >= num2 let result = ''; let borrow = 0; let i = num1.length - 1; let j = num2.length - 1; while (i >= 0) { let digit1 = parseInt(num1[i]); const digit2 = j >= 0 ? parseInt(num2[j]) : 0; digit1 -= borrow; if (digit1 < digit2) { digit1 += 10; borrow = 1; } else { borrow = 0; } result = (digit1 - digit2) + result; i--; j--; } return result.replace(/^0+/, '') || '0'; } // Three multiplications const ac = karatsubaString(a, c); const bd = karatsubaString(b, d); const abcd = karatsubaString(addStrings(a, b), addStrings(c, d)); const middle = subtractStrings(subtractStrings(abcd, ac), bd); // Combine with powers of 10 (append zeros) return addStrings( addStrings(ac + '0'.repeat(2 * half), middle + '0'.repeat(half)), bd );}// Can multiply arbitrarily large integers// "12345678901234567890" * "98765432109876543210"
Binary Tree: Natural recursion on left/right subtrees
Closest Pair: Geometric divide and conquer, O(n log n)
Max Subarray: Consider left, right, and crossing cases
Karatsuba: Reduce multiplications from 4 to 3, O(n^1.58)
Note: Divide and conquer achieves O(n log n) for many problems by breaking into smaller subproblems. Master theorem: T(n) = aT(n/b) + f(n). For merge sort: a=2, b=2, f(n)=O(n) → O(n log n). For Karatsuba: a=3, b=2 → O(n^log₂3) ≈ O(n^1.585).
Warning: Divide and conquer has recursion overhead - for small inputs, simple iterative solutions may be faster. Quick sort's O(n²) worst case occurs with poor pivot selection (already sorted array with first/last pivot). Use random pivot or median-of-3 for better performance. Merge sort requires O(n) extra space.
12. Recursion Patterns
12.1 Tree Recursion Patterns
Pattern
Structure
Complexity
Application
Single Branch
One recursive call per invocation
O(n) linear
Linked list traversal, linear search
Binary Tree
Two recursive calls (left, right)
O(2^h) exponential
Binary tree traversal, Fibonacci naive
N-ary Tree
N recursive calls for N children
O(N^h)
Directory traversal, game trees
Pruned Tree
Conditional recursion with early exit
Better than worst case
Backtracking, search with constraints
Example: Binary tree recursion
// Preorder traversalfunction preorder(root) { if (!root) return; console.log(root.val); // Process root preorder(root.left); // Recurse left preorder(root.right); // Recurse right}// Inorder traversalfunction inorder(root) { if (!root) return; inorder(root.left); console.log(root.val); inorder(root.right);}// Postorder traversalfunction postorder(root) { if (!root) return; postorder(root.left); postorder(root.right); console.log(root.val);}// Time: O(n), Space: O(h) recursion stack
Example: N-ary tree recursion
function traverseNary(root) { if (!root) return; // Process current node console.log(root.val); // Recurse on all children for (const child of root.children) { traverseNary(child); }}// Count nodes in N-ary treefunction countNodes(root) { if (!root) return 0; let count = 1; // Current node for (const child of root.children) { count += countNodes(child); } return count;}// Time: O(n), Space: O(h)
Example: Tree recursion with return value
// Find maximum value in binary treefunction findMax(root) { if (!root) return -Infinity; const leftMax = findMax(root.left); const rightMax = findMax(root.right); return Math.max(root.val, leftMax, rightMax);}// Check if tree is symmetricfunction isSymmetric(root) { function isMirror(left, right) { if (!left && !right) return true; if (!left || !right) return false; return left.val === right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left); } return !root || isMirror(root.left, root.right);}// Path sum existsfunction hasPathSum(root, targetSum) { if (!root) return false; // Leaf node if (!root.left && !root.right) { return root.val === targetSum; } return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}
function factorialTail(n, acc = 1) { if (n <= 1) return acc; // Tail recursive // No pending operations after recursion return factorialTail(n - 1, n * acc);}// With TCO optimization:// factorialTail(5, 1)// factorialTail(4, 5) // reuse frame// factorialTail(3, 20) // reuse frame// factorialTail(2, 60) // reuse frame// factorialTail(1, 120) // reuse frame// return 120// Space: O(1) with TCO// Without TCO: still O(n) in JavaScript
Example: Converting to iterative (guaranteed O(1) space)
// Tail recursive Fibonaccifunction fibTail(n, a = 0, b = 1) { if (n === 0) return a; if (n === 1) return b; return fibTail(n - 1, b, a + b);}// Iterative version (manual tail call elimination)function fibIterative(n) { if (n === 0) return 0; if (n === 1) return 1; let a = 0, b = 1; for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; } return b;}// Both O(n) time, iterative guaranteed O(1) space// fibTail depends on TCO support// Sum of array - tail recursivefunction sumTail(arr, index = 0, acc = 0) { if (index === arr.length) return acc; return sumTail(arr, index + 1, acc + arr[index]);}// Iterative equivalentfunction sumIterative(arr) { let sum = 0; for (const num of arr) { sum += num; } return sum;}
function fibMemo(n, memo = {}) { // Check cache if (n in memo) return memo[n]; // Base cases if (n <= 1) return n; // Compute and cache memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n];}// Alternatively with arrayfunction fibMemoArray(n) { const memo = Array(n + 1).fill(-1); function helper(n) { if (memo[n] !== -1) return memo[n]; if (n <= 1) return n; memo[n] = helper(n - 1) + helper(n - 2); return memo[n]; } return helper(n);}// Time: O(n), Space: O(n)// Each subproblem computed once!
Example: Climbing stairs memoized
function climbStairs(n) { const memo = {}; function climb(n) { if (n in memo) return memo[n]; if (n <= 2) return n; memo[n] = climb(n - 1) + climb(n - 2); return memo[n]; } return climb(n);}// Time: O(n), Space: O(n)// Without memoization: O(2^n)// Can take 1 or 2 steps at a time// How many ways to reach step n?// climb(n) = climb(n-1) + climb(n-2)
Mutual Recursion: Functions call each other, useful for state machines and parsers
Note:Memoization is critical for recursive problems with overlapping subproblems. Fibonacci naive: O(2^n), with memoization: O(n). Tail recursion optimization converts recursion to iteration internally, achieving O(1) space, but JavaScript engines may not guarantee TCO. When in doubt, manually convert to iteration.
Warning: Deep recursion can cause stack overflow. JavaScript typically allows ~10,000-50,000 frames. For very deep recursion, use iteration or trampolining. Memoization requires extra space - be mindful of memory constraints. In mutual recursion, ensure all functions have proper base cases to avoid infinite loops.
13. Dynamic Programming
13.1 0/1 Knapsack Space Optimization
Approach
Space
Technique
Trade-off
2D DP Table
O(n*W)
dp[i][w] = max value with first i items, capacity w
Straightforward, can reconstruct solution
1D DP Array
O(W)
Process items one by one, update in reverse
Space optimized, harder to reconstruct items
Reverse Iteration
Required for 1D
Prevents using updated values from same iteration
Critical for correctness
State Transition
Take or skip item
dp[w] = max(dp[w], dp[w-weight] + value)
Classic 0/1 knapsack formula
Example: 0/1 Knapsack 2D DP
function knapsack2D(weights, values, capacity) { const n = weights.length; // dp[i][w] = max value using first i items with capacity w const dp = Array(n + 1).fill(null) .map(() => Array(capacity + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let w = 0; w <= capacity; w++) { // Option 1: Don't take item i-1 dp[i][w] = dp[i - 1][w]; // Option 2: Take item i-1 (if fits) if (weights[i - 1] <= w) { dp[i][w] = Math.max( dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1] ); } } } return dp[n][capacity];}// weights=[1,3,4,5], values=[1,4,5,7], capacity=7// -> 9 (take items 1 and 3: values 4+5)// Time: O(n*W), Space: O(n*W)
Example: 0/1 Knapsack 1D optimized
function knapsack1D(weights, values, capacity) { const dp = Array(capacity + 1).fill(0); for (let i = 0; i < weights.length; i++) { // MUST iterate backwards! // Prevents using updated values from current iteration for (let w = capacity; w >= weights[i]; w--) { dp[w] = Math.max( dp[w], // Don't take item i dp[w - weights[i]] + values[i] // Take item i ); } } return dp[capacity];}// Same result: 9// Time: O(n*W), Space: O(W)// Key: Reverse iteration preserves previous row values
Example: Partition equal subset sum (0/1 knapsack variant)
function canPartition(nums) { const sum = nums.reduce((a, b) => a + b, 0); // If odd sum, can't partition equally if (sum % 2 !== 0) return false; const target = sum / 2; const dp = Array(target + 1).fill(false); dp[0] = true; // Base case: sum 0 is always achievable for (const num of nums) { // Iterate backwards (0/1 knapsack pattern) for (let j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } } return dp[target];}// [1,5,11,5] -> true (partition: [1,5,5] and [11])// [1,2,3,5] -> false// Time: O(n*sum), Space: O(sum)
13.2 Unbounded Knapsack Bottom Up
Difference from 0/1
Implementation
Reason
Application
Unlimited Items
Can use same item multiple times
Forward iteration in inner loop
Coin change, rod cutting
Forward Iteration
Use updated values in same iteration
Allows reusing same item
Different from 0/1's reverse iteration
State Transition
dp[w] = max(dp[w], dp[w-weight] + value)
Can revisit dp[w-weight] after update
Enables unlimited use
Space Optimization
1D array sufficient
Only need current state
O(W) space
Example: Unbounded knapsack
function unboundedKnapsack(weights, values, capacity) { const dp = Array(capacity + 1).fill(0); for (let i = 0; i < weights.length; i++) { // Forward iteration (key difference!) for (let w = weights[i]; w <= capacity; w++) { dp[w] = Math.max( dp[w], dp[w - weights[i]] + values[i] ); } } return dp[capacity];}// weights=[1,3,4], values=[15,20,25], capacity=4// Can use item multiple times// Best: take item 0 four times (15*4=60) or// take item 2 once (25)// Time: O(n*W), Space: O(W)
Example: Coin change (ways to make amount)
function change(amount, coins) { const dp = Array(amount + 1).fill(0); dp[0] = 1; // One way to make 0: use no coins for (const coin of coins) { // Forward iteration for unbounded for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount];}// amount=5, coins=[1,2,5]// Ways: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]// -> 4 ways// Time: O(n*amount), Space: O(amount)
Example: Rod cutting problem
function rodCutting(prices, length) { // prices[i] = price of rod of length i+1 const dp = Array(length + 1).fill(0); for (let len = 1; len <= length; len++) { for (let cut = 1; cut <= len; cut++) { // Try cutting piece of length 'cut' dp[len] = Math.max( dp[len], prices[cut - 1] + dp[len - cut] ); } } return dp[length];}// prices=[1,5,8,9,10,17,17,20], length=8// Best: cut into 2+6 for price 5+17=22// Time: O(n²), Space: O(n)
13.3 Longest Common Subsequence LCS
Concept
State Definition
Transition
Complexity
Subsequence
Characters in order, not necessarily consecutive
Different from substring (must be consecutive)
More flexible matching
DP Table
dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
2D table, bottom-up or top-down
O(m*n) time and space
Match Case
If s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Extend previous LCS by 1
Characters match
Mismatch Case
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Take best by skipping one character
Try both options
Example: Longest common subsequence
function longestCommonSubsequence(text1, text2) { const m = text1.length; const n = text2.length; // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1] const dp = Array(m + 1).fill(null) .map(() => Array(n + 1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { // Characters match: extend LCS dp[i][j] = dp[i - 1][j - 1] + 1; } else { // Characters don't match: take max dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n];}// "abcde", "ace" -> 3 (LCS = "ace")// "abc", "abc" -> 3 (LCS = "abc")// "abc", "def" -> 0 (no common subsequence)// Time: O(m*n), Space: O(m*n)
Example: LCS with path reconstruction
function lcsWithPath(text1, text2) { const m = text1.length; const n = text2.length; const dp = Array(m + 1).fill(null) .map(() => Array(n + 1).fill(0)); // Build DP table for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // Reconstruct LCS let i = m, j = n; const lcs = []; while (i > 0 && j > 0) { if (text1[i - 1] === text2[j - 1]) { lcs.unshift(text1[i - 1]); i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } return { length: dp[m][n], sequence: lcs.join('') };}// "ABCDGH", "AEDFHR"// -> {length: 3, sequence: "ADH"}
Example: Space-optimized LCS O(min(m,n))
function lcsSpaceOptimized(text1, text2) { // Ensure text1 is shorter for space efficiency if (text1.length > text2.length) { [text1, text2] = [text2, text1]; } const m = text1.length; const n = text2.length; let prev = Array(m + 1).fill(0); let curr = Array(m + 1).fill(0); for (let j = 1; j <= n; j++) { for (let i = 1; i <= m; i++) { if (text1[i - 1] === text2[j - 1]) { curr[i] = prev[i - 1] + 1; } else { curr[i] = Math.max(curr[i - 1], prev[i]); } } [prev, curr] = [curr, prev]; } return prev[m];}// Space: O(min(m,n)) instead of O(m*n)// Can't reconstruct path with this approach
13.4 Longest Increasing Subsequence LIS
Approach
Method
Time
Space
DP O(n²)
For each i, check all j < i
O(n²)
O(n)
Binary Search
Maintain tails array, binary search for position
O(n log n)
O(n)
DP State
dp[i] = length of LIS ending at index i
Must check all previous elements
Simple to understand
Tails Array
tails[i] = smallest tail of LIS of length i+1
Optimal for finding length only
Complex but efficient
Example: LIS with O(n²) DP
function lengthOfLIS(nums) { if (nums.length === 0) return 0; const dp = Array(nums.length).fill(1); for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp);}// [10,9,2,5,3,7,101,18]// dp = [1,1,1,2,2,3,4,4]// LIS: [2,3,7,101] or [2,5,7,101], length = 4// Time: O(n²), Space: O(n)
Example: LIS with binary search O(n log n)
function lengthOfLISOptimal(nums) { const tails = []; for (const num of nums) { // Binary search for position let left = 0, right = tails.length; while (left < right) { const mid = Math.floor((left + right) / 2); if (tails[mid] < num) { left = mid + 1; } else { right = mid; } } // Replace or append if (left === tails.length) { tails.push(num); } else { tails[left] = num; } } return tails.length;}// tails[i] = smallest ending value of LIS of length i+1// Time: O(n log n), Space: O(n)
Example: LIS with reconstruction
function lisWithPath(nums) { if (nums.length === 0) return []; const dp = Array(nums.length).fill(1); const prev = Array(nums.length).fill(-1); let maxLen = 1; let maxIndex = 0; for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; prev[i] = j; // Track predecessor } } if (dp[i] > maxLen) { maxLen = dp[i]; maxIndex = i; } } // Reconstruct LIS const lis = []; let idx = maxIndex; while (idx !== -1) { lis.unshift(nums[idx]); idx = prev[idx]; } return lis;}// [10,9,2,5,3,7,101,18]// -> [2,3,7,101] (one possible LIS)
Note: Key DP patterns: 0/1 Knapsack uses reverse iteration for 1D optimization, Unbounded Knapsack uses forward iteration to allow item reuse. LCS is fundamental for diff algorithms and bioinformatics. LIS has O(n²) DP solution and O(n log n) binary search optimization.
13.5 Coin Change Min Coins
Variant
State Definition
Transition
Base Case
Min Coins
dp[i] = min coins to make amount i
dp[i] = min(dp[i], dp[i-coin] + 1)
dp[0] = 0, others = Infinity
Count Ways
dp[i] = ways to make amount i
dp[i] += dp[i-coin]
dp[0] = 1, others = 0
Unbounded Type
Can use same coin multiple times
Forward iteration
Classic unbounded knapsack
Impossible Case
If dp[amount] remains Infinity
Return -1
No combination exists
Example: Coin change minimum coins
function coinChange(coins, amount) { const dp = Array(amount + 1).fill(Infinity); dp[0] = 0; // 0 coins needed for amount 0 for (const coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } return dp[amount] === Infinity ? -1 : dp[amount];}// coins=[1,2,5], amount=11// -> 3 (5+5+1)// coins=[2], amount=3// -> -1 (impossible)// Time: O(n*amount), Space: O(amount)
Example: Coin change with path
function coinChangeWithPath(coins, amount) { const dp = Array(amount + 1).fill(Infinity); const parent = Array(amount + 1).fill(-1); dp[0] = 0; for (let i = 1; i <= amount; i++) { for (const coin of coins) { if (coin <= i && dp[i - coin] + 1 < dp[i]) { dp[i] = dp[i - coin] + 1; parent[i] = coin; } } } if (dp[amount] === Infinity) return null; // Reconstruct path const result = []; let curr = amount; while (curr > 0) { result.push(parent[curr]); curr -= parent[curr]; } return result;}// coins=[1,2,5], amount=11// -> [5,5,1]
Example: Coin change II (count ways)
function change(amount, coins) { const dp = Array(amount + 1).fill(0); dp[0] = 1; // One way to make 0 // IMPORTANT: Iterate coins in outer loop // to avoid counting permutations for (const coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount];}// amount=5, coins=[1,2,5]// Ways: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]// -> 4 ways// If we iterate amount in outer loop, we get permutations instead!// Time: O(n*amount), Space: O(amount)
13.6 Palindromic Substrings Expand Centers
Approach
Method
Time
Advantage
DP 2D Table
dp[i][j] = is s[i..j] palindrome
O(n²)
Can query any substring
Expand Centers
Try each position as center, expand outward
O(n²)
Better space O(1), simpler code
Odd Length
Single character center
Expand while s[i-k] === s[i+k]
Center at index i
Even Length
Two character center
Expand while s[i] === s[i+1+k]
Center between i and i+1
Example: Count palindromic substrings
function countSubstrings(s) { let count = 0; function expandAroundCenter(left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { count++; left--; right++; } } for (let i = 0; i < s.length; i++) { // Odd length palindromes (center at i) expandAroundCenter(i, i); // Even length palindromes (center between i and i+1) expandAroundCenter(i, i + 1); } return count;}// "abc" -> 3 ("a", "b", "c")// "aaa" -> 6 ("a", "a", "a", "aa", "aa", "aaa")// Time: O(n²), Space: O(1)
Example: Longest palindromic substring
function longestPalindrome(s) { let start = 0; let maxLen = 0; function expandAroundCenter(left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { const len = right - left + 1; if (len > maxLen) { start = left; maxLen = len; } left--; right++; } } for (let i = 0; i < s.length; i++) { expandAroundCenter(i, i); // Odd expandAroundCenter(i, i + 1); // Even } return s.substring(start, start + maxLen);}// "babad" -> "bab" or "aba"// "cbbd" -> "bb"// Time: O(n²), Space: O(1)
Example: Palindromic substrings DP approach
function countSubstringsDP(s) { const n = s.length; const dp = Array(n).fill(null).map(() => Array(n).fill(false)); let count = 0; // Every single character is a palindrome for (let i = 0; i < n; i++) { dp[i][i] = true; count++; } // Check substrings of length 2 for (let i = 0; i < n - 1; i++) { if (s[i] === s[i + 1]) { dp[i][i + 1] = true; count++; } } // Check substrings of length 3+ for (let len = 3; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (s[i] === s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; count++; } } } return count;}// Same results as expand approach// Time: O(n²), Space: O(n²)
13.7 Edit Distance Levenshtein
Operation
Description
State Transition
Example
Insert
Add character to word1
dp[i][j] = dp[i][j-1] + 1
"abc" → "abdc" (insert 'd')
Delete
Remove character from word1
dp[i][j] = dp[i-1][j] + 1
"abc" → "ac" (delete 'b')
Replace
Change character in word1
dp[i][j] = dp[i-1][j-1] + 1
"abc" → "adc" (replace 'b' with 'd')
Match
Characters already equal
dp[i][j] = dp[i-1][j-1]
No operation needed
Example: Edit distance (Levenshtein distance)
function minDistance(word1, word2) { const m = word1.length; const n = word2.length; // dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1] const dp = Array(m + 1).fill(null) .map(() => Array(n + 1).fill(0)); // Base cases: convert empty string for (let i = 0; i <= m; i++) dp[i][0] = i; // Delete all for (let j = 0; j <= n; j++) dp[0][j] = j; // Insert all for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (word1[i - 1] === word2[j - 1]) { // Characters match, no operation needed dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min( dp[i - 1][j] + 1, // Delete dp[i][j - 1] + 1, // Insert dp[i - 1][j - 1] + 1 // Replace ); } } } return dp[m][n];}// "horse", "ros" -> 3// horse -> rorse (replace 'h' with 'r')// rorse -> rose (remove 'r')// rose -> ros (remove 'e')// Time: O(m*n), Space: O(m*n)
Example: Space-optimized edit distance
function minDistanceOptimized(word1, word2) { const m = word1.length; const n = word2.length; let prev = Array(n + 1).fill(0); let curr = Array(n + 1).fill(0); // Initialize base case for (let j = 0; j <= n; j++) prev[j] = j; for (let i = 1; i <= m; i++) { curr[0] = i; // Base case for current row for (let j = 1; j <= n; j++) { if (word1[i - 1] === word2[j - 1]) { curr[j] = prev[j - 1]; } else { curr[j] = Math.min( prev[j] + 1, // Delete curr[j - 1] + 1, // Insert prev[j - 1] + 1 // Replace ); } } [prev, curr] = [curr, prev]; } return prev[n];}// Same result, Space: O(n) instead of O(m*n)
Example: One edit distance
function isOneEditDistance(s, t) { const m = s.length; const n = t.length; // Length difference must be 0 or 1 if (Math.abs(m - n) > 1) return false; if (s === t) return false; // Must be exactly one edit let i = 0; // Find first difference while (i < Math.min(m, n) && s[i] === t[i]) { i++; } if (m === n) { // Replace: rest must match return s.slice(i + 1) === t.slice(i + 1); } else if (m < n) { // Insert into s: skip one char in t return s.slice(i) === t.slice(i + 1); } else { // Delete from s: skip one char in s return s.slice(i + 1) === t.slice(i); }}// "ab", "acb" -> true (insert 'c')// "cab", "ad" -> false (2 edits)// Time: O(n), Space: O(1)
13.8 Maximum Subarray Kadane Algorithm
Concept
Description
Formula
Complexity
Core Idea
At each position, extend or start new subarray
Either continue or restart
Greedy choice at each step
State
maxEndingHere = max sum ending at current position
max(nums[i], maxEndingHere + nums[i])
Local maximum
Global Max
Track best result seen so far
max(maxSoFar, maxEndingHere)
Answer
Performance
Single pass through array
O(n) time, O(1) space
Optimal solution
Example: Kadane's algorithm
function maxSubArray(nums) { let maxSoFar = nums[0]; let maxEndingHere = nums[0]; for (let i = 1; i < nums.length; i++) { // Either extend current subarray or start new maxEndingHere = Math.max( nums[i], maxEndingHere + nums[i] ); // Update global maximum maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar;}// [-2,1,-3,4,-1,2,1,-5,4]// maxEndingHere: [-2,1,-2,4,3,5,6,1,5]// -> 6 (subarray [4,-1,2,1])// Time: O(n), Space: O(1)
Example: Kadane with indices
function maxSubArrayWithIndices(nums) { let maxSoFar = nums[0]; let maxEndingHere = nums[0]; let start = 0, end = 0, tempStart = 0; for (let i = 1; i < nums.length; i++) { if (nums[i] > maxEndingHere + nums[i]) { maxEndingHere = nums[i]; tempStart = i; // New subarray starts } else { maxEndingHere = maxEndingHere + nums[i]; } if (maxEndingHere > maxSoFar) { maxSoFar = maxEndingHere; start = tempStart; end = i; } } return { sum: maxSoFar, subarray: nums.slice(start, end + 1) };}// [-2,1,-3,4,-1,2,1,-5,4]// -> {sum: 6, subarray: [4,-1,2,1]}
Example: Circular array maximum subarray
function maxSubarraySumCircular(nums) { function kadane(arr) { let maxSoFar = arr[0]; let maxEndingHere = arr[0]; for (let i = 1; i < arr.length; i++) { maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar; } // Case 1: Maximum subarray is in the middle (normal Kadane) const maxNormal = kadane(nums); // Case 2: Maximum subarray wraps around // Find minimum subarray, subtract from total const total = nums.reduce((a, b) => a + b, 0); const inverted = nums.map(x => -x); const maxInverted = kadane(inverted); const maxWrap = total + maxInverted; // total - minSubarray // Edge case: all negative numbers if (maxWrap === 0) return maxNormal; return Math.max(maxNormal, maxWrap);}// [5,-3,5] -> 10 (wrap: 5+5)// [1,-2,3,-2] -> 3 (normal)// Time: O(n), Space: O(n) for inverted array
Note:Coin Change is fundamental unbounded knapsack. Palindromes use expand-from-center for O(1) space or DP for substring queries. Edit Distance is essential for spell checkers and DNA sequencing. Kadane's Algorithm is the optimal O(n) solution for maximum subarray, can be adapted for 2D, circular arrays, and product variants.
13.9 House Robber State Transitions
Variant
Constraint
State
Transition
House Robber I
Linear array, can't rob adjacent
dp[i] = max money up to house i
max(dp[i-1], dp[i-2] + nums[i])
House Robber II
Circular array, first and last adjacent
Two cases: rob first or rob last
max(rob(0..n-2), rob(1..n-1))
House Robber III
Binary tree, can't rob parent and child
{rob: maxIfRob, skip: maxIfSkip}
Tree DP with two states per node
Space Optimization
Only need last 2 values
Two variables instead of array
O(1) space
Example: House robber I
function rob(nums) { if (nums.length === 0) return 0; if (nums.length === 1) return nums[0]; let prev2 = nums[0]; let prev1 = Math.max(nums[0], nums[1]); for (let i = 2; i < nums.length; i++) { const curr = Math.max( prev1, // Skip current house prev2 + nums[i] // Rob current house ); prev2 = prev1; prev1 = curr; } return prev1;}// [1,2,3,1] -> 4 (rob houses 0 and 2: 1+3=4)// [2,7,9,3,1] -> 12 (rob houses 0,2,4: 2+9+1=12)// Time: O(n), Space: O(1)
Example: House robber II (circular)
function robCircular(nums) { if (nums.length === 1) return nums[0]; if (nums.length === 2) return Math.max(nums[0], nums[1]); function robLinear(start, end) { let prev2 = 0, prev1 = 0; for (let i = start; i <= end; i++) { const curr = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; } // Case 1: Rob houses 0 to n-2 (exclude last) // Case 2: Rob houses 1 to n-1 (exclude first) return Math.max( robLinear(0, nums.length - 2), robLinear(1, nums.length - 1) );}// [2,3,2] -> 3 (can't rob both 0 and 2)// [1,2,3,1] -> 4 (rob 1 and 3)// Time: O(n), Space: O(1)
Example: House robber III (binary tree)
function robTree(root) { // Returns {rob: maxIfRobRoot, skip: maxIfSkipRoot} function dfs(node) { if (!node) return { rob: 0, skip: 0 }; const left = dfs(node.left); const right = dfs(node.right); // If we rob this node, can't rob children const rob = node.val + left.skip + right.skip; // If we skip this node, take max from children const skip = Math.max(left.rob, left.skip) + Math.max(right.rob, right.skip); return { rob, skip }; } const result = dfs(root); return Math.max(result.rob, result.skip);}// 3// / \// 2 3// \ \// 3 1// -> 7 (rob 3, 3, 1)// Time: O(n), Space: O(h) for recursion
13.10 DP on Trees Pattern
Pattern
State
Recurrence
Use Case
Tree DP
Compute value at node using children
Post-order traversal (children first)
Diameter, path sum, subtree properties
Multiple States
Track different scenarios per node
Return object/array with all states
Include/exclude node, different paths
Parent Info
Pass info down from parent
Pre-order or two-pass approach
Distance from root, parent values
Rerooting
Answer for each node as root
Two DFS: compute subtree, then reroot
Sum of distances to all nodes
Example: Binary tree diameter
function diameterOfBinaryTree(root) { let diameter = 0; function height(node) { if (!node) return 0; const leftHeight = height(node.left); const rightHeight = height(node.right); // Diameter through this node diameter = Math.max( diameter, leftHeight + rightHeight ); // Return height for parent return 1 + Math.max(leftHeight, rightHeight); } height(root); return diameter;}// 1// / \// 2 3// / \// 4 5// -> 3 (path 4-2-1-3 or 5-2-1-3)// Time: O(n), Space: O(h)
Example: Binary tree maximum path sum
function maxPathSum(root) { let maxSum = -Infinity; function maxGain(node) { if (!node) return 0; // Get max gain from children (ignore negative) const leftGain = Math.max(maxGain(node.left), 0); const rightGain = Math.max(maxGain(node.right), 0); // Path through current node const pathSum = node.val + leftGain + rightGain; maxSum = Math.max(maxSum, pathSum); // Return max gain through this node // (can only use one child) return node.val + Math.max(leftGain, rightGain); } maxGain(root); return maxSum;}// -10// / \// 9 20// / \// 15 7// -> 42 (path 15-20-7)// Time: O(n), Space: O(h)
Example: Count good nodes in tree
function goodNodes(root) { let count = 0; function dfs(node, maxSoFar) { if (!node) return; // Good node: value >= max on path from root if (node.val >= maxSoFar) { count++; maxSoFar = node.val; } dfs(node.left, maxSoFar); dfs(node.right, maxSoFar); } dfs(root, -Infinity); return count;}// 3// / \// 1 4// / / \// 3 1 5// -> 4 (nodes 3,3,4,5 are good)// Time: O(n), Space: O(h)
13.11 DP with Bitmask
Concept
Representation
Operations
Use Case
State Compression
Use bits to represent subset
Each bit = element included/excluded
Track visited states compactly
Check Bit
(mask >> i) & 1
Test if i-th element included
Query state
Set Bit
mask | (1 << i)
Include i-th element
Transition to new state
Clear Bit
mask & ~(1 << i)
Exclude i-th element
Remove from state
Example: Traveling salesman problem (TSP)
function tsp(dist) { const n = dist.length; const VISITED_ALL = (1 << n) - 1; // dp[mask][i] = min cost to visit cities in mask, ending at i const dp = Array(1 << n).fill(null) .map(() => Array(n).fill(Infinity)); dp[1][0] = 0; // Start at city 0 for (let mask = 0; mask <= VISITED_ALL; mask++) { for (let last = 0; last < n; last++) { if (!(mask & (1 << last))) continue; if (dp[mask][last] === Infinity) continue; for (let next = 0; next < n; next++) { if (mask & (1 << next)) continue; const newMask = mask | (1 << next); dp[newMask][next] = Math.min( dp[newMask][next], dp[mask][last] + dist[last][next] ); } } } // Find min cost ending at any city let result = Infinity; for (let i = 0; i < n; i++) { result = Math.min(result, dp[VISITED_ALL][i] + dist[i][0]); } return result;}// Time: O(2^n * n²), Space: O(2^n * n)
Example: Minimum cost to connect all points (Steiner tree)
function assignTasks(servers, tasks) { const n = servers.length; const m = tasks.length; // dp[mask] = min cost to assign tasks in mask const dp = Array(1 << m).fill(Infinity); dp[0] = 0; for (let mask = 0; mask < (1 << m); mask++) { if (dp[mask] === Infinity) continue; // Count assigned tasks const assigned = countBits(mask); if (assigned >= n) continue; for (let task = 0; task < m; task++) { if (mask & (1 << task)) continue; const newMask = mask | (1 << task); const cost = servers[assigned] * tasks[task]; dp[newMask] = Math.min( dp[newMask], dp[mask] + cost ); } } return dp[(1 << m) - 1];}function countBits(n) { let count = 0; while (n) { count += n & 1; n >>= 1; } return count;}// Time: O(2^m * m * n), Space: O(2^m)
Example: Partition into k equal sum subsets
function canPartitionKSubsets(nums, k) { const sum = nums.reduce((a, b) => a + b, 0); if (sum % k !== 0) return false; const target = sum / k; nums.sort((a, b) => b - a); if (nums[0] > target) return false; const n = nums.length; const dp = Array(1 << n).fill(-1); dp[0] = 0; for (let mask = 0; mask < (1 << n); mask++) { if (dp[mask] === -1) continue; for (let i = 0; i < n; i++) { if (mask & (1 << i)) continue; const newSum = dp[mask] + nums[i]; if (newSum > target) continue; const newMask = mask | (1 << i); if (dp[newMask] !== -1) continue; dp[newMask] = newSum % target; } } return dp[(1 << n) - 1] === 0;}// [4,3,2,3,5,2,1], k=4 -> true// Can partition into [5], [1,4], [2,3], [2,3]// Time: O(2^n * n), Space: O(2^n)
13.12 Interval DP Pattern
Pattern
State
Iteration Order
Example
Interval DP
dp[i][j] = answer for subarray/substring [i..j]
Increasing interval length
Optimal way to merge/split interval
Length Loop
Outer loop: interval length from 1 to n
Build small intervals first
Ensures subproblems solved
Split Point
Try all ways to split [i..j]
dp[i][j] = min/max over all k in [i..j]
Matrix chain, burst balloons
Complexity
Usually O(n³)
n² states, O(n) transition
Can optimize with monotonic queue
Example: Matrix chain multiplication
function matrixChainOrder(dims) { // dims[i] = dimensions of matrix i // Matrix i has dimensions dims[i-1] x dims[i] const n = dims.length - 1; // dp[i][j] = min multiplications for matrices i to j const dp = Array(n).fill(null) .map(() => Array(n).fill(0)); // len = chain length for (let len = 2; len <= n; len++) { for (let i = 0; i < n - len + 1; i++) { const j = i + len - 1; dp[i][j] = Infinity; // Try splitting at k for (let k = i; k < j; k++) { const cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]; dp[i][j] = Math.min(dp[i][j], cost); } } } return dp[0][n - 1];}// dims = [10, 20, 30, 40, 30]// Matrices: A(10x20), B(20x30), C(30x40), D(40x30)// Optimal: ((A*B)*C)*D = 30,000 multiplications// Time: O(n³), Space: O(n²)
Example: Burst balloons
function maxCoins(nums) { // Add virtual balloons with value 1 const arr = [1, ...nums, 1]; const n = arr.length; // dp[i][j] = max coins from bursting balloons (i+1..j-1) const dp = Array(n).fill(null) .map(() => Array(n).fill(0)); for (let len = 2; len < n; len++) { for (let left = 0; left < n - len; left++) { const right = left + len; // Try bursting k last in range (left+1..right-1) for (let k = left + 1; k < right; k++) { const coins = arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right]; dp[left][right] = Math.max( dp[left][right], coins ); } } } return dp[0][n - 1];}// [3,1,5,8] -> 167// Burst order: 1,5,3,8// 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167// Time: O(n³), Space: O(n²)
Example: Palindrome partitioning II
function minCut(s) { const n = s.length; // isPalin[i][j] = is s[i..j] palindrome const isPalin = Array(n).fill(null) .map(() => Array(n).fill(false)); // Build palindrome table for (let len = 1; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (len === 1) { isPalin[i][j] = true; } else if (len === 2) { isPalin[i][j] = s[i] === s[j]; } else { isPalin[i][j] = s[i] === s[j] && isPalin[i + 1][j - 1]; } } } // dp[i] = min cuts for s[0..i] const dp = Array(n).fill(Infinity); for (let i = 0; i < n; i++) { if (isPalin[0][i]) { dp[i] = 0; } else { for (let j = 0; j < i; j++) { if (isPalin[j + 1][i]) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } } return dp[n - 1];}// "aab" -> 1 (cut: "aa|b")// "a" -> 0 (already palindrome)// Time: O(n²), Space: O(n²)
Warning: Dynamic programming requires identifying optimal substructure and overlapping subproblems. Space optimization (2D→1D) is common but may prevent path reconstruction. For bitmask DP, limit to n≤20 due to exponential states. Interval DP typically needs O(n³) time - ensure n is manageable. Always verify base cases and state transitions carefully.
Summary: Dynamic Programming is solving complex problems by breaking them into overlapping subproblems. Key techniques: Knapsack (0/1 and Unbounded) for subset selection, LCS/LIS for sequence problems, Edit Distance for string transformations, Kadane for optimal subarrays, Tree DP for hierarchical structures, Bitmask DP for subset enumeration, and Interval DP for range optimization. Master state definition, transition formulas, and space optimization techniques.
14. Greedy Algorithm
14.1 Activity Selection Interval Scheduling
Aspect
Description
Complexity
Pattern
Select maximum number of non-overlapping activities by always choosing the activity that finishes earliest
O(n log n)
Key Insight
Sorting by end time and greedily selecting earliest-finishing compatible activity gives optimal solution
Proof by exchange
Approach
Sort intervals by end time, iterate and select if start ≥ last selected end
function activitySelection(activities) { // Sort by end time activities.sort((a, b) => a[1] - b[1]); const selected = [activities[0]]; let lastEnd = activities[0][1]; for (let i = 1; i < activities.length; i++) { const [start, end] = activities[i]; // Select if non-overlapping if (start >= lastEnd) { selected.push(activities[i]); lastEnd = end; } } return selected;}// Example: [[1,3], [2,5], [4,6], [6,8], [5,7], [8,9]]// After sorting by end: [[1,3], [2,5], [4,6], [5,7], [6,8], [8,9]]// Selected: [[1,3], [4,6], [6,8], [8,9]]const activities = [[1,3], [2,5], [4,6], [6,8], [5,7], [8,9]];console.log(activitySelection(activities)); // 4 activities
Note: Why sort by end time? If we sort by start time or duration, we might select a long activity that blocks many shorter ones. Earliest finish time ensures maximum room for future selections.
14.2 Jump Game Reachability
Variant
Problem
Greedy Strategy
Jump Game I
Can reach last index from index 0?
Track maximum reachable position, update at each step
Jump Game II
Minimum jumps to reach end
BFS-like approach: jump when current range ends, count levels
Key Insight
At each position, maximize reach; if current position unreachable, return false
O(n) time, O(1) space
Example: Jump Game I - Can Reach End
function canJump(nums) { let maxReach = 0; for (let i = 0; i < nums.length; i++) { // If current position is beyond max reach, can't proceed if (i > maxReach) return false; // Update max reachable position maxReach = Math.max(maxReach, i + nums[i]); // Early exit if can reach end if (maxReach >= nums.length - 1) return true; } return true;}console.log(canJump([2,3,1,1,4])); // trueconsole.log(canJump([3,2,1,0,4])); // false
Example: Jump Game II - Minimum Jumps
function minJumps(nums) { if (nums.length <= 1) return 0; let jumps = 0; let currentEnd = 0; // End of current jump range let farthest = 0; // Farthest we can reach for (let i = 0; i < nums.length - 1; i++) { // Update farthest reachable position farthest = Math.max(farthest, i + nums[i]); // When we reach end of current range, must jump if (i === currentEnd) { jumps++; currentEnd = farthest; // Early exit if can reach end if (currentEnd >= nums.length - 1) break; } } return jumps;}// Example: [2,3,1,1,4]// i=0: farthest=2, jump to range [1,2], jumps=1// i=1: farthest=4, i=2: reach end of range, jump to range [3,4], jumps=2console.log(minJumps([2,3,1,1,4])); // 2
14.3 Gas Station Circular Array
Concept
Description
Complexity
Problem
Find starting gas station to complete circular route, given gas[] and cost[] arrays
O(n) time
Greedy Insight
If total gas ≥ total cost, solution exists. Start from position where running tank never goes negative
One pass solution
Key Observation
If we can't reach station j from i, then any station between i and j also can't reach j
Skip entire segment
Example: Gas Station Circuit
function canCompleteCircuit(gas, cost) { let totalGas = 0, totalCost = 0; let tank = 0, start = 0; for (let i = 0; i < gas.length; i++) { totalGas += gas[i]; totalCost += cost[i]; tank += gas[i] - cost[i]; // If tank goes negative, can't start from 'start' // Try next position as new starting point if (tank < 0) { start = i + 1; tank = 0; } } // If total gas < total cost, no solution return totalGas >= totalCost ? start : -1;}const gas = [1,2,3,4,5];const cost = [3,4,5,1,2];console.log(canCompleteCircuit(gas, cost)); // 3// Starting at index 3: tank=4-1=3, then 3+5-2=6, then 6+1-3=4...
Note: The key greedy choice is: if we fail at position j starting from i, we skip all positions between i and j as potential starts, because they have even less fuel accumulated than position i.
14.4 Interval Scheduling Maximization
Problem Type
Strategy
Sorting Key
Max Non-overlapping
Select maximum count of intervals
Sort by end time (earliest finish)
Min Removal
Remove minimum intervals to make non-overlapping
Sort by end time, count overlaps to remove
Min Meeting Rooms
Minimum rooms needed for all meetings
Sort starts and ends separately, sweep line
Merge Intervals
Merge all overlapping intervals
Sort by start time, merge consecutive overlaps
Example: Minimum Interval Removals
function eraseOverlapIntervals(intervals) { if (intervals.length === 0) return 0; // Sort by end time intervals.sort((a, b) => a[1] - b[1]); let removals = 0; let lastEnd = intervals[0][1]; for (let i = 1; i < intervals.length; i++) { const [start, end] = intervals[i]; if (start < lastEnd) { // Overlapping - remove current interval removals++; // Keep the one with earlier end (already sorted) } else { // Non-overlapping - update end lastEnd = end; } } return removals;}console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1// Remove [1,3] to make all non-overlapping
Example: Minimum Meeting Rooms
function minMeetingRooms(intervals) { if (intervals.length === 0) return 0; 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, endPtr = 0; for (let i = 0; i < starts.length; i++) { // If meeting starts before earliest ending, need new room if (starts[i] < ends[endPtr]) { rooms++; } else { // A room becomes available endPtr++; } } return rooms;}console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2
14.5 Job Sequencing with Deadlines
Concept
Description
Approach
Problem
Given jobs with deadlines and profits, maximize profit by scheduling one job per unit time
Greedy selection
Strategy
Sort jobs by profit (descending), assign each to latest available slot before deadline
O(n²) or O(n log n)
Data Structure
Use array/set to track occupied time slots, or disjoint set for optimization
Union-Find for O(n log n)
Example: Job Sequencing Problem
function jobSequencing(jobs) { // jobs = [[id, deadline, profit], ...] // Sort by profit descending jobs.sort((a, b) => b[2] - a[2]); const maxDeadline = Math.max(...jobs.map(j => j[1])); const slots = new Array(maxDeadline).fill(null); let totalProfit = 0; const sequence = []; for (const [id, deadline, profit] of jobs) { // Find latest available slot before deadline for (let i = Math.min(deadline - 1, maxDeadline - 1); i >= 0; i--) { if (slots[i] === null) { slots[i] = id; totalProfit += profit; sequence.push(id); break; } } } return { totalProfit, sequence };}const jobs = [ ['a', 2, 100], ['b', 1, 19], ['c', 2, 27], ['d', 1, 25], ['e', 3, 15]];console.log(jobSequencing(jobs));// { totalProfit: 142, sequence: ['a', 'c', 'e'] }
Example: Job Sequencing with Disjoint Set (Optimized)
class DisjointSet { constructor(n) { this.parent = Array.from({length: n}, (_, i) => i); } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { this.parent[this.find(x)] = this.find(y); }}function jobSequencingOptimized(jobs) { jobs.sort((a, b) => b[2] - a[2]); const maxDeadline = Math.max(...jobs.map(j => j[1])); const ds = new DisjointSet(maxDeadline + 1); let totalProfit = 0; for (const [id, deadline, profit] of jobs) { // Find latest available slot const slot = ds.find(Math.min(deadline, maxDeadline)); if (slot > 0) { ds.union(slot, slot - 1); // Mark as occupied, point to previous totalProfit += profit; } } return totalProfit;}console.log(jobSequencingOptimized(jobs)); // 142
14.6 Greedy Choice Property
Property
Description
Verification
Greedy Choice
Locally optimal choice leads to globally optimal solution
Proof by exchange argument
Optimal Substructure
Optimal solution contains optimal solutions to subproblems
Required for correctness
Matroid Structure
Problem exhibits matroid properties (hereditary, exchange)
// Greedy works for fractional knapsack (not 0/1)function fractionalKnapsack(items, capacity) { // items = [[value, weight], ...] // Sort by value-to-weight ratio descending items.sort((a, b) => (b[0]/b[1]) - (a[0]/a[1])); let totalValue = 0; let remainingCapacity = capacity; for (const [value, weight] of items) { if (remainingCapacity === 0) break; // Take as much as possible const taken = Math.min(remainingCapacity, weight); totalValue += (value / weight) * taken; remainingCapacity -= taken; } return totalValue;}const items = [[60, 10], [100, 20], [120, 30]];console.log(fractionalKnapsack(items, 50)); // 240// Take all of item 2 (ratio=6), all of item 1 (ratio=5), // and 2/3 of item 3 (ratio=4) = 100 + 60 + 80 = 240
When Greedy Works
Activity Selection: Sort by end time, select earliest finish
Huffman Coding: Merge two smallest frequencies repeatedly
Prim's/Kruskal's MST: Add minimum weight edge that doesn't create cycle
Fractional Knapsack: Sort by value/weight ratio
Coin Change (canonical): Use largest denomination first
Warning: When Greedy Fails
0/1 Knapsack: Need DP, greedy gives wrong answer
Longest Path: NP-hard, greedy doesn't work
Non-canonical Coin Systems: e.g., {1,3,4}, greedy fails for 6
Traveling Salesman: Greedy gives approximation, not optimal
Example: Huffman Coding (Greedy Correctness)
class MinHeap { constructor() { this.heap = []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { if (this.heap.length === 1) return this.heap.pop(); const min = this.heap[0]; this.heap[0] = this.heap.pop(); this.bubbleDown(0); return min; } bubbleUp(i) { while (i > 0) { const p = Math.floor((i - 1) / 2); if (this.heap[p].freq <= this.heap[i].freq) break; [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; } } bubbleDown(i) { while (true) { let min = i; const left = 2 * i + 1, right = 2 * i + 2; if (left < this.heap.length && this.heap[left].freq < this.heap[min].freq) min = left; if (right < this.heap.length && this.heap[right].freq < this.heap[min].freq) min = right; if (min === i) break; [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]]; i = min; } } size() { return this.heap.length; }}function huffmanCoding(freqMap) { const heap = new MinHeap(); // Create leaf nodes for (const [char, freq] of Object.entries(freqMap)) { heap.push({ char, freq, left: null, right: null }); } // Build tree by merging two smallest while (heap.size() > 1) { const left = heap.pop(); const right = heap.pop(); heap.push({ char: null, freq: left.freq + right.freq, left, right }); } // Generate codes const codes = {}; function traverse(node, code = '') { if (node.char) { codes[node.char] = code || '0'; return; } if (node.left) traverse(node.left, code + '0'); if (node.right) traverse(node.right, code + '1'); } traverse(heap.pop()); return codes;}const freq = { 'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45 };console.log(huffmanCoding(freq));// { f: '0', c: '100', d: '101', a: '1100', b: '1101', e: '111' }
Note: To prove greedy correctness, use exchange argument: Assume optimal solution differs from greedy choice. Show you can exchange optimal's choice with greedy's without making solution worse. Repeat until greedy solution is reached, proving it's optimal.
Summary: Greedy Algorithm Pattern
Core Principle: Make locally optimal choice at each step, never backtrack
Activity Selection: Sort by end time, select earliest finish - maximizes remaining time
Jump Game: Track maximum reachable position; for min jumps, use BFS-like levels
Gas Station: If total gas ≥ cost, solution exists; start where tank never goes negative
Interval Scheduling: Various strategies depending on goal (max count, min rooms, min removals)
Job Sequencing: Sort by profit, assign to latest available slot before deadline
Verification: Prove greedy choice property and optimal substructure; use exchange argument
Key Insight: Greedy works when local optimum leads to global optimum - not all problems have this property
15. Bit Manipulation
15.1 Bitmasking Subset Enumeration
Concept
Technique
Formula/Pattern
Use Case
Subset as Bitmask
Represent subset using binary number
bit i set → element i included
Enumerate all 2n subsets
Iterate All Subsets
Loop from 0 to 2n-1
for (let mask = 0; mask < (1<<n); mask++)
Generate powerset efficiently
Check Bit Set
Test if bit i is set in mask
(mask >> i) & 1 or mask & (1<<i)
Determine element membership
Set Bit
Turn on bit i
mask | (1 << i)
Add element to subset
Clear Bit
Turn off bit i
mask & ~(1 << i)
Remove element from subset
Toggle Bit
Flip bit i
mask ^ (1 << i)
Add/remove element toggle
Example: Generate All Subsets Using Bitmask
function subsetsUsingBitmask(nums) { const n = nums.length; const result = []; // Iterate through all possible subsets (2^n) for (let mask = 0; mask < (1 << n); mask++) { const subset = []; // Check each bit position for (let i = 0; i < n; i++) { // If bit i is set, include nums[i] if ((mask >> i) & 1) { subset.push(nums[i]); } } result.push(subset); } return result;}console.log(subsetsUsingBitmask([1, 2, 3]));// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]// Mask representation:// 000 (0) → []// 001 (1) → [1]// 010 (2) → [2]// 011 (3) → [1,2]// 100 (4) → [3]// 101 (5) → [1,3]// 110 (6) → [2,3]// 111 (7) → [1,2,3]
Note: Bitmask subset enumeration is memory efficient (O(1) space for mask) and allows fast subset operations using bitwise operators. Perfect for problems with n ≤ 20 elements.
15.2 Subset Generation Powers of 2
Operation
Bitwise Formula
Example
Application
Count Subsets
2^n = 1 << n
n=3 → 8 subsets
Total number of subsets
Iterate Submasks
for (s = mask; s; s = (s-1) & mask)
Submasks of 101 → 101, 100, 001
Enumerate all submasks of mask
Power of 2 Check
n & (n-1) === 0
8 (1000) & 7 (0111) = 0
Detect exact power of 2
Lowest Set Bit
n & -n
12 (1100) → 4 (0100)
Extract rightmost 1-bit
Remove Lowest Bit
n & (n-1)
12 (1100) → 8 (1000)
Clear rightmost 1-bit
Example: Iterate All Submasks of a Mask
function iterateSubmasks(mask) { const submasks = []; // Standard submask iteration trick for (let s = mask; s > 0; s = (s - 1) & mask) { submasks.push(s); } // Don't forget empty submask (0) submasks.push(0); return submasks;}console.log(iterateSubmasks(5)); // 5 = 101 in binary// Output: [5, 4, 1, 0]// 101 → 100 → 001 → 000// Why this works:// mask = 101// s-1 flips all bits from rightmost 1// & mask keeps only bits that are in original mask// 101 - 1 = 100, 100 & 101 = 100// 100 - 1 = 011, 011 & 101 = 001// 001 - 1 = 000, 000 & 101 = 000 (loop ends)
Example: DP with Bitmask - Traveling Salesman Problem
function tsp(dist) { const n = dist.length; const VISITED_ALL = (1 << n) - 1; const dp = Array(1 << n).fill(null).map(() => Array(n).fill(Infinity)); // Start from city 0 dp[1][0] = 0; // Iterate all subsets for (let mask = 1; mask <= VISITED_ALL; mask++) { for (let last = 0; last < n; last++) { // If last city not in mask, skip if (!(mask & (1 << last))) continue; // Previous mask without last city const prevMask = mask ^ (1 << last); // Try all previous cities for (let prev = 0; prev < n; prev++) { if (prevMask & (1 << prev)) { dp[mask][last] = Math.min( dp[mask][last], dp[prevMask][prev] + dist[prev][last] ); } } } } // Return to city 0 from any city let minCost = Infinity; for (let i = 1; i < n; i++) { minCost = Math.min(minCost, dp[VISITED_ALL][i] + dist[i][0]); } return minCost;}const dist = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]];console.log(tsp(dist)); // 80
15.3 Counting Bits Brian Kernighan
Method
Algorithm
Time
Description
Brian Kernighan
n &= (n-1) in loop
O(k) k=set bits
Clears rightmost set bit each iteration
Naive Loop
Check each bit with >>
O(log n)
Loop through all 32/64 bits
Built-in
n.toString(2).split('1').length-1
O(log n)
Convert to binary string and count '1's
Lookup Table
Precompute counts for 0-255
O(1)
Split number into bytes, lookup each
Parallel Count
SWAR (SIMD Within A Register)
O(1)
Count bits in parallel using bit tricks
Example: Brian Kernighan's Algorithm
function countSetBits(n) { let count = 0; // Each iteration removes rightmost set bit while (n) { n &= (n - 1); count++; } return count;}console.log(countSetBits(13)); // 3 (1101 has 3 ones)console.log(countSetBits(7)); // 3 (0111 has 3 ones)// Trace for n=13 (1101):// Iteration 1: 1101 & 1100 = 1100, count=1// Iteration 2: 1100 & 1011 = 1000, count=2// Iteration 3: 1000 & 0111 = 0000, count=3// Why n & (n-1) removes rightmost set bit:// n = ...10110100// n-1 = ...10110011 (flips bits after rightmost 1)// & = ...10110000 (rightmost 1 cleared)
Example: Count Bits for All Numbers 0 to n (DP)
function countBits(n) { const result = new Array(n + 1); result[0] = 0; for (let i = 1; i <= n; i++) { // Key insight: count[i] = count[i >> 1] + (i & 1) // Right shift removes last bit, &1 checks if last bit was 1 result[i] = result[i >> 1] + (i & 1); } return result;}console.log(countBits(5)); // [0, 1, 1, 2, 1, 2]// 0: 0000 → 0 bits// 1: 0001 → 1 bit// 2: 0010 → 1 bit// 3: 0011 → 2 bits// 4: 0100 → 1 bit// 5: 0101 → 2 bits// Alternative DP: result[i] = result[i & (i-1)] + 1// i & (i-1) removes rightmost set bitfunction countBitsAlt(n) { const result = new Array(n + 1); result[0] = 0; for (let i = 1; i <= n; i++) { result[i] = result[i & (i - 1)] + 1; } return result;}
15.4 XOR Patterns Single Number
Property
Formula
Example
Application
Self XOR
a ^ a = 0
5 ^ 5 = 0
Cancel out duplicates
XOR with 0
a ^ 0 = a
5 ^ 0 = 5
Identity property
Commutative
a ^ b = b ^ a
3 ^ 5 = 5 ^ 3
Order doesn't matter
Associative
(a ^ b) ^ c = a ^ (b ^ c)
Can group any way
Chain XOR operations
Find Unique
result = a1 ^ a2 ^ ... ^ an
All pairs cancel
Find single non-duplicate
Swap Without Temp
a^=b; b^=a; a^=b
Swap two variables
In-place swap
Example: Single Number - Find Unique Element
function singleNumber(nums) { let result = 0; // XOR all numbers: duplicates cancel out for (const num of nums) { result ^= num; } return result;}console.log(singleNumber([4, 1, 2, 1, 2])); // 4// 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2// = 4 ^ (1 ^ 1) ^ (2 ^ 2)// = 4 ^ 0 ^ 0// = 4
Example: Single Number II - Element Appears Thrice
function singleNumberII(nums) { let ones = 0, twos = 0; for (const num of nums) { // Add to twos if already in ones twos |= ones & num; // XOR with ones ones ^= num; // Remove from both if appears 3 times const threes = ones & twos; ones &= ~threes; twos &= ~threes; } return ones;}console.log(singleNumberII([2, 2, 3, 2])); // 3// All numbers appear 3 times except one// Alternative using bit countingfunction singleNumberIIBitCount(nums) { let result = 0; // Count bits at each position for (let i = 0; i < 32; i++) { let sum = 0; for (const num of nums) { sum += (num >> i) & 1; } // If count not divisible by 3, unique number has this bit if (sum % 3 !== 0) { result |= (1 << i); } } return result;}
Example: Single Number III - Two Unique Elements
function singleNumberIII(nums) { // XOR all numbers: result = a ^ b (two unique numbers) let xorAll = 0; for (const num of nums) { xorAll ^= num; } // Find rightmost set bit (where a and b differ) const rightmostBit = xorAll & -xorAll; // Partition into two groups based on this bit let a = 0, b = 0; for (const num of nums) { if (num & rightmostBit) { a ^= num; } else { b ^= num; } } return [a, b];}console.log(singleNumberIII([1, 2, 1, 3, 2, 5])); // [3, 5]// Step 1: 1^2^1^3^2^5 = 3^5 = 6 (110)// Step 2: rightmost bit = 6 & -6 = 2 (010)// Step 3: Partition by bit 1// Group 1 (bit set): 2,3,2 → 3// Group 2 (bit not set): 1,1,5 → 5
15.5 Bit Tricks Fast Operations
Operation
Bit Trick
Equivalent
Use Case
Multiply by 2k
n << k
n * (2^k)
Fast multiplication by power of 2
Divide by 2k
n >> k
Math.floor(n / (2^k))
Fast division by power of 2
Check Even/Odd
n & 1
n % 2
0=even, 1=odd
Modulo Power of 2
n & (2^k - 1)
n % (2^k)
Fast modulo by power of 2
Absolute Value
(n ^ (n >> 31)) - (n >> 31)
Math.abs(n)
Branchless absolute value
Min of Two
b ^ ((a ^ b) & -(a < b))
Math.min(a, b)
Branchless minimum
Max of Two
a ^ ((a ^ b) & -(a < b))
Math.max(a, b)
Branchless maximum
Sign Function
(n >> 31) | ((-n) >>> 31)
-1 if n<0, 0 if n=0, 1 if n>0
Get sign without branches
Next Power of 2
Decrease by 1, set all bits right of MSB, add 1
Find next 2k ≥ n
Round up to power of 2
Isolate Rightmost 1
n & -n
Get lowest set bit
Extract least significant bit
Isolate Rightmost 0
~n & (n+1)
Get lowest unset bit
Find first zero bit
Turn Off Rightmost 1
n & (n-1)
Clear lowest set bit
Remove least significant bit
Turn On Rightmost 0
n | (n+1)
Set lowest unset bit
Set first zero bit
Example: Common Bit Tricks
// Check if power of 2function isPowerOfTwo(n) { return n > 0 && (n & (n - 1)) === 0;}// Get next power of 2function nextPowerOfTwo(n) { if (n <= 0) return 1; n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; return n + 1;}// Swap two numbers without temp variablefunction swap(a, b) { console.log(`Before: a=${a}, b=${b}`); a ^= b; b ^= a; a ^= b; console.log(`After: a=${a}, b=${b}`);}// Check if opposite signsfunction oppositeSign(a, b) { return (a ^ b) < 0;}console.log(isPowerOfTwo(16)); // trueconsole.log(nextPowerOfTwo(10)); // 16swap(5, 10); // Before: a=5, b=10, After: a=10, b=5console.log(oppositeSign(5, -3)); // trueconsole.log(oppositeSign(5, 3)); // false
Example: Fast Modulo and Multiplication
function fastOperations() { const n = 25; // Multiply by 8 (2^3) console.log(n << 3); // 200 (same as n * 8) // Divide by 4 (2^2) console.log(n >> 2); // 6 (same as Math.floor(n / 4)) // Check even/odd console.log(n & 1); // 1 (odd) console.log(24 & 1); // 0 (even) // Modulo 16 (2^4) console.log(n & 15); // 9 (same as n % 16, where 15 = 16-1) // Isolate rightmost set bit console.log(12 & -12); // 4 (1100 → 0100) // Remove rightmost set bit console.log(12 & 11); // 8 (1100 → 1000)}fastOperations();
Note: While bit tricks are fast, modern compilers often optimize standard operations automatically. Use bit tricks for clarity and specific algorithms (like counting bits, XOR problems), not general arithmetic unless profiling shows benefit.
15.6 Hamming Distance Bit Difference
Concept
Definition
Formula
Application
Hamming Distance
Number of positions where bits differ
countBits(x ^ y)
Measure bit difference between numbers
XOR for Difference
XOR highlights different bits
x ^ y gives 1 where bits differ
Find positions of difference
Total Hamming
Sum of all pairwise distances
Count contribution of each bit position
Analyze array bit differences
Hamming Weight
Number of 1-bits in number
countBits(n)
Also called population count
Example: Hamming Distance Between Two Numbers
function hammingDistance(x, y) { // XOR to find differing bits, then count them let xor = x ^ y; let distance = 0; // Brian Kernighan's algorithm while (xor) { xor &= (xor - 1); distance++; } return distance;}console.log(hammingDistance(1, 4)); // 2// 1 = 0001// 4 = 0100// XOR = 0101 (2 bits set)
Example: Total Hamming Distance of Array
function totalHammingDistance(nums) { let total = 0; const n = nums.length; // Check each bit position (0-31 for 32-bit integers) for (let bit = 0; bit < 32; bit++) { let countOnes = 0; // Count how many numbers have this bit set for (const num of nums) { if ((num >> bit) & 1) { countOnes++; } } // Numbers with 1 * numbers with 0 = pairs with different bit const countZeros = n - countOnes; total += countOnes * countZeros; } return total;}console.log(totalHammingDistance([4, 14, 2])); // 6// 4 = 0100// 14 = 1110// 2 = 0010//// Bit 0: [0,0,0] → 0*3 = 0// Bit 1: [0,1,1] → 1*2 = 2// Bit 2: [1,1,1] → 3*0 = 0// Bit 3: [0,1,0] → 1*2 = 2// Total = 0+2+0+2+2 = 6
15.7 Power of Two Detection
Check
Technique
Why It Works
Edge Cases
Is Power of 2
n > 0 && (n & (n-1)) === 0
Power of 2 has exactly one bit set
n=0 is NOT power of 2
Count Check
countBits(n) === 1
Exactly one 1-bit present
Slower but more explicit
Is Power of 4
(n & (n-1)) === 0 && (n & 0x55555555)
Power of 2 with bit at even position
0x55...5 = 01010101... pattern
Next Power of 2
Set all bits right of MSB, then add 1
Creates number like 2k-1, then +1
Handle n ≤ 0 specially
Example: Power of Two Variations
function isPowerOfTwo(n) { return n > 0 && (n & (n - 1)) === 0;}function isPowerOfFour(n) { // Must be power of 2 AND bit at even position (0,2,4,6,...) // 0x55555555 = 01010101010101010101010101010101 (bits at even positions) return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;}function nextPowerOfTwo(n) { if (n <= 1) return 1; // Decrease by 1 to handle exact powers of 2 n--; // Set all bits to the right of MSB n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Add 1 to get next power of 2 return n + 1;}console.log(isPowerOfTwo(16)); // true (10000)console.log(isPowerOfTwo(18)); // false (10010)console.log(isPowerOfFour(16)); // true (16 = 4^2)console.log(isPowerOfFour(8)); // false (8 = 2^3, not 4^k)console.log(nextPowerOfTwo(10)); // 16console.log(nextPowerOfTwo(16)); // 16 (already power of 2)
Example: Find Missing Power of Two
function missingPowerOfTwo(arr, n) { // Array contains all powers of 2 from 2^0 to 2^n except one // Use XOR to find missing let xor = 0; // XOR all elements in array for (const num of arr) { xor ^= num; } // XOR all powers of 2 from 0 to n for (let i = 0; i <= n; i++) { xor ^= (1 << i); } return xor; // Missing number}// Array has [1,2,8,16,32] - missing 4console.log(missingPowerOfTwo([1, 2, 8, 16, 32], 5)); // 4
function binaryToGray(binary) { return binary ^ (binary >> 1);}function grayToBinary(gray) { let binary = gray; // XOR with all right-shifted versions while (gray >>= 1) { binary ^= gray; } return binary;}// Alternative: recursive reflection methodfunction grayCodeRecursive(n) { if (n === 0) return [0]; if (n === 1) return [0, 1]; // Get previous Gray codes const prev = grayCodeRecursive(n - 1); const result = [...prev]; // Reflect and prepend 1 (add 2^(n-1)) const prefix = 1 << (n - 1); for (let i = prev.length - 1; i >= 0; i--) { result.push(prefix | prev[i]); } return result;}console.log(binaryToGray(6)); // 5 (110 → 101)console.log(grayToBinary(5)); // 6 (101 → 110)console.log(grayCodeRecursive(3)); // [0,1,3,2,6,7,5,4]
15.9 Gosper's Hack Next Combination
Technique
Purpose
How It Works
Complexity
Gosper's Hack
Generate next k-combination in lexicographic order
Find next number with same bit count
O(1) per iteration
Pattern
Iterate all n choose k combinations
Maintains same number of set bits
Total: O(C(n,k))
Formula
c = x & -x; r = x + c; x = (((r^x)>>2)/c)|r
Finds next combination efficiently
Bitwise arithmetic only
Example: Gosper's Hack - Enumerate k-Combinations
function gospersHack(n, k) { const combinations = []; // Start with k rightmost bits set: 2^k - 1 let set = (1 << k) - 1; const limit = 1 << n; while (set < limit) { combinations.push(set); // Gosper's hack: find next combination const c = set & -set; // Rightmost set bit const r = set + c; // Add to create carry set = (((r ^ set) >> 2) / c) | r; } return combinations;}// Get all 3-bit combinations from 5 bitsconsole.log(gospersHack(5, 3));// [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]// Binary representations all have exactly 3 bits set:// 00111 (7)// 01011 (11)// 01101 (13)// 01110 (14)// 10011 (19)// ...// Extract indices of set bitsfunction getIndices(mask) { const indices = []; let i = 0; while (mask) { if (mask & 1) indices.push(i); mask >>= 1; i++; } return indices;}const combs = gospersHack(5, 3);console.log(combs.map(getIndices));// [[0,1,2], [0,1,3], [0,2,3], [1,2,3], [0,1,4], ...]
Example: Apply Gosper's Hack to Array
function generateCombinations(arr, k) { const n = arr.length; const result = []; let set = (1 << k) - 1; const limit = 1 << n; while (set < limit) { const combination = []; // Extract elements based on set bits for (let i = 0; i < n; i++) { if ((set >> i) & 1) { combination.push(arr[i]); } } result.push(combination); // Next combination const c = set & -set; const r = set + c; set = (((r ^ set) >> 2) / c) | r; } return result;}console.log(generateCombinations(['a', 'b', 'c', 'd'], 2));// [['a','b'], ['a','c'], ['b','c'], ['a','d'], ['b','d'], ['c','d']]
15.10 Reverse Bits Swap Nibbles
Operation
Technique
Steps
Complexity
Reverse Bits
Swap bits from outside to inside
Swap 16-bit halves, 8-bit, 4-bit, 2-bit, 1-bit
O(log n) bits
Swap Adjacent Bits
Mask odd and even bits separately
((n & 0xAAAAAAAA)>>1)|((n & 0x55555555)<<1)
O(1)
Swap Nibbles
Swap 4-bit groups
((n & 0xF0F0F0F0)>>4)|((n & 0x0F0F0F0F)<<4)
O(1)
Swap Bytes
Swap 8-bit groups
((n & 0xFF00FF00)>>8)|((n & 0x00FF00FF)<<8)
O(1)
Lookup Table
Precompute reverse for 0-255
Split into bytes, lookup each, reassemble
O(1)
Example: Reverse 32-bit Integer
function reverseBits(n) { // Swap 16-bit halves n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16); // Swap 8-bit halves within each 16-bit group n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8); // Swap 4-bit nibbles within each 8-bit group n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4); // Swap 2-bit pairs within each 4-bit group n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2); // Swap adjacent bits n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1); return n >>> 0; // Convert to unsigned}console.log(reverseBits(43261596).toString(2)); // Input: 00000010100101000001111010011100 (43261596)// Output: 00111001011110000010100101000000 (964176192)
Note: Use >>> (unsigned right shift) instead of >> when working with bit reversal to avoid sign extension issues with negative numbers. The mask 0xAAAAAAAA = all odd bits, 0x55555555 = all even bits.
Summary: Bit Manipulation Pattern
Bitmasking: Use integers as sets - iterate 2n subsets with for (mask=0; mask<(1<<n); mask++)
Subset Generation: Powers of 2 are single bits; iterate submasks with s=(s-1)&mask
Counting Bits: Brian Kernighan's n&(n-1) removes rightmost bit - O(k) for k set bits
XOR Properties:a^a=0, a^0=a - perfect for finding unique elements in duplicates
Bit Tricks:n<<k = multiply by 2k, n>>k = divide by 2k, n&1 = check odd/even
Hamming Distance: Count bits in x^y - for arrays, count per bit position
Power of 2: Check with n>0 && (n&(n-1))===0 - exactly one bit set
Gray Code:binary^(binary>>1) - adjacent codes differ by 1 bit
Gosper's Hack: Generate next k-combination efficiently - maintains bit count
Key Insight: Bits can represent sets, states, and choices - enables compact DP and combinatorial algorithms
16. Matrix Traversal
16.1 Spiral Traversal Four Directions
Technique
Pattern
Boundary Management
Application
Layer-by-Layer
Process outer layer, then inner recursively
Track top, bottom, left, right boundaries
Spiral matrix traversal
Direction Array
dirs = [[0,1], [1,0], [0,-1], [-1,0]]
Right → Down → Left → Up cycle
Clockwise spiral movement
Visited Tracking
Mark cells as visited or use boundaries
Prevent revisiting cells
When cannot modify matrix
Shrinking Bounds
Adjust boundaries after each direction
top++, right--, bottom--, left++
Memory efficient approach
Example: Spiral Matrix Traversal
function spiralOrder(matrix) { if (!matrix.length) return []; const result = []; let top = 0, bottom = matrix.length - 1; let left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { // Move right along top row for (let col = left; col <= right; col++) { result.push(matrix[top][col]); } top++; // Move down along right column for (let row = top; row <= bottom; row++) { result.push(matrix[row][right]); } right--; // Move left along bottom row (if row exists) if (top <= bottom) { for (let col = right; col >= left; col--) { result.push(matrix[bottom][col]); } bottom--; } // Move up along left column (if column exists) if (left <= right) { for (let row = bottom; row >= top; row--) { result.push(matrix[row][left]); } left++; } } return result;}const matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]];console.log(spiralOrder(matrix));// [1,2,3,4,8,12,11,10,9,5,6,7]
Example: Generate Spiral Matrix
function generateMatrix(n) { const matrix = Array(n).fill(null).map(() => Array(n).fill(0)); let num = 1; let top = 0, bottom = n - 1; let left = 0, right = n - 1; while (top <= bottom && left <= right) { // Fill top row for (let col = left; col <= right; col++) { matrix[top][col] = num++; } top++; // Fill right column for (let row = top; row <= bottom; row++) { matrix[row][right] = num++; } right--; // Fill bottom row for (let col = right; col >= left; col--) { matrix[bottom][col] = num++; } bottom--; // Fill left column for (let row = bottom; row >= top; row--) { matrix[row][left] = num++; } left++; } return matrix;}console.log(generateMatrix(3));// [[1,2,3],// [8,9,4],// [7,6,5]]
Note: For spiral traversal, always check boundary conditions before the bottom-left and left-up movements to avoid duplicate elements in non-square matrices.
16.2 Search in Sorted Matrix Stairs
Matrix Type
Strategy
Starting Point
Time Complexity
Row & Column Sorted
Staircase search from top-right or bottom-left
Top-right: go left if target < current, down if >
O(m + n)
Fully Sorted
Binary search treating as 1D array
Map 1D index to 2D: [mid/n][mid%n]
O(log(m*n))
Each Row Sorted
Binary search on each row
Find valid row range, then binary search
O(m log n)
Example: Search in Row and Column Sorted Matrix
function searchMatrix(matrix, target) { if (!matrix.length || !matrix[0].length) return false; const m = matrix.length; const n = matrix[0].length; // Start from top-right corner let row = 0; let col = n - 1; while (row < m && col >= 0) { if (matrix[row][col] === target) { return true; } else if (matrix[row][col] > target) { col--; // Move left } else { row++; // Move down } } return false;}const matrix = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]];console.log(searchMatrix(matrix, 5)); // trueconsole.log(searchMatrix(matrix, 20)); // false// Why top-right works:// - Smallest in column (can only go down)// - Largest in row (can only go left)// - Eliminates entire row or column each step
Example: Search in Fully Sorted Matrix (2D Binary Search)
function searchMatrixFullySorted(matrix, target) { if (!matrix.length || !matrix[0].length) return false; const m = matrix.length; const n = matrix[0].length; let left = 0; let right = m * n - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); // Convert 1D index to 2D coordinates const row = Math.floor(mid / n); const col = mid % n; const midValue = matrix[row][col]; if (midValue === target) { return true; } else if (midValue < target) { left = mid + 1; } else { right = mid - 1; } } return false;}// Matrix where each row's first element > previous row's lastconst sortedMatrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];console.log(searchMatrixFullySorted(sortedMatrix, 3)); // true
function numIslands(grid) { if (!grid.length || !grid[0].length) return 0; const m = grid.length; const n = grid[0].length; let count = 0; function dfs(row, col) { // Base cases: out of bounds or water if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === '0') { return; } // Mark as visited grid[row][col] = '0'; // Explore 4 directions dfs(row + 1, col); // Down dfs(row - 1, col); // Up dfs(row, col + 1); // Right dfs(row, col - 1); // Left } for (let row = 0; row < m; row++) { for (let col = 0; col < n; col++) { if (grid[row][col] === '1') { count++; dfs(row, col); // Sink entire island } } } return count;}const grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']];console.log(numIslands(grid)); // 3
Example: Number of Islands (BFS)
function numIslandsBFS(grid) { if (!grid.length || !grid[0].length) return 0; const m = grid.length; const n = grid[0].length; let count = 0; const directions = [[0,1], [1,0], [0,-1], [-1,0]]; function bfs(startRow, startCol) { const queue = [[startRow, startCol]]; grid[startRow][startCol] = '0'; while (queue.length) { const [row, col] = queue.shift(); for (const [dr, dc] of directions) { const newRow = row + dr; const newCol = col + dc; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] === '1') { grid[newRow][newCol] = '0'; queue.push([newRow, newCol]); } } } } for (let row = 0; row < m; row++) { for (let col = 0; col < n; col++) { if (grid[row][col] === '1') { count++; bfs(row, col); } } } return count;}// Alternative: Use deque for better performance// queue.shift() is O(n), use index pointer or actual Queue
Example: Max Area of Island
function maxAreaOfIsland(grid) { const m = grid.length; const n = grid[0].length; let maxArea = 0; function dfs(row, col) { if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === 0) { return 0; } grid[row][col] = 0; // Mark visited // Count current cell + all connected cells return 1 + dfs(row + 1, col) + dfs(row - 1, col) + dfs(row, col + 1) + dfs(row, col - 1); } for (let row = 0; row < m; row++) { for (let col = 0; col < n; col++) { if (grid[row][col] === 1) { const area = dfs(row, col); maxArea = Math.max(maxArea, area); } } } return maxArea;}const islandGrid = [ [0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0]];console.log(maxAreaOfIsland(islandGrid)); // 6
Note: When counting islands, you can either use in-place modification (change grid values) or maintain a separate visited set. In-place is O(1) space but modifies input; visited set is O(m*n) space but preserves input.
16.4 Rotating Matrix In-place
Rotation
Strategy
Steps
Space
90° Clockwise
Transpose + Reverse each row
Swap [i][j] ↔ [j][i], then reverse rows
O(1)
90° Counter-Clockwise
Transpose + Reverse each column
Swap [i][j] ↔ [j][i], then reverse columns
O(1)
180°
Reverse rows + Reverse each row
Or apply 90° twice
O(1)
Layer by Layer
Rotate outer layers to inner
Four-way swap in concentric squares
O(1)
Example: Rotate Matrix 90° Clockwise
function rotate90Clockwise(matrix) { const n = matrix.length; // Step 1: Transpose (swap across diagonal) for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Step 2: Reverse each row for (let i = 0; i < n; i++) { matrix[i].reverse(); }}const mat1 = [ [1, 2, 3], [4, 5, 6], [7, 8, 9]];rotate90Clockwise(mat1);console.log(mat1);// [[7, 4, 1],// [8, 5, 2],// [9, 6, 3]]// Visualization:// Original: Transpose: Reverse rows:// 1 2 3 1 4 7 7 4 1// 4 5 6 → 2 5 8 → 8 5 2// 7 8 9 3 6 9 9 6 3
Example: Rotate 90° Counter-Clockwise
function rotate90CounterClockwise(matrix) { const n = matrix.length; // Step 1: Transpose for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Step 2: Reverse each column (reverse the array of rows) matrix.reverse();}// Alternative: Reverse rows first, then transposefunction rotate90CounterClockwiseAlt(matrix) { const n = matrix.length; // Reverse rows (flip vertically) matrix.reverse(); // Transpose for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } }}
Example: Layer-by-Layer Rotation
function rotateLayerByLayer(matrix) { const n = matrix.length; // Process concentric layers for (let layer = 0; layer < Math.floor(n / 2); layer++) { const first = layer; const last = n - 1 - layer; for (let i = first; i < last; i++) { const offset = i - first; // Save top const top = matrix[first][i]; // Left → Top matrix[first][i] = matrix[last - offset][first]; // Bottom → Left matrix[last - offset][first] = matrix[last][last - offset]; // Right → Bottom matrix[last][last - offset] = matrix[i][last]; // Top → Right matrix[i][last] = top; } }}const mat2 = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]];rotateLayerByLayer(mat2);console.log(mat2);// [[13, 9, 5, 1],// [14, 10, 6, 2],// [15, 11, 7, 3],// [16, 12, 8, 4]]
Rotation Formulas
90° CW: [i][j] → [j][n-1-i]
90° CCW: [i][j] → [n-1-j][i]
180°: [i][j] → [n-1-i][n-1-j]
Transpose: [i][j] ↔ [j][i]
Flip Horizontal: [i][j] ↔ [i][n-1-j]
Flip Vertical: [i][j] ↔ [n-1-i][j]
Note: Rotation Strategies
Transpose + Reverse: Simple, easy to remember
Layer by Layer: Direct rotation, good for understanding
Formula: Calculate new position directly
All are O(n²) time, O(1) space
16.5 Shortest Path in Grid A*
Algorithm
Strategy
Use Case
Time
BFS
Explore level-by-level, unweighted edges
Shortest path in unweighted grid
O(m*n)
Dijkstra
Priority queue, weighted edges
Shortest path with edge weights
O(m*n*log(m*n))
A* Search
Dijkstra + heuristic (Manhattan distance)
Faster path finding with goal knowledge
O(b^d) optimal
Bidirectional BFS
Search from both start and end
Reduce search space by half
O(b^(d/2))
Example: Shortest Path in Binary Grid (BFS)
function shortestPathBinaryMatrix(grid) { const n = grid.length; // Check if start or end is blocked if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1; // 8 directions (including diagonals) const dirs = [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1] ]; const queue = [[0, 0, 1]]; // [row, col, distance] grid[0][0] = 1; // Mark visited while (queue.length) { const [row, col, dist] = queue.shift(); // Reached destination if (row === n - 1 && col === n - 1) { return dist; } for (const [dr, dc] of dirs) { const newRow = row + dr; const newCol = col + dc; if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] === 0) { grid[newRow][newCol] = 1; // Mark visited queue.push([newRow, newCol, dist + 1]); } } } return -1; // No path found}const pathGrid = [ [0,0,0], [1,1,0], [1,1,0]];console.log(shortestPathBinaryMatrix(pathGrid)); // 4
Example: A* Search with Manhattan Heuristic
class MinHeap { constructor(compareFn) { this.heap = []; this.compare = compareFn || ((a, b) => a - b); } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { if (this.size() === 0) return null; if (this.size() === 1) return this.heap.pop(); const min = this.heap[0]; this.heap[0] = this.heap.pop(); this.bubbleDown(0); return min; } bubbleUp(i) { while (i > 0) { const p = Math.floor((i - 1) / 2); if (this.compare(this.heap[p], this.heap[i]) <= 0) break; [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; } } bubbleDown(i) { while (true) { let min = i; const left = 2 * i + 1; const right = 2 * i + 2; if (left < this.size() && this.compare(this.heap[left], this.heap[min]) < 0) { min = left; } if (right < this.size() && this.compare(this.heap[right], this.heap[min]) < 0) { min = right; } if (min === i) break; [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]]; i = min; } } size() { return this.heap.length; }}function aStarSearch(grid, start, end) { const m = grid.length; const n = grid[0].length; const [startR, startC] = start; const [endR, endC] = end; // Manhattan distance heuristic const heuristic = (r, c) => Math.abs(r - endR) + Math.abs(c - endC); // Priority queue: [f-score, g-score, row, col] const pq = new MinHeap((a, b) => a[0] - b[0]); pq.push([heuristic(startR, startC), 0, startR, startC]); const visited = new Set(); const dirs = [[0,1], [1,0], [0,-1], [-1,0]]; while (pq.size() > 0) { const [f, g, row, col] = pq.pop(); if (row === endR && col === endC) { return g; // Found shortest path } const key = `${row},${col}`; if (visited.has(key)) continue; visited.add(key); for (const [dr, dc] of dirs) { const newRow = row + dr; const newCol = col + dc; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] === 0 && !visited.has(`${newRow},${newCol}`)) { const newG = g + 1; const newH = heuristic(newRow, newCol); const newF = newG + newH; pq.push([newF, newG, newRow, newCol]); } } } return -1; // No path}const aStarGrid = [ [0,0,0,0], [1,1,0,1], [0,0,0,0], [0,1,1,0]];console.log(aStarSearch(aStarGrid, [0,0], [3,3])); // 6
Note: A* is optimal when heuristic is admissible (never overestimates) and consistent (satisfies triangle inequality). Manhattan distance is perfect for grid-based pathfinding.
16.6 Diagonal Traversal Pattern
Pattern
Direction
Formula
Use Case
Main Diagonal
Top-left to bottom-right
i === j
Primary diagonal elements
Anti-Diagonal
Top-right to bottom-left
i + j === n - 1
Secondary diagonal elements
Diagonal Order
Bottom-left to top-right
Group by i + j, alternate direction
Zigzag diagonal traversal
Parallel Diagonals
All diagonals from corners
Start from edges, move inward
Process all diagonals systematically
Example: Diagonal Traversal (Zigzag)
function findDiagonalOrder(matrix) { if (!matrix.length || !matrix[0].length) return []; const m = matrix.length; const n = matrix[0].length; const result = []; // Group elements by diagonal (i+j is constant for each diagonal) const diagonals = new Map(); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const diag = i + j; if (!diagonals.has(diag)) { diagonals.set(diag, []); } diagonals.get(diag).push(matrix[i][j]); } } // Process diagonals in order, alternating direction for (let d = 0; d < m + n - 1; d++) { const diagonal = diagonals.get(d); if (d % 2 === 0) { // Even diagonals: reverse (bottom-left to top-right) result.push(...diagonal.reverse()); } else { // Odd diagonals: normal (top-right to bottom-left) result.push(...diagonal); } } return result;}const diagMatrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9]];console.log(findDiagonalOrder(diagMatrix));// [1, 2, 4, 7, 5, 3, 6, 8, 9]// Visualization:// Diag 0: [1]// Diag 1: [2, 4] → reverse → [4, 2]// Diag 2: [3, 5, 7]// Diag 3: [6, 8] → reverse → [8, 6]// Diag 4: [9]
Example: Process All Diagonals
function traverseAllDiagonals(matrix) { const m = matrix.length; const n = matrix[0].length; const diagonals = []; // Top-left to bottom-right diagonals // Start from first row for (let startCol = 0; startCol < n; startCol++) { const diagonal = []; let row = 0, col = startCol; while (row < m && col < n) { diagonal.push(matrix[row][col]); row++; col++; } diagonals.push(diagonal); } // Start from first column (skip [0,0] already covered) for (let startRow = 1; startRow < m; startRow++) { const diagonal = []; let row = startRow, col = 0; while (row < m && col < n) { diagonal.push(matrix[row][col]); row++; col++; } diagonals.push(diagonal); } return diagonals;}const mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]];console.log(traverseAllDiagonals(mat));// [[1], [2,6], [3,7,11], [4,8,12], [5,10], [9]]
Example: Check Diagonal and Anti-Diagonal Sums
function diagonalSum(matrix) { const n = matrix.length; let sum = 0; for (let i = 0; i < n; i++) { sum += matrix[i][i]; // Main diagonal sum += matrix[i][n - 1 - i]; // Anti-diagonal } // If odd size, center element counted twice if (n % 2 === 1) { const mid = Math.floor(n / 2); sum -= matrix[mid][mid]; } return sum;}// Check if matrix is Toeplitz (diagonals have same value)function isToeplitzMatrix(matrix) { const m = matrix.length; const n = matrix[0].length; for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (matrix[i][j] !== matrix[i - 1][j - 1]) { return false; } } } return true;}const toeplitz = [ [1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]];console.log(isToeplitzMatrix(toeplitz)); // true
Summary: Matrix Traversal Pattern
Spiral Traversal: Track 4 boundaries (top, bottom, left, right) - shrink after each direction
Search Sorted Matrix: Staircase from top-right - go left if too big, down if too small - O(m+n)
Island Counting: DFS/BFS from each unvisited land cell - mark visited to avoid recount
Rotate 90° CW: Transpose matrix (swap [i][j] ↔ [j][i]) then reverse each row
Shortest Path BFS: Level-by-level exploration - optimal for unweighted grids
A* Search: Priority queue with f = g + h (cost + heuristic) - faster than Dijkstra
Diagonal Traversal: Group by i+j sum - alternate direction for zigzag pattern
Direction Arrays: Use [[0,1],[1,0],[0,-1],[-1,0]] for 4-way, add diagonals for 8-way
In-place Modification: Mark visited cells directly in grid for O(1) space vs visited set O(m*n)
Key Insight: Matrix problems often reduce to graph traversal - choose BFS for shortest path, DFS for exploration
17. String Matching
17.1 Longest Substring Without Repeating
Technique
Strategy
Data Structure
Time Complexity
Sliding Window
Expand right, shrink left when duplicate found
HashSet or HashMap for tracking
O(n)
HashMap Optimization
Store last seen index, jump left pointer
Map: char → last index
O(n)
Array Index
Use array for ASCII characters (256 size)
lastSeen[128] or [256]
O(n)
Example: Longest Substring Without Repeating Characters
function lengthOfLongestSubstring(s) { const seen = new Map(); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { const char = s[right]; // If char seen and within current window if (seen.has(char) && seen.get(char) >= left) { // Move left pointer past the previous occurrence left = seen.get(char) + 1; } // Update last seen position seen.set(char, right); // Update max length maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")console.log(lengthOfLongestSubstring("bbbbb")); // 1 ("b")console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")// Trace for "abcabcbb":// right=0, char='a': seen={a:0}, left=0, len=1// right=1, char='b': seen={a:0,b:1}, left=0, len=2// right=2, char='c': seen={a:0,b:1,c:2}, left=0, len=3// right=3, char='a': seen at 0, left=1, len=3// right=4, char='b': seen at 1, left=2, len=3// ...
Example: Alternative Using Set
function lengthOfLongestSubstringSet(s) { const window = new Set(); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { // Shrink window while duplicate exists while (window.has(s[right])) { window.delete(s[left]); left++; } window.add(s[right]); maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}// Using array for ASCII (faster for small character sets)function lengthOfLongestSubstringArray(s) { const lastSeen = new Array(128).fill(-1); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { const charCode = s.charCodeAt(right); // If char seen within current window if (lastSeen[charCode] >= left) { left = lastSeen[charCode] + 1; } lastSeen[charCode] = right; maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}
Note: The HashMap optimization jumps left directly to index + 1 of duplicate character, avoiding the need to remove characters one-by-one. This maintains O(n) with only one pass.
17.2 Longest Palindromic Substring Manacher
Algorithm
Approach
Key Idea
Complexity
Expand Around Center
Try each position as center, expand outward
Handle odd/even length separately
O(n²)
Dynamic Programming
dp[i][j] = is s[i..j] palindrome
Build from length 1 to n
O(n²)
Manacher's Algorithm
Use previously computed palindromes
Mirror property + special characters
O(n)
Example: Expand Around Center
function longestPalindrome(s) { if (!s || s.length < 1) return ""; let start = 0, maxLen = 0; function expandAroundCenter(left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } // Return length of palindrome return right - left - 1; } for (let i = 0; i < s.length; i++) { // Odd length palindrome (single center) const len1 = expandAroundCenter(i, i); // Even length palindrome (two centers) const len2 = expandAroundCenter(i, i + 1); const len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; // Calculate start position start = i - Math.floor((len - 1) / 2); } } return s.substring(start, start + maxLen);}console.log(longestPalindrome("babad")); // "bab" or "aba"console.log(longestPalindrome("cbbd")); // "bb"// Why expand around center works:// "racecar": center at 'e' → expands to full string// "abba": center between 'b' and 'b' → expands to full string
Example: Manacher's Algorithm (Linear Time)
function longestPalindromeManacher(s) { if (!s) return ""; // Transform string: "abc" → "^#a#b#c#$" // ^ and $ are sentinels to avoid boundary checks let T = "^"; for (const char of s) { T += "#" + char; } T += "#$"; const n = T.length; const P = new Array(n).fill(0); // P[i] = radius of palindrome centered at i let center = 0, right = 0; for (let i = 1; i < n - 1; i++) { // Mirror of i with respect to center const mirror = 2 * center - i; // If i is within right boundary, use mirror's value if (i < right) { P[i] = Math.min(right - i, P[mirror]); } // Try to expand palindrome centered at i while (T[i + P[i] + 1] === T[i - P[i] - 1]) { P[i]++; } // If palindrome centered at i extends past right, update center if (i + P[i] > right) { center = i; right = i + P[i]; } } // Find the longest palindrome let maxLen = 0; let centerIndex = 0; for (let i = 1; i < n - 1; i++) { if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; } } // Extract the longest palindrome from original string const start = Math.floor((centerIndex - maxLen) / 2); return s.substring(start, start + maxLen);}console.log(longestPalindromeManacher("babad")); // "bab" or "aba"// Manacher's key insight:// Use symmetry - palindrome's left half mirrors right half// If position i is inside palindrome centered at c,// then P[i] is at least min(P[mirror], right - i)
Note: Manacher's algorithm uses mirror property of palindromes and adds special characters (#) to handle both odd and even length palindromes uniformly. Achieves O(n) by avoiding redundant comparisons.
17.3 Minimum Window Substring Sliding
Technique
Strategy
Tracking
Complexity
Two Pointers
Expand right until valid, shrink left while valid
Count required vs found characters
O(n + m)
Character Frequency
Map to track required and current counts
Compare frequencies for validity
O(n)
Formed Counter
Count how many unique chars meet requirement
formed === required → valid window
O(n)
Example: Minimum Window Substring
function minWindow(s, t) { if (!s || !t || s.length < t.length) return ""; // Count characters in t const tCount = new Map(); for (const char of t) { tCount.set(char, (tCount.get(char) || 0) + 1); } const required = tCount.size; // Unique characters needed let formed = 0; // Unique characters in current window with desired frequency const windowCount = new Map(); let left = 0; let minLen = Infinity; let minStart = 0; for (let right = 0; right < s.length; right++) { const char = s[right]; windowCount.set(char, (windowCount.get(char) || 0) + 1); // Check if this character's frequency matches requirement if (tCount.has(char) && windowCount.get(char) === tCount.get(char)) { formed++; } // Try to shrink window while it's valid while (formed === required && left <= right) { // Update result if this window is smaller if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; } // Remove leftmost character const leftChar = s[left]; windowCount.set(leftChar, windowCount.get(leftChar) - 1); if (tCount.has(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) { formed--; } left++; } } return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);}console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"console.log(minWindow("a", "a")); // "a"console.log(minWindow("a", "aa")); // ""// Trace for "ADOBECODEBANC", "ABC":// Need: {A:1, B:1, C:1}// Window expands to "ADOBEC" - valid, try shrink// Window "DOBEC" - invalid (no A)// Continue expanding to "ODEBANC" - valid// Final answer: "BANC"
Example: Simplified Version with Character Array
function minWindowSimplified(s, t) { const tFreq = {}; for (const char of t) { tFreq[char] = (tFreq[char] || 0) + 1; } let required = Object.keys(tFreq).length; let formed = 0; const windowFreq = {}; let left = 0; let result = ""; let minLen = Infinity; for (let right = 0; right < s.length; right++) { const char = s[right]; windowFreq[char] = (windowFreq[char] || 0) + 1; if (tFreq[char] && windowFreq[char] === tFreq[char]) { formed++; } while (formed === required) { // Update result const windowSize = right - left + 1; if (windowSize < minLen) { minLen = windowSize; result = s.substring(left, right + 1); } // Shrink const leftChar = s[left]; if (tFreq[leftChar] && windowFreq[leftChar] === tFreq[leftChar]) { formed--; } windowFreq[leftChar]--; left++; } } return result;}// Variation: Find all start indicesfunction findSubstring(s, words) { if (!s || !words || words.length === 0) return []; const wordLen = words[0].length; const totalLen = wordLen * words.length; const wordCount = {}; for (const word of words) { wordCount[word] = (wordCount[word] || 0) + 1; } const result = []; for (let i = 0; i <= s.length - totalLen; i++) { const seen = {}; let j = 0; while (j < words.length) { const wordStart = i + j * wordLen; const word = s.substring(wordStart, wordStart + wordLen); if (!wordCount[word]) break; seen[word] = (seen[word] || 0) + 1; if (seen[word] > wordCount[word]) break; j++; } if (j === words.length) { result.push(i); } } return result;}
Window Validity Criteria
Formed Counter: Track unique chars meeting requirement
Valid Window: formed === required
Expand: Add right char, check if formed increases
Shrink: Remove left char, check if formed decreases
Update Result: Only when window is valid and smaller
Note: Key Pattern
Use two maps: required frequencies and window frequencies
Formed tracks chars with exact frequency match
Expand until valid, then shrink while maintaining validity
O(n) time: each character visited at most twice (right + left)
17.4 Anagram Grouping Pattern
Approach
Key Generation
Time
Space
Sorted String Key
Sort characters: "eat" → "aet"
O(n * k log k)
O(n * k)
Character Count Key
Frequency array: [1,0,0,1,1...] for "eat"
O(n * k)
O(n * k)
Prime Number Hash
Product of primes for each char
O(n * k)
O(n * k)
Example: Group Anagrams Using Sorted Key
function groupAnagrams(strs) { const groups = new Map(); for (const str of strs) { // Sort string to create key const key = str.split('').sort().join(''); if (!groups.has(key)) { groups.set(key, []); } groups.get(key).push(str); } return Array.from(groups.values());}console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));// [["eat","tea","ate"], ["tan","nat"], ["bat"]]// Why it works:// "eat" → sort → "aet"// "tea" → sort → "aet" (same key!)// "ate" → sort → "aet" (same key!)// All anagrams produce identical sorted string
Example: Using Character Count as Key
function groupAnagramsCharCount(strs) { const groups = new Map(); for (const str of strs) { // Create frequency array as key const count = new Array(26).fill(0); for (const char of str) { count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Convert array to string key const key = count.join('#'); if (!groups.has(key)) { groups.set(key, []); } groups.get(key).push(str); } return Array.from(groups.values());}// Example with detailed trace:// "eat" → [1,0,0,0,1,0,...,0,1] → "1#0#0#0#1#...#1"// "tea" → [1,0,0,0,1,0,...,0,1] → "1#0#0#0#1#...#1" (same!)// Alternative: Use object as mapfunction groupAnagramsObject(strs) { const groups = {}; for (const str of strs) { const count = new Array(26).fill(0); for (const char of str) { count[char.charCodeAt(0) - 97]++; } const key = count.toString(); if (!groups[key]) { groups[key] = []; } groups[key].push(str); } return Object.values(groups);}
Example: Related Problems - Valid Anagram
function isAnagram(s, t) { if (s.length !== t.length) return false; const count = new Array(26).fill(0); for (let i = 0; i < s.length; i++) { count[s.charCodeAt(i) - 97]++; count[t.charCodeAt(i) - 97]--; } return count.every(c => c === 0);}// Find all anagrams of p in sfunction findAnagrams(s, p) { const result = []; const pCount = new Array(26).fill(0); const windowCount = new Array(26).fill(0); // Count characters in p for (const char of p) { pCount[char.charCodeAt(0) - 97]++; } for (let i = 0; i < s.length; i++) { // Add new character to window windowCount[s.charCodeAt(i) - 97]++; // Remove old character if window too large if (i >= p.length) { windowCount[s.charCodeAt(i - p.length) - 97]--; } // Check if current window is anagram if (i >= p.length - 1 && arraysEqual(pCount, windowCount)) { result.push(i - p.length + 1); } } return result;}function arraysEqual(arr1, arr2) { for (let i = 0; i < arr1.length; i++) { if (arr1[i] !== arr2[i]) return false; } return true;}console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]
17.5 String Permutation Check
Problem Type
Technique
Key Insight
Complexity
Check if Permutation
Compare character frequencies
Same frequency → permutation possible
O(n)
Permutation in String
Sliding window of fixed size
Window matches pattern frequency
O(n)
Generate All Permutations
Backtracking or iterative
Swap elements recursively
O(n!)
Example: Check Permutation in String
function checkInclusion(s1, s2) { if (s1.length > s2.length) return false; const s1Count = new Array(26).fill(0); const windowCount = new Array(26).fill(0); // Count characters in s1 for (const char of s1) { s1Count[char.charCodeAt(0) - 97]++; } // Sliding window for (let i = 0; i < s2.length; i++) { // Add right character windowCount[s2.charCodeAt(i) - 97]++; // Remove left character if window too large if (i >= s1.length) { windowCount[s2.charCodeAt(i - s1.length) - 97]--; } // Check if window matches s1 if (i >= s1.length - 1 && matches(s1Count, windowCount)) { return true; } } return false;}function matches(arr1, arr2) { for (let i = 0; i < 26; i++) { if (arr1[i] !== arr2[i]) return false; } return true;}console.log(checkInclusion("ab", "eidbaooo")); // true ("ba" is permutation)console.log(checkInclusion("ab", "eidboaoo")); // false// Optimized: Use difference counterfunction checkInclusionOptimized(s1, s2) { if (s1.length > s2.length) return false; const count = new Array(26).fill(0); // Initialize: count s1 chars as positive, first window as negative for (let i = 0; i < s1.length; i++) { count[s1.charCodeAt(i) - 97]++; count[s2.charCodeAt(i) - 97]--; } let diff = 0; for (const c of count) { if (c !== 0) diff++; } if (diff === 0) return true; // Slide window for (let i = s1.length; i < s2.length; i++) { const rightIdx = s2.charCodeAt(i) - 97; const leftIdx = s2.charCodeAt(i - s1.length) - 97; // Add right if (count[rightIdx] === 0) diff++; count[rightIdx]--; if (count[rightIdx] === 0) diff--; // Remove left if (count[leftIdx] === 0) diff++; count[leftIdx]++; if (count[leftIdx] === 0) diff--; if (diff === 0) return true; } return false;}
Example: Generate All Permutations
function permute(nums) { const result = []; function backtrack(path, used) { if (path.length === nums.length) { result.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; path.push(nums[i]); used[i] = true; backtrack(path, used); path.pop(); used[i] = false; } } backtrack([], new Array(nums.length).fill(false)); return result;}console.log(permute([1, 2, 3]));// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]// String permutationsfunction permuteString(s) { const result = []; const chars = s.split(''); function swap(i, j) { [chars[i], chars[j]] = [chars[j], chars[i]]; } function permute(start) { if (start === chars.length) { result.push(chars.join('')); return; } for (let i = start; i < chars.length; i++) { swap(start, i); permute(start + 1); swap(start, i); // backtrack } } permute(0); return result;}console.log(permuteString("abc")); // ["abc", "acb", "bac", "bca", "cab", "cba"]
17.6 Longest Repeating Character Replacement
Concept
Strategy
Formula
Complexity
Sliding Window
Expand right, shrink if replacements > k
windowSize - maxFreq <= k
O(n)
Max Frequency
Track most frequent character in window
Others can be replaced to match max
O(26n) = O(n)
Valid Window
Window valid if replacements ≤ k
len - maxCount ≤ k
Check per iteration
Example: Longest Repeating Character Replacement
function characterReplacement(s, k) { const count = new Array(26).fill(0); let left = 0; let maxCount = 0; // Most frequent char in current window let maxLen = 0; for (let right = 0; right < s.length; right++) { const rightIdx = s.charCodeAt(right) - 65; // 'A' = 65 count[rightIdx]++; // Update max frequency in current window maxCount = Math.max(maxCount, count[rightIdx]); // Window size - max frequency = characters to replace // If more than k, shrink window while (right - left + 1 - maxCount > k) { const leftIdx = s.charCodeAt(left) - 65; count[leftIdx]--; left++; // Note: We don't update maxCount here (optimization) } maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}console.log(characterReplacement("ABAB", 2)); // 4 (replace both B → "AAAA")console.log(characterReplacement("AABABBA", 1)); // 4 (replace 1 B → "AABAA")// Trace for "ABAB", k=2:// Window "A": len=1, maxCount=1, replacements=0, valid// Window "AB": len=2, maxCount=1, replacements=1, valid// Window "ABA": len=3, maxCount=2, replacements=1, valid// Window "ABAB": len=4, maxCount=2, replacements=2, valid ✓// Result: 4 (can replace 2 B's to get "AAAA")
Example: Alternative with Explicit Max Count Update
function characterReplacementExplicit(s, k) { const count = {}; let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { count[s[right]] = (count[s[right]] || 0) + 1; // Get current max frequency const maxCount = Math.max(...Object.values(count)); // Shrink if invalid while (right - left + 1 - maxCount > k) { count[s[left]]--; if (count[s[left]] === 0) { delete count[s[left]]; } left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}// Related: Longest Substring with At Most K Distinct Charactersfunction lengthOfLongestSubstringKDistinct(s, k) { if (k === 0) return 0; const count = new Map(); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { count.set(s[right], (count.get(s[right]) || 0) + 1); // Shrink if more than k distinct characters while (count.size > k) { count.set(s[left], count.get(s[left]) - 1); if (count.get(s[left]) === 0) { count.delete(s[left]); } left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
Note: Key insight: windowSize - maxFreq = characters to replace. If this exceeds k, window is invalid. We don't need to update maxCount when shrinking because we only care about finding a larger window, not maintaining exact maxCount.
Summary: String Matching Pattern
Longest Substring No Repeat: Sliding window with HashMap - jump left to duplicate's next position - O(n)
Longest Palindrome: Expand around center O(n²), or Manacher's algorithm O(n) with mirror property
Minimum Window Substring: Two pointers with frequency maps - expand right until valid, shrink left while valid
Group Anagrams: Use sorted string or character count array as key - anagrams map to same key
Permutation Check: Fixed-size sliding window with frequency comparison - O(n) with 26-size array
Character Replacement: Window valid when (size - maxFreq) ≤ k - track most frequent character
Frequency Tracking: Use Map/Object for flexible chars, Array[26] for lowercase letters (faster)
Key Insight: Most string problems use sliding window or frequency maps - choose data structure based on character set size
18. Monotonic Stack Queue
18.1 Next Greater Element Stack
Concept
Stack Property
Operation
Complexity
Monotonic Stack
Elements in increasing/decreasing order
Pop elements that violate monotonicity
O(n)
Next Greater
Decreasing stack (top to bottom)
Pop smaller elements when larger found
O(n) amortized
Previous Greater
Same as next greater, scan left to right
Stack top is previous greater
O(n)
Circular Array
Process array twice (index % n)
Handle wraparound with modulo
O(n)
Example: Next Greater Element
function nextGreaterElement(nums) { const n = nums.length; const result = new Array(n).fill(-1); const stack = []; // Stores indices for (let i = 0; i < n; i++) { // Pop all smaller elements - current is their next greater while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { const index = stack.pop(); result[index] = nums[i]; } stack.push(i); } // Remaining elements have no next greater (-1) return result;}console.log(nextGreaterElement([4, 5, 2, 10, 8]));// [5, 10, 10, -1, -1]// Trace:// i=0, nums[0]=4: stack=[0]// i=1, nums[1]=5: pop 0 (4<5), result[0]=5, stack=[1]// i=2, nums[2]=2: stack=[1,2]// i=3, nums[3]=10: pop 2 (2<10), pop 1 (5<10), result[2]=10, result[1]=10, stack=[3]// i=4, nums[4]=8: stack=[3,4]// Final: result[3]=-1, result[4]=-1
Example: Next Greater Element II (Circular Array)
function nextGreaterElementsCircular(nums) { const n = nums.length; const result = new Array(n).fill(-1); const stack = []; // Process array twice to handle circular nature for (let i = 0; i < 2 * n; i++) { const num = nums[i % n]; while (stack.length > 0 && nums[stack[stack.length - 1]] < num) { const index = stack.pop(); result[index] = num; } // Only push indices in first pass if (i < n) { stack.push(i); } } return result;}console.log(nextGreaterElementsCircular([1, 2, 1])); // [2, -1, 2]// In circular: [1,2,1,1,2,1]// 1 → 2, 2 → -1 (largest), 1 → 2 (wraps around)console.log(nextGreaterElementsCircular([1, 2, 3, 4, 3])); // [2, 3, 4, -1, 4]
Example: Next Greater Element I (Subset Problem)
function nextGreaterElementSubset(nums1, nums2) { // nums1 is subset of nums2 const nextGreater = new Map(); const stack = []; // Build next greater map for nums2 for (const num of nums2) { while (stack.length > 0 && stack[stack.length - 1] < num) { nextGreater.set(stack.pop(), num); } stack.push(num); } // Map nums1 to their next greater in nums2 return nums1.map(num => nextGreater.get(num) ?? -1);}console.log(nextGreaterElementSubset([4, 1, 2], [1, 3, 4, 2]));// [-, 3, 3]// 4: no next greater → -1// 1: next greater is 3// 2: no next greater → -1
Note: Monotonic stack works in O(n) amortized time because each element is pushed and popped at most once. The stack maintains elements in decreasing order for "next greater" problems.
18.2 Next Smaller Element Pattern
Variation
Stack Order
Condition
Use Case
Next Smaller
Increasing stack
Pop when current < stack.top()
Find next smaller to the right
Previous Smaller
Increasing stack
Stack top after popping larger
Find previous smaller to the left
Next Greater
Decreasing stack
Pop when current > stack.top()
Find next greater to the right
Previous Greater
Decreasing stack
Stack top after popping smaller
Find previous greater to the left
Example: Next Smaller Element
function nextSmallerElement(nums) { const n = nums.length; const result = new Array(n).fill(-1); const stack = []; for (let i = 0; i < n; i++) { // Pop all greater elements - current is their next smaller while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) { const index = stack.pop(); result[index] = nums[i]; } stack.push(i); } return result;}console.log(nextSmallerElement([4, 5, 2, 10, 8]));// [2, 2, -1, 8, -1]// Previous and Next for all four variantsfunction findPrevNextGreaterSmaller(nums) { const n = nums.length; // Next Greater const nextGreater = new Array(n).fill(-1); let stack = []; for (let i = 0; i < n; i++) { while (stack.length && nums[stack[stack.length - 1]] < nums[i]) { nextGreater[stack.pop()] = nums[i]; } stack.push(i); } // Previous Greater const prevGreater = new Array(n).fill(-1); stack = []; for (let i = 0; i < n; i++) { while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) { stack.pop(); } if (stack.length) prevGreater[i] = nums[stack[stack.length - 1]]; stack.push(i); } // Next Smaller const nextSmaller = new Array(n).fill(-1); stack = []; for (let i = 0; i < n; i++) { while (stack.length && nums[stack[stack.length - 1]] > nums[i]) { nextSmaller[stack.pop()] = nums[i]; } stack.push(i); } // Previous Smaller const prevSmaller = new Array(n).fill(-1); stack = []; for (let i = 0; i < n; i++) { while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) { stack.pop(); } if (stack.length) prevSmaller[i] = nums[stack[stack.length - 1]]; stack.push(i); } return { nextGreater, prevGreater, nextSmaller, prevSmaller };}const arr = [3, 7, 8, 4];console.log(findPrevNextGreaterSmaller(arr));// nextGreater: [7, 8, -1, -1]// prevGreater: [-1, -1, -1, 8]// nextSmaller: [-1, 4, 4, -1]// prevSmaller: [-1, 3, 7, 3]
Monotonic Stack Patterns
Next Greater: Decreasing stack, pop smaller
Next Smaller: Increasing stack, pop greater
Previous Greater: Decreasing stack, check top
Previous Smaller: Increasing stack, check top
Key: Stack order determines what we find
Note: Stack Choice
Decreasing: Find greater elements
Increasing: Find smaller elements
Right scan: Next element
Left scan: Previous element
18.3 Largest Rectangle Histogram
Approach
Strategy
Key Insight
Complexity
Monotonic Stack
Track previous/next smaller for each bar
Width = right - left - 1, area = height * width
O(n)
Brute Force
For each bar, expand left and right
Find max width with current height
O(n²)
Divide & Conquer
Find min in range, recurse left/right
Max is min*width or in subproblem
O(n log n)
Example: Largest Rectangle in Histogram
function largestRectangleArea(heights) { const stack = []; // Stores indices let maxArea = 0; for (let i = 0; i <= heights.length; i++) { // Use 0 as sentinel to pop all remaining bars const h = i === heights.length ? 0 : heights[i]; // Pop bars taller than current while (stack.length > 0 && heights[stack[stack.length - 1]] > h) { const height = heights[stack.pop()]; // Width: from element after previous stack top to current-1 const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; maxArea = Math.max(maxArea, height * width); } stack.push(i); } return maxArea;}console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])); // 10// Trace for [2,1,5,6,2,3]:// i=0, h=2: stack=[0]// i=1, h=1: pop 0 (2>1), area=2*1=2, stack=[1]// i=2, h=5: stack=[1,2]// i=3, h=6: stack=[1,2,3]// i=4, h=2: // pop 3 (6>2), area=6*1=6// pop 2 (5>2), area=5*2=10 ✓// stack=[1,4]// i=5, h=3: stack=[1,4,5]// i=6, h=0: pop all, check areas
Example: Using Previous and Next Smaller Arrays
function largestRectangleAreaExplicit(heights) { const n = heights.length; // Find previous smaller (left boundary) const prevSmaller = new Array(n).fill(-1); let stack = []; for (let i = 0; i < n; i++) { while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) { stack.pop(); } if (stack.length) prevSmaller[i] = stack[stack.length - 1]; stack.push(i); } // Find next smaller (right boundary) const nextSmaller = new Array(n).fill(n); stack = []; for (let i = 0; i < n; i++) { while (stack.length && heights[stack[stack.length - 1]] > heights[i]) { nextSmaller[stack.pop()] = i; } stack.push(i); } // Calculate max area let maxArea = 0; for (let i = 0; i < n; i++) { const width = nextSmaller[i] - prevSmaller[i] - 1; const area = heights[i] * width; maxArea = Math.max(maxArea, area); } return maxArea;}// Visualization for [2,1,5,6,2,3]:// Index: 0 1 2 3 4 5// Heights: 2 1 5 6 2 3// PrevSmaller: -1 -1 1 2 1 4// NextSmaller: 1 6 4 4 6 6// // For i=2 (height=5):// left = prevSmaller[2] + 1 = 1 + 1 = 2// right = nextSmaller[2] - 1 = 4 - 1 = 3// width = 3 - 2 + 1 = 2// area = 5 * 2 = 10
Example: Maximal Rectangle in Binary Matrix
function maximalRectangle(matrix) { if (!matrix.length || !matrix[0].length) return 0; const m = matrix.length; const n = matrix[0].length; const heights = new Array(n).fill(0); let maxArea = 0; for (let row = 0; row < m; row++) { // Build histogram heights for current row for (let col = 0; col < n; col++) { if (matrix[row][col] === '1') { heights[col]++; } else { heights[col] = 0; } } // Find largest rectangle in current histogram maxArea = Math.max(maxArea, largestRectangleArea(heights)); } return maxArea;}const matrix = [ ['1','0','1','0','0'], ['1','0','1','1','1'], ['1','1','1','1','1'], ['1','0','0','1','0']];console.log(maximalRectangle(matrix)); // 6// Row 0: heights = [1,0,1,0,0]// Row 1: heights = [2,0,2,1,1]// Row 2: heights = [3,1,3,2,2] → max area = 6// Row 3: heights = [4,0,0,3,0]
Note: For histogram problems, the key insight is: for each bar, find the largest rectangle using this bar as the minimum height. Width is determined by previous and next smaller elements.
18.4 Sliding Window Maximum Deque
Approach
Data Structure
Property
Complexity
Monotonic Deque
Deque storing decreasing values
Front always has max in current window
O(n)
Brute Force
Scan window for max each time
Check all k elements per window
O(n*k)
Heap/Priority Queue
Max heap with lazy deletion
Extract max, ignore out-of-window
O(n log k)
Example: Sliding Window Maximum Using Deque
function maxSlidingWindow(nums, k) { const result = []; const deque = []; // Stores indices for (let i = 0; i < nums.length; i++) { // Remove elements outside current window while (deque.length && deque[0] < i - k + 1) { deque.shift(); } // Remove elements smaller than current (they can't be max) while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i); // Add max of current window to result if (i >= k - 1) { result.push(nums[deque[0]]); } } return result;}console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));// [3, 3, 5, 5, 6, 7]// Trace for k=3:// i=0: deque=[0], window=[1]// i=1: remove 0 (1<3), deque=[1], window=[1,3]// i=2: deque=[1,2], window=[1,3,-1], max=3// i=3: deque=[1,3], window=[3,-1,-3], max=3// i=4: remove 1,2,3 (all<5), deque=[4], window=[-1,-3,5], max=5// i=5: deque=[4,5], window=[-3,5,3], max=5// i=6: remove 4,5 (all<6), deque=[6], window=[5,3,6], max=6// i=7: remove 6 (6<7), deque=[7], window=[3,6,7], max=7
Example: Min and Max in Sliding Window
function minMaxSlidingWindow(nums, k) { const maxResult = []; const minResult = []; const maxDeque = []; // Decreasing deque for max const minDeque = []; // Increasing deque for min for (let i = 0; i < nums.length; i++) { // Remove out-of-window elements while (maxDeque.length && maxDeque[0] < i - k + 1) maxDeque.shift(); while (minDeque.length && minDeque[0] < i - k + 1) minDeque.shift(); // Maintain decreasing deque for max while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] < nums[i]) { maxDeque.pop(); } // Maintain increasing deque for min while (minDeque.length && nums[minDeque[minDeque.length - 1]] > nums[i]) { minDeque.pop(); } maxDeque.push(i); minDeque.push(i); if (i >= k - 1) { maxResult.push(nums[maxDeque[0]]); minResult.push(nums[minDeque[0]]); } } return { max: maxResult, min: minResult };}console.log(minMaxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));// max: [3, 3, 5, 5, 6, 7]// min: [-1, -3, -3, -3, 3, 3]
Note: Monotonic deque maintains a decreasing sequence of indices for max (increasing for min). Front has the maximum, back removes smaller elements that can never be maximum.
18.5 Stock Span Problem
Concept
Definition
Approach
Complexity
Stock Span
Number of consecutive days ≤ current price
Count days from current back to previous greater
O(n)
Monotonic Stack
Store indices of decreasing prices
Span = current index - previous greater index
O(n)
Brute Force
For each day, scan backwards
Count until price > current
O(n²)
Example: Stock Span
function calculateSpan(prices) { const n = prices.length; const span = new Array(n); const stack = []; // Stores indices for (let i = 0; i < n; i++) { // Pop all prices less than or equal to current while (stack.length && prices[stack[stack.length - 1]] <= prices[i]) { stack.pop(); } // Span = distance to previous greater (or start of array) span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1]; stack.push(i); } return span;}console.log(calculateSpan([100, 80, 60, 70, 60, 75, 85]));// [1, 1, 1, 2, 1, 4, 6]// Explanation:// Day 0 (100): no previous days, span=1// Day 1 (80): 80<100, span=1// Day 2 (60): 60<80, span=1// Day 3 (70): 70>60, includes day 2, span=2// Day 4 (60): 60<70, span=1// Day 5 (75): 75>60,60,70,60, includes days 2-4, span=4// Day 6 (85): 85>75,60,70,60,80, includes days 1-5, span=6
function trap(height) { if (!height.length) return 0; let left = 0, right = height.length - 1; let leftMax = 0, rightMax = 0; let water = 0; while (left < right) { if (height[left] < height[right]) { // Process left side if (height[left] >= leftMax) { leftMax = height[left]; } else { water += leftMax - height[left]; } left++; } else { // Process right side if (height[right] >= rightMax) { rightMax = height[right]; } else { water += rightMax - height[right]; } right--; } } return water;}console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6// Visualization:// ██// ██▓▓██▓██// ██▓███▓███// Water (▓) = 6 units
Example: Trapping Rain Water (Monotonic Stack)
function trapStack(height) { const stack = []; // Stores indices let water = 0; for (let i = 0; i < height.length; i++) { // Fill water when we find a taller bar while (stack.length && height[i] > height[stack[stack.length - 1]]) { const top = stack.pop(); if (!stack.length) break; const distance = i - stack[stack.length - 1] - 1; const boundedHeight = Math.min( height[i], height[stack[stack.length - 1]] ) - height[top]; water += distance * boundedHeight; } stack.push(i); } return water;}// DP approach with precomputed arraysfunction trapDP(height) { const n = height.length; if (n === 0) return 0; const leftMax = new Array(n); const rightMax = new Array(n); // Build left max array leftMax[0] = height[0]; for (let i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } // Build right max array rightMax[n - 1] = height[n - 1]; for (let i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } // Calculate water let water = 0; for (let i = 0; i < n; i++) { water += Math.min(leftMax[i], rightMax[i]) - height[i]; } return water;}console.log(trapStack([0,1,0,2,1,0,1,3,2,1,2,1])); // 6console.log(trapDP([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
Example: Trapping Rain Water II (2D Grid)
function trapRainWater2D(heightMap) { if (!heightMap.length || !heightMap[0].length) return 0; const m = heightMap.length; const n = heightMap[0].length; // Min heap: [height, row, col] const pq = new MinHeap((a, b) => a[0] - b[0]); const visited = Array(m).fill(null).map(() => Array(n).fill(false)); // Add all border cells to heap for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (i === 0 || i === m - 1 || j === 0 || j === n - 1) { pq.push([heightMap[i][j], i, j]); visited[i][j] = true; } } } const dirs = [[0,1], [1,0], [0,-1], [-1,0]]; let water = 0; let maxHeight = 0; while (pq.size() > 0) { const [height, row, col] = pq.pop(); maxHeight = Math.max(maxHeight, height); for (const [dr, dc] of dirs) { const newRow = row + dr; const newCol = col + dc; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) { visited[newRow][newCol] = true; // Water trapped = max seen height - current height if (heightMap[newRow][newCol] < maxHeight) { water += maxHeight - heightMap[newRow][newCol]; } pq.push([heightMap[newRow][newCol], newRow, newCol]); } } } return water;}// Helper MinHeap class (reuse from previous sections)class MinHeap { constructor(compareFn) { this.heap = []; this.compare = compareFn || ((a, b) => a - b); } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { if (this.size() === 0) return null; if (this.size() === 1) return this.heap.pop(); const min = this.heap[0]; this.heap[0] = this.heap.pop(); this.bubbleDown(0); return min; } bubbleUp(i) { while (i > 0) { const p = Math.floor((i - 1) / 2); if (this.compare(this.heap[p], this.heap[i]) <= 0) break; [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; } } bubbleDown(i) { while (true) { let min = i; const left = 2 * i + 1, right = 2 * i + 2; if (left < this.size() && this.compare(this.heap[left], this.heap[min]) < 0) min = left; if (right < this.size() && this.compare(this.heap[right], this.heap[min]) < 0) min = right; if (min === i) break; [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]]; i = min; } } size() { return this.heap.length; }}
Note: For trapping rain water, the key insight is: water at position i = min(leftMax, rightMax) - height[i]. Two pointers optimize space by tracking maxes on-the-fly without extra arrays.
Summary: Monotonic Stack Queue Pattern
Next Greater Element: Decreasing stack - pop smaller when larger found - O(n) amortized
Next Smaller Element: Increasing stack - pop greater when smaller found - mirror of next greater
Largest Rectangle: For each bar, find previous/next smaller - width between them, area = height * width
Sliding Window Max: Monotonic deque (decreasing) - front is max, remove out-of-window from front
Stock Span: Days since last greater price - use stack to track previous greater index
Trapping Rain Water: Two pointers with leftMax/rightMax - water = min(maxes) - height
Stack vs Deque: Stack for next/previous elements, Deque for sliding window max/min
Monotonic Property: Decreasing for greater, increasing for smaller - maintains order invariant
Key Insight: Each element pushed and popped once - amortized O(n) despite nested loops
19. Line Sweep Scanline
The line sweep algorithm processes events in sorted order, typically by position or time, maintaining an active state that updates as the sweep line moves. Commonly used for interval problems, geometric algorithms, and event-driven simulations.
19.1 Interval Merging Sweep Line
Approach
Strategy
Key Steps
Complexity
Sort + Merge
Sort by start time, merge overlaps
Compare current.end with next.start
O(n log n)
Event-based Sweep
Create start/end events, process sorted
Track active intervals count
O(n log n)
Interval Tree
Augmented BST for dynamic queries
Store max endpoint in each node
O(n log n + k)
Example: Merge Overlapping Intervals
function mergeIntervals(intervals) { if (!intervals.length) return []; // 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 last = merged[merged.length - 1]; const current = intervals[i]; // Check for overlap if (current[0] <= last[1]) { // Merge by extending the end time last[1] = Math.max(last[1], current[1]); } else { // No overlap, add new interval merged.push(current); } } return merged;}console.log(mergeIntervals([[1,3], [2,6], [8,10], [15,18]]));// [[1,6], [8,10], [15,18]]console.log(mergeIntervals([[1,4], [4,5]]));// [[1,5]]// Variation: Merge with gap tolerancefunction mergeWithGap(intervals, gap) { if (!intervals.length) return []; intervals.sort((a, b) => a[0] - b[0]); const merged = [intervals[0]]; for (let i = 1; i < intervals.length; i++) { const last = merged[merged.length - 1]; const current = intervals[i]; // Merge if gap is within tolerance if (current[0] - last[1] <= gap) { last[1] = Math.max(last[1], current[1]); } else { merged.push(current); } } return merged;}console.log(mergeWithGap([[1,2], [4,5], [7,9]], 1));// [[1,5], [7,9]] - gap of 1 allows [1,2] and [4,5] to merge
Example: Insert Interval
function insertInterval(intervals, newInterval) { const result = []; let i = 0; // Add all intervals before the new interval while (i < intervals.length && intervals[i][1] < newInterval[0]) { result.push(intervals[i]); i++; } // Merge overlapping intervals with new interval 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;}console.log(insertInterval([[1,3], [6,9]], [2,5]));// [[1,5], [6,9]]console.log(insertInterval([[1,2], [3,5], [6,7], [8,10], [12,16]], [4,8]));// [[1,2], [3,10], [12,16]]
Note: When merging intervals, always sort by start time first. Overlap exists when current.start <= previous.end. Merged end is max(previous.end, current.end).
19.2 Meeting Rooms Multiple Events
Problem Type
Approach
Key Insight
Complexity
Can Attend All
Sort and check adjacent overlaps
No overlap if sorted intervals don't touch
O(n log n)
Min Rooms Needed
Sweep line with start/end events
Max concurrent events = min rooms
O(n log n)
Free Time Intervals
Merge all busy times, find gaps
Gaps between merged intervals
O(n log n)
Example: Meeting Rooms I - Can Attend All
function canAttendMeetings(intervals) { if (!intervals.length) return true; // Sort by start time intervals.sort((a, b) => a[0] - b[0]); // Check for any overlap for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] < intervals[i - 1][1]) { return false; // Overlap detected } } return true;}console.log(canAttendMeetings([[0,30], [5,10], [15,20]])); // falseconsole.log(canAttendMeetings([[7,10], [2,4]])); // true
Example: Meeting Rooms II - Minimum Rooms
function minMeetingRooms(intervals) { if (!intervals.length) return 0; // Create separate arrays for starts and ends 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 maxRooms = 0; let startPtr = 0, endPtr = 0; // Sweep through all events while (startPtr < starts.length) { if (starts[startPtr] < ends[endPtr]) { // Meeting starts, need a room rooms++; maxRooms = Math.max(maxRooms, rooms); startPtr++; } else { // Meeting ends, free a room rooms--; endPtr++; } } return maxRooms;}console.log(minMeetingRooms([[0,30], [5,10], [15,20]])); // 2console.log(minMeetingRooms([[7,10], [2,4]])); // 1// Alternative: Using events with priorityfunction minMeetingRoomsEvents(intervals) { const events = []; for (const [start, end] of intervals) { events.push([start, 1]); // Start event events.push([end, -1]); // End event } // Sort by time, end events before start events at same time events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); let rooms = 0; let maxRooms = 0; for (const [time, delta] of events) { rooms += delta; maxRooms = Math.max(maxRooms, rooms); } return maxRooms;}console.log(minMeetingRoomsEvents([[0,30], [5,10], [15,20]])); // 2
Example: Employee Free Time
// Input: list of employee schedules (each is a list of intervals)function employeeFreeTime(schedules) { // Flatten all intervals const allIntervals = []; for (const schedule of schedules) { allIntervals.push(...schedule); } // Sort by start time allIntervals.sort((a, b) => a[0] - b[0]); // Merge all busy intervals const merged = [allIntervals[0]]; for (let i = 1; i < allIntervals.length; i++) { const last = merged[merged.length - 1]; const current = allIntervals[i]; if (current[0] <= last[1]) { last[1] = Math.max(last[1], current[1]); } else { merged.push(current); } } // 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;}console.log(employeeFreeTime([ [[1,3], [6,7]], [[2,4]], [[2,5], [9,12]]]));// [[5,6], [7,9]]// Explanation:// Employee 1: [1,3], [6,7]// Employee 2: [2,4]// Employee 3: [2,5], [9,12]// Merged busy: [1,5], [6,7], [9,12]// Free time: [5,6], [7,9]
Note: For minimum meeting rooms, the key insight is: max concurrent meetings equals the number of rooms needed. Use two-pointer sweep with sorted start/end times or event-based approach.
19.3 Skyline Problem Event Points
Component
Representation
Processing
Complexity
Critical Points
Building start/end x-coordinates
Track height changes at each x
O(n)
Active Heights
Multiset/heap of current building heights
Add on start, remove on end
O(log n) per event
Skyline Output
[x, height] when max height changes
Compare previous max with current max
O(n log n) total
Example: Skyline Problem
function getSkyline(buildings) { const events = []; // Create events: [x, isStart, height] for (const [left, right, height] of buildings) { events.push([left, true, height]); // Start event events.push([right, false, height]); // End event } // Sort events // - By x coordinate // - Start events before end events at same x // - Start events: taller buildings first // - End events: shorter buildings first events.sort((a, b) => { if (a[0] !== b[0]) return a[0] - b[0]; if (a[1] !== b[1]) return a[1] ? -1 : 1; return a[1] ? b[2] - a[2] : a[2] - b[2]; }); const result = []; const heights = new Map(); // height -> count heights.set(0, 1); // Ground level for (const [x, isStart, height] of events) { if (isStart) { heights.set(height, (heights.get(height) || 0) + 1); } else { const count = heights.get(height); if (count === 1) { heights.delete(height); } else { heights.set(height, count - 1); } } // Get current max height const maxHeight = Math.max(...heights.keys()); // Add to result if height changed if (!result.length || result[result.length - 1][1] !== maxHeight) { result.push([x, maxHeight]); } } return result;}console.log(getSkyline([[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]));// [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]// Optimized version using priority queueclass MaxHeap { constructor() { this.heap = []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } remove(val) { const idx = this.heap.indexOf(val); if (idx === -1) return; if (idx === this.heap.length - 1) { this.heap.pop(); return; } this.heap[idx] = this.heap.pop(); this.bubbleDown(idx); } peek() { return this.heap[0] || 0; } bubbleUp(i) { while (i > 0) { const p = Math.floor((i - 1) / 2); if (this.heap[p] >= this.heap[i]) break; [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; } } bubbleDown(i) { while (true) { let max = i; const left = 2 * i + 1, right = 2 * i + 2; if (left < this.heap.length && this.heap[left] > this.heap[max]) max = left; if (right < this.heap.length && this.heap[right] > this.heap[max]) max = right; if (max === i) break; [this.heap[i], this.heap[max]] = [this.heap[max], this.heap[i]]; i = max; } }}function getSkylineHeap(buildings) { const events = []; for (const [left, right, height] of buildings) { events.push([left, 'start', height]); events.push([right, 'end', height]); } events.sort((a, b) => { if (a[0] !== b[0]) return a[0] - b[0]; const order = { start: 0, end: 1 }; if (a[1] !== b[1]) return order[a[1]] - order[b[1]]; return a[1] === 'start' ? b[2] - a[2] : a[2] - b[2]; }); const result = []; const heap = new MaxHeap(); heap.push(0); for (const [x, type, height] of events) { const prevMax = heap.peek(); if (type === 'start') { heap.push(height); } else { heap.remove(height); } const currMax = heap.peek(); if (currMax !== prevMax) { result.push([x, currMax]); } } return result;}
Note: The skyline problem requires careful event sorting: start events before end events at same x, and for start events, process taller buildings first to avoid duplicate key points.
19.4 Rectangle Overlap Detection
Problem Type
Approach
Key Insight
Complexity
Two Rectangles
Check boundary conditions
Overlap if NOT separated in any axis
O(1)
N Rectangles (Pairs)
All pairs comparison
Check each pair for overlap
O(n²)
Area Union (Sweep Line)
Vertical sweep with active segments
Process x-events, merge y-intervals
O(n² log n)
Interval Tree 2D
Separate x and y interval trees
Query overlapping intervals in both dims
O(n log n + k)
Example: Rectangle Overlap (2 Rectangles)
// Rectangle represented as [x1, y1, x2, y2] (bottom-left, top-right)function isRectangleOverlap(rec1, rec2) { const [x1, y1, x2, y2] = rec1; const [x3, y3, x4, y4] = rec2; // Check if NOT overlapping (separated) // Separated if: rec1 is left of rec2 OR rec1 is right of rec2 // OR rec1 is below rec2 OR rec1 is above rec2 const separated = x2 <= x3 || x4 <= x1 || y2 <= y3 || y4 <= y1; return !separated;}console.log(isRectangleOverlap([0,0,2,2], [1,1,3,3])); // trueconsole.log(isRectangleOverlap([0,0,1,1], [1,0,2,1])); // false (touching but not overlapping)console.log(isRectangleOverlap([0,0,1,1], [2,2,3,3])); // false// Alternative: Check overlap directlyfunction isRectangleOverlapDirect(rec1, rec2) { const [x1, y1, x2, y2] = rec1; const [x3, y3, x4, y4] = rec2; // Overlap in both x and y dimensions const xOverlap = Math.max(x1, x3) < Math.min(x2, x4); const yOverlap = Math.max(y1, y3) < Math.min(y2, y4); return xOverlap && yOverlap;}
Example: Rectangle Area II (Union of Multiple Rectangles)
function rectangleArea(rectangles) { const MOD = 1e9 + 7; // Collect all unique x and y coordinates const xCoords = new Set(); const yCoords = new Set(); for (const [x1, y1, x2, y2] of rectangles) { xCoords.add(x1); xCoords.add(x2); yCoords.add(y1); yCoords.add(y2); } const xs = Array.from(xCoords).sort((a, b) => a - b); const ys = Array.from(yCoords).sort((a, b) => a - b); let totalArea = 0; // Coordinate compression: check each grid cell for (let i = 0; i < xs.length - 1; i++) { for (let j = 0; j < ys.length - 1; j++) { const x1 = xs[i], x2 = xs[i + 1]; const y1 = ys[j], y2 = ys[j + 1]; // Check if this cell is covered by any rectangle let covered = false; for (const [rx1, ry1, rx2, ry2] of rectangles) { if (rx1 <= x1 && x2 <= rx2 && ry1 <= y1 && y2 <= ry2) { covered = true; break; } } if (covered) { const area = (x2 - x1) * (y2 - y1); totalArea = (totalArea + area) % MOD; } } } return totalArea;}console.log(rectangleArea([[0,0,2,2], [1,0,2,3], [1,0,3,1]])); // 6// Optimized sweep line approachfunction rectangleAreaSweepLine(rectangles) { const MOD = 1e9 + 7; const events = []; // Create events for each rectangle for (const [x1, y1, x2, y2] of rectangles) { events.push([x1, y1, y2, 1]); // Start of rectangle events.push([x2, y1, y2, -1]); // End of rectangle } // Sort by x coordinate events.sort((a, b) => a[0] - b[0]); let totalArea = 0; let prevX = 0; const active = []; // [y1, y2, count] for (const [x, y1, y2, type] of events) { // Calculate area for previous x range if (active.length > 0) { const yLength = getTotalYLength(active); totalArea = (totalArea + (x - prevX) * yLength) % MOD; } // Update active intervals if (type === 1) { active.push([y1, y2]); } else { const idx = active.findIndex(([a, b]) => a === y1 && b === y2); active.splice(idx, 1); } prevX = x; } return totalArea;}function getTotalYLength(intervals) { if (!intervals.length) return 0; // Sort and merge intervals const sorted = intervals.slice().sort((a, b) => a[0] - b[0]); const merged = [sorted[0]]; for (let i = 1; i < sorted.length; i++) { const last = merged[merged.length - 1]; const curr = sorted[i]; if (curr[0] <= last[1]) { last[1] = Math.max(last[1], curr[1]); } else { merged.push(curr); } } return merged.reduce((sum, [y1, y2]) => sum + (y2 - y1), 0);}
Note: Rectangle overlap: two rectangles overlap if they are NOT separated in both x and y dimensions. For union area of multiple rectangles, use coordinate compression or sweep line with interval merging.
19.5 Event-driven Processing Pattern
Pattern
Event Types
Processing Order
Use Case
Timeline Events
Start/End events with timestamps
Sort by time, process sequentially
Meeting rooms, resource allocation
Priority Events
Events with importance/urgency
Sort by priority, then time
Task scheduling, CPU scheduling
Geometric Events
Points, lines, rectangles
Sweep line in spatial order
Skyline, closest pair, intersections
State Transition
Events that change system state
Maintain active state, update on events
Finite state machines, simulations
Example: Task Scheduler with Cooldown
// Given tasks and cooldown n, find minimum intervals neededfunction leastInterval(tasks, n) { // Count frequency of each task const freq = new Map(); for (const task of tasks) { freq.set(task, (freq.get(task) || 0) + 1); } // Get max frequency const maxFreq = Math.max(...freq.values()); // Count how many tasks have max frequency const maxCount = Array.from(freq.values()).filter(f => f === maxFreq).length; // Calculate minimum intervals // Pattern: A _ _ A _ _ A (for n=2, freq=3) // Intervals = (maxFreq - 1) * (n + 1) + maxCount const minIntervals = (maxFreq - 1) * (n + 1) + maxCount; // Can't be less than total tasks return Math.max(minIntervals, tasks.length);}console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8// A -> B -> idle -> A -> B -> idle -> A -> Bconsole.log(leastInterval(['A','A','A','B','B','B'], 0)); // 6// A -> B -> A -> B -> A -> Bconsole.log(leastInterval(['A','A','A','A','A','A','B','C','D','E','F','G'], 2)); // 16// A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
Example: Car Fleet (Event-driven)
function carFleet(target, position, speed) { const n = position.length; if (n === 0) return 0; // Create cars with their arrival times const cars = position.map((pos, i) => ({ pos, time: (target - pos) / speed[i] })); // Sort by starting position (descending - closest to target first) cars.sort((a, b) => b.pos - a.pos); let fleets = 0; let slowestTime = 0; // Process cars from closest to target for (const car of cars) { // If this car takes longer, it forms a new fleet if (car.time > slowestTime) { fleets++; slowestTime = car.time; } // Otherwise, it catches up to the previous fleet } return fleets;}console.log(carFleet(12, [10,8,0,5,3], [2,4,1,1,3])); // 3// Explanation:// Car at position 10, speed 2: time = (12-10)/2 = 1// Car at position 8, speed 4: time = (12-8)/4 = 1// Car at position 5, speed 1: time = (12-5)/1 = 7// Car at position 3, speed 3: time = (12-3)/3 = 3// Car at position 0, speed 1: time = (12-0)/1 = 12//// Sorted by position: [10,8,5,3,0]// Times: [1,1,7,3,12]// Fleet 1: Cars at 10,8 (both arrive at time 1)// Fleet 2: Car at 5 (arrives at time 7, catches car at 3)// Fleet 3: Car at 0 (arrives at time 12, slowest)
Example: The Earliest Moment When Everyone Becomes Friends
// Union-Find for connectivityclass UnionFind { constructor(n) { this.parent = Array(n).fill(0).map((_, i) => i); this.rank = Array(n).fill(1); this.components = n; } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // Path compression } return this.parent[x]; } union(x, y) { const rootX = this.find(x); const rootY = this.find(y); if (rootX === rootY) return false; // Union by rank if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else { this.parent[rootY] = rootX; this.rank[rootX]++; } this.components--; return true; } isConnected() { return this.components === 1; }}function earliestAcq(logs, n) { // Sort logs by timestamp logs.sort((a, b) => a[0] - b[0]); const uf = new UnionFind(n); // Process events in chronological order for (const [timestamp, x, y] of logs) { uf.union(x, y); // Check if all are connected if (uf.isConnected()) { return timestamp; } } return -1; // Not everyone becomes friends}console.log(earliestAcq([ [20190101,0,1], [20190104,3,4], [20190107,2,3], [20190211,1,5], [20190224,2,4], [20190301,0,3], [20190312,1,2], [20190322,4,5]], 6)); // 20190301// Explanation: At timestamp 20190301, everyone becomes connected
Note: Event-driven processing follows a pattern: sort events by time/position, maintain active state, update state on each event. Use appropriate data structures (stack, heap, union-find) based on the problem requirements.
Summary: Line Sweep Scanline Pattern
Core Concept: Process events in sorted order (time/position), maintain active state that updates at each event
Interval Merging: Sort by start time, merge when current.start ≤ previous.end, extend end to max
Meeting Rooms: Min rooms = max concurrent meetings, use two-pointer sweep or event-based counting
Skyline Problem: Create start/end events, track active heights with multiset/heap, output when max changes
Rectangle Overlap: Two rectangles overlap if NOT separated in both x and y axes
Rectangle Area Union: Coordinate compression creates grid cells, or sweep line with y-interval merging
Event Sorting: Critical for correctness - consider event type priority at same timestamp
State Management: Use appropriate data structure: stack for monotonic, heap for priority, map for frequencies
Complexity: Typically O(n log n) for sorting + O(n) or O(n log n) for processing events