Skip to content

Instantly share code, notes, and snippets.

@wingtonrbrito

wingtonrbrito/core-interview-review.js

Last active September 9, 2025 11:27
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save wingtonrbrito/6a39311114713e2278e5acf960af1c98 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save wingtonrbrito/6a39311114713e2278e5acf960af1c98 to your computer and use it in GitHub Desktop.
Download ZIP
Core problem snippets
Raw
core-interview-review.js
## 1️⃣ **TWO POINTERS**
**1. Two Sum II (Sorted Array)**
- **Pattern:** Two Pointers (Opposite Ends)
- **Core Logic:**
```javascript
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
```
- **Key Insight:** Use sorted property to eliminate half the search space
**2. 3Sum**
- **Pattern:** Fixed Point + Two Pointers
- **Core Logic:**
```javascript
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1, right = nums.length - 1;
while (left < right) {
// Two pointer logic with fixed nums[i]
}
}
```
- **Key Insight:** Fix one element, use two pointers for remaining two
**3. Valid Palindrome**
- **Pattern:** Two Pointers (Character Validation)
- **Core Logic:**
```javascript
while (left < right) {
while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
while (left < right && !/[a-z0-9]/i.test(s[right])) right--
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++; right--;
}
```
- **Key Insight:** Skip non-alphanumeric characters, compare case-insensitive
**4. Container With Most Water**
- **Pattern:** Two Pointers (Greedy)
- **Core Logic:**
```javascript
while (left < right) {
const area = Math.min(heights[left], heights[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (heights[left] < heights[right]) left++;
else right--;
}
```
- **Key Insight:** Always move pointer with smaller height
## 2️⃣ **HASH MAP**
**5. Two Sum**
- **Pattern:** Hash Map Complement
- **Core Logic:**
```javascript
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
```
- **Key Insight:** Store what you've seen, check for complement
**6. Valid Sudoku**
- **Pattern:** Hash Sets for Constraints
- **Core Logic:**
```javascript
const rows = Array(9).fill().map(() => new Set());
const cols = Array(9).fill().map(() => new Set());
const boxes = Array(3).fill().map(() => Array(3).fill().map(() => new Set()));
// Check if num already exists in row/col/box before adding
```
- **Key Insight:** Track three constraints: row, column, 3x3 box
**7. Set Matrix Zeroes**
- **Pattern:** Two-Pass with Markers
- **Core Logic:**
```javascript
// First pass: mark zeros
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (matrix[r][c] === 0) {
rows.add(r); cols.add(c);
}
}
}
// Second pass: set zeros
```
- **Key Insight:** Mark first, then modify to avoid interference
## 3️⃣ **LINKED LIST**
**8. Reverse Linked List**
- **Pattern:** Three Pointer Reversal
- **Core Logic:**
```javascript
let prev = null, current = head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
```
- **Key Insight:** Track previous, current, and next nodes
**9. Remove Nth Node From End**
- **Pattern:** Two Pointers with Gap
- **Core Logic:**
```javascript
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
```
- **Key Insight:** Create n+1 gap, then move both pointers
**10. Intersection of Two Linked Lists**
- **Pattern:** Length Equalization
- **Core Logic:**
```javascript
let pA = headA, pB = headB;
while (pA !== pB) {
pA = pA ? pA.next : headB;
pB = pB ? pB.next : headA;
}
return pA;
```
- **Key Insight:** Switch heads when reaching end to equalize lengths
**11. LRU Cache**
- **Pattern:** HashMap + Doubly Linked List
- **Core Logic:**
```javascript
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value); // Move to end
return value;
}
return -1;
}
```
- **Key Insight:** Map maintains insertion order in JavaScript
## 4️⃣ **FAST & SLOW POINTERS**
**12. Linked List Cycle**
- **Pattern:** Floyd's Cycle Detection
- **Core Logic:**
```javascript
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
```
- **Key Insight:** If cycle exists, fast will eventually meet slow
**13. Middle of Linked List**
- **Pattern:** Fast/Slow for Middle
- **Core Logic:**
```javascript
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
```
- **Key Insight:** When fast reaches end, slow is at middle
**14. Happy Number**
- **Pattern:** Cycle Detection on Numbers
- **Core Logic:**
```javascript
let slow = n, fast = getNext(n);
while (fast !== 1 && slow !== fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
```
- **Key Insight:** Apply Floyd's algorithm to number sequences
## 5️⃣ **SLIDING WINDOW**
**15. Find All Anagrams**
- **Pattern:** Fixed Size Sliding Window
- **Core Logic:**
```javascript
for (let i = 0; i < s.length; i++) {
windowCount[s[i]]++;
if (i >= p.length) {
const leftChar = s[i - p.length];
if (--windowCount[leftChar] === 0) delete windowCount[leftChar];
}
if (i >= p.length - 1 && isEqual(pCount, windowCount)) {
result.push(i - p.length + 1);
}
}
```
- **Key Insight:** Maintain fixed window size, compare frequency maps
**16. Longest Substring Without Repeating**
- **Pattern:** Variable Size Sliding Window
- **Core Logic:**
```javascript
const seen = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left++]);
}
seen.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
```
- **Key Insight:** Shrink window when constraint violated
**17. Longest Repeating Character Replacement**
- **Pattern:** Window with Constraint
- **Core Logic:**
```javascript
let maxFreq = 0, left = 0;
for (let right = 0; right < s.length; right++) {
count[s[right]]++;
maxFreq = Math.max(maxFreq, count[s[right]]);
if (right - left + 1 - maxFreq > k) {
count[s[left++]]--;
}
result = Math.max(result, right - left + 1);
}
```
- **Key Insight:** Window size - max frequency = characters to replace
## 6️⃣ **BINARY SEARCH**
**18. Binary Search**
- **Pattern:** Classic Binary Search
- **Core Logic:**
```javascript
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
```
- **Key Insight:** Eliminate half the search space each iteration
**19. Search Insert Position**
- **Pattern:** Binary Search for Position
- **Core Logic:**
```javascript
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left; // Insert position
```
- **Key Insight:** Return left pointer for insertion position
**20. Find First and Last Position**
- **Pattern:** Binary Search Bounds
- **Core Logic:**
```javascript
function findBound(isFirst) {
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
bound = mid;
if (isFirst) right = mid - 1; // Keep searching left
else left = mid + 1; // Keep searching right
}
}
}
```
- **Key Insight:** Continue searching after finding target
**21. Search in Rotated Sorted Array**
- **Pattern:** Binary Search with Pivot
- **Core Logic:**
```javascript
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else left = mid + 1;
} else {
// Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else right = mid - 1;
}
```
- **Key Insight:** At least one half is always sorted
## 7️⃣ **STACK**
**22. Valid Parentheses**
- **Pattern:** Stack for Matching
- **Core Logic:**
```javascript
const stack = [];
for (const char of s) {
if (isOpening(char)) stack.push(char);
else if (!stack.length || stack.pop() !== getMatching(char)) return false;
}
return stack.length === 0;
```
- **Key Insight:** Push opening brackets, pop and match closing
**23. Next Greater Element**
- **Pattern:** Monotonic Stack
- **Core Logic:**
```javascript
const stack = []; // Store indices
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
```
- **Key Insight:** Maintain decreasing stack, pop when greater found
**24. Basic Calculator**
- **Pattern:** Stack for Operations
- **Core Logic:**
```javascript
if (sign === '+') stack.push(num);
else if (sign === '-') stack.push(-num);
else if (sign === '*') stack.push(stack.pop() * num);
else if (sign === '/') stack.push(Math.trunc(stack.pop() / num));
```
- **Key Insight:** Process operators immediately, stack handles precedence
## 8️⃣ **HEAP**
**25. Top K Frequent Elements**
- **Pattern:** Frequency + Bucket Sort
- **Core Logic:**
```javascript
const buckets = Array(nums.length + 1).fill().map(() => []);
for (const [num, freq] of Object.entries(count)) {
buckets[freq].push(parseInt(num));
}
// Collect from highest frequency buckets
```
- **Key Insight:** Use frequency as bucket index for O(n) solution
**26. Merge k Sorted Lists**
- **Pattern:** Divide and Conquer
- **Core Logic:**
```javascript
while (lists.length > 1) {
const merged = [];
for (let i = 0; i < lists.length; i += 2) {
const l1 = lists[i];
const l2 = i + 1 < lists.length ? lists[i + 1] : null;
merged.push(mergeTwoLists(l1, l2));
}
lists = merged;
}
```
- **Key Insight:** Merge pairs repeatedly until one list remains
**27. Find Median from Data Stream**
- **Pattern:** Two Heaps (Max + Min)
- **Core Logic:**
```javascript
// Add to small (max heap), then move largest to large (min heap)
small.push(num);
large.push(small.shift());
// Balance: large can have at most 1 more element
if (large.length > small.length + 1) {
small.push(large.shift());
}
```
- **Key Insight:** Keep heaps balanced, median is at heap tops
## 9️⃣ **INTERVALS**
**28. Merge Intervals**
- **Pattern:** Sort + Merge Overlapping
- **Core Logic:**
```javascript
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
if (merged[merged.length - 1][1] >= intervals[i][0]) {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], intervals[i][1]);
} else merged.push(intervals[i]);
}
```
- **Key Insight:** Sort by start time, merge if overlap detected
**29. Interval List Intersections**
- **Pattern:** Two Pointers on Intervals
- **Core Logic:**
```javascript
const start = Math.max(firstList[i][0], secondList[j][0]);
const end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) result.push([start, end]);
// Move pointer with earlier end time
if (firstList[i][1] < secondList[j][1]) i++;
else j++;
```
- **Key Insight:** Find overlap range, advance pointer with earlier end
**30. Meeting Rooms II**
- **Pattern:** Event Sweep Line
- **Core Logic:**
```javascript
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 (const start of starts) {
if (start < ends[endPtr]) rooms++;
else endPtr++;
}
```
- **Key Insight:** Separate start/end events, track simultaneous meetings
## 🔟 **PREFIX SUM**
**31. Range Sum Query**
- **Pattern:** Prefix Sum Array
- **Core Logic:**
```javascript
constructor(nums) {
this.prefix = [0];
for (const num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
sumRange(left, right) {
return this.prefix[right + 1] - this.prefix[left];
}
```
- **Key Insight:** Precompute cumulative sums for O(1) range queries
**32. Subarray Sum Equals K**
- **Pattern:** Prefix Sum + HashMap
- **Core Logic:**
```javascript
let count = 0, currentSum = 0;
const prefixSums = {0: 1};
for (const num of nums) {
currentSum += num;
if (currentSum - k in prefixSums) {
count += prefixSums[currentSum - k];
}
prefixSums[currentSum] = (prefixSums[currentSum] || 0) + 1;
}
```
- **Key Insight:** If currentSum - k exists, we found a subarray
**33. Product of Array Except Self**
- **Pattern:** Left/Right Product Arrays
- **Core Logic:**
```javascript
// Left pass
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
// Right pass
let rightProduct = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= rightProduct;
rightProduct *= nums[i];
}
```
- **Key Insight:** Two passes to avoid division
## 1️⃣1️⃣ **TREES**
**34. Invert Binary Tree**
- **Pattern:** Recursive Tree Modification
- **Core Logic:**
```javascript
if (!root) return null;
[root.left, root.right] = [root.right, root.left];
invertBinaryTree(root.left);
invertBinaryTree(root.right);
return root;
```
- **Key Insight:** Swap children at each node recursively
**35. Balanced Binary Tree**
- **Pattern:** Bottom-Up Height Check
- **Core Logic:**
```javascript
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;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
```
- **Key Insight:** Return -1 for unbalanced, height for balanced
**36. Binary Tree Right Side View**
- **Pattern:** Level Order Traversal (BFS)
- **Core Logic:**
```javascript
while (queue.length) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (i === levelSize - 1) result.push(node.val); // Rightmost
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
```
- **Key Insight:** Last node in each level is rightmost visible
**37. Maximum Width of Binary Tree**
- **Pattern:** BFS with Position Tracking
- **Core Logic:**
```javascript
const queue = [[root, 0]]; // [node, position]
while (queue.length) {
const levelSize = queue.length;
const firstPos = queue[0][1];
const lastPos = queue[levelSize - 1][1];
maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
// Add children with positions 2*pos and 2*pos+1
}
```
- **Key Insight:** Track positions to calculate width
**38. Validate Binary Search Tree**
- **Pattern:** Recursive with Bounds
- **Core Logic:**
```javascript
function validate(node, min, max) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
```
- **Key Insight:** Pass valid range down to each subtree
**39. Lowest Common Ancestor**
- **Pattern:** Bottom-Up Search
- **Core Logic:**
```javascript
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root; // Both found in different subtrees
return left || right;
```
- **Key Insight:** If both nodes found in different subtrees, current is LCA
**40. Construct Tree from Preorder/Inorder**
- **Pattern:** Recursive Division
- **Core Logic:**
```javascript
const root = new TreeNode(preorder[0]); // First in preorder is root
const mid = inorder.indexOf(preorder[0]); // Split point in inorder
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
```
- **Key Insight:** Preorder gives root, inorder gives left/right split
**41. Binary Tree Maximum Path Sum**
- **Pattern:** Post-Order with Global Max
- **Core Logic:**
```javascript
function maxGain(node) {
if (!node) return 0;
const leftGain = Math.max(maxGain(node.left), 0);
const rightGain = Math.max(maxGain(node.right), 0);
const currentMax = node.val + leftGain + rightGain; // Path through node
maxSum = Math.max(maxSum, currentMax);
return node.val + Math.max(leftGain, rightGain); // Max path continuing
}
```
- **Key Insight:** Track global max path, return continuing path
## 1️⃣2️⃣ **TRIE**
**42. Implement Trie**
- **Pattern:** Character-Based Tree
- **Core Logic:**
```javascript
insert(word) {
let node = this.root;
for (const char of word) {
if (!node[char]) node[char] = {};
node = node[char];
}
node.isEnd = true;
}
```
- **Key Insight:** Each node represents character position in words
**43. Design Add and Search Words**
- **Pattern:** Trie with Wildcard DFS
- **Core Logic:**
```javascript
search(word) {
function dfs(node, index) {
if (index === word.length) return node.isEnd === true;
const char = word[index];
if (char === '.') {
for (const key in node) {
if (key !== 'isEnd' && dfs(node[key], index + 1)) return true;
}
return false;
}
return node[char] && dfs(node[char], index + 1);
}
return dfs(this.root, 0);
}
```
- **Key Insight:** DFS explores all possibilities for '.' wildcard
**44. Word Search II**
- **Pattern:** Trie + DFS Backtracking
- **Core Logic:**
```javascript
function dfs(i, j, node) {
const char = board[i][j];
if (!node[char]) return;
node = node[char];
if (node.word) {
result.push(node.word);
node.word = null; // Avoid duplicates
}
board[i][j] = '#'; // Mark visited
// Try 4 directions
board[i][j] = char; // Restore
}
```
- **Key Insight:** Build trie of words, then DFS with pruning
## 1️⃣3️⃣ **GRAPHS**
**45. Clone Graph**
- **Pattern:** DFS with HashMap
- **Core Logic:**
```javascript
function dfs(node) {
if (cloned.has(node)) return cloned.get(node);
const copy = new Node(node.val);
cloned.set(node, copy);
for (const neighbor of node.neighbors) {
copy.neighbors.push(dfs(neighbor));
}
return copy;
}
```
- **Key Insight:** Use map to track cloned nodes, avoid cycles
**46. Number of Islands**
- **Pattern:** DFS Grid Traversal
- **Core Logic:**
```javascript
function dfs(i, j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') return;
grid[i][j] = '0'; // Mark as visited
dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
}
// Count connected components
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
islands++; dfs(i, j);
}
}
}
```
- **Key Insight:** Each DFS marks one complete island
**47. Rotting Oranges**
- **Pattern:** Multi-Source BFS
- **Core Logic:**
```javascript
// Start BFS from all rotten oranges simultaneously
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) queue.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
}
// BFS level by level
while (queue.length && fresh > 0) {
minutes++;
const size = queue.length;
for (let i = 0; i < size; i++) {
// Process current level
}
}
```
- **Key Insight:** BFS from all sources simultaneously for minimum time
**48. Is Graph Bipartite**
- **Pattern:** Graph Coloring DFS
- **Core Logic:**
```javascript
function dfs(node, color) {
colors[node] = color;
for (const neighbor of graph[node]) {
if (colors[neighbor] === color) return false; // Same color
if (colors[neighbor] === -1 && !dfs(neighbor, 1 - color)) return false;
}
return true;
}
```
- **Key Insight:** Try to color graph with two colors, check conflicts
**49. Longest Increasing Path in Matrix**
- **Pattern:** DFS with Memoization
- **Core Logic:**
```javascript
function dfs(i, j) {
if (cache[i][j] !== 0) return cache[i][j];
let maxPath = 1;
for (const [di, dj] of directions) {
const ni = i + di, nj = j + dj;
if (isValid(ni, nj) && matrix[ni][nj] > matrix[i][j]) {
maxPath = Math.max(maxPath, 1 + dfs(ni, nj));
}
}
cache[i][j] = maxPath;
return maxPath;
}
```
- **Key Insight:** Memoize results to avoid recomputation
**50. Word Ladder**
- **Pattern:** BFS Shortest Path
- **Core Logic:**
```javascript
const queue = [[beginWord, 1]];
while (queue.length) {
const [word, level] = queue.shift();
if (word === endWord) return level;
for (let i = 0; i < word.length; i++) {
for (let j = 0; j < 26; j++) {
const newWord = word.slice(0, i) + String.fromCharCode(97 + j) + word.slice(i + 1);
if (wordSet.has(newWord)) {
wordSet.delete(newWord);
queue.push([newWord, level + 1]);
}
}
}
}
```
- **Key Insight:** BFS guarantees shortest transformation sequence
**51. Union Find**
- **Pattern:** Disjoint Set with Path Compression
- **Core Logic:**
```javascript
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 px = this.find(x), py = this.find(y);
if (px === py) return false;
if (this.rank[px] < this.rank[py]) this.parent[px] = py;
else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
else { this.parent[py] = px; this.rank[px]++; }
return true;
}
```
- **Key Insight:** Path compression + union by rank for efficiency
**52. Course Schedule**
- **Pattern:** Cycle Detection DFS
- **Core Logic:**
```javascript
// 0: unvisited, 1: visiting, 2: visited
function hasCycle(course) {
if (states[course] === 1) return true; // Back edge - cycle
if (states[course] === 2) return false; // Already processed
states[course] = 1; // Mark as visiting
for (const next of graph[course]) {
if (hasCycle(next)) return true;
}
states[course] = 2; // Mark as visited
return false;
}
```
- **Key Insight:** Three states track cycle detection in directed graph
## 1️⃣4️⃣ **BACKTRACKING**
**53. Permutations**
- **Pattern:** Swap-Based Backtracking
- **Core Logic:**
```javascript
function backtrack(start = 0) {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]]; // Swap
backtrack(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]]; // Restore
}
}
```
- **Key Insight:** Generate permutations by swapping elements
**54. Subsets**
- **Pattern:** Include/Exclude Backtracking
- **Core Logic:**
```javascript
function backtrack(start, path) {
result.push([...path]); // Add current subset
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // Include
backtrack(i + 1, path);
path.pop(); // Exclude
}
}
```
- **Key Insight:** Each position has include/exclude choice
**55. N-Queens**
- **Pattern:** Constraint-Based Backtracking
- **Core Logic:**
```javascript
function backtrack(row) {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
```
- **Key Insight:** Check all constraints before placing queen
## 1️⃣5️⃣ **DYNAMIC PROGRAMMING**
**56. Climbing Stairs**
- **Pattern:** 1D DP (Fibonacci)
- **Core Logic:**
```javascript
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
```
- **Key Insight:** Each step is sum of previous two possibilities
**57. Coin Change**
- **Pattern:** 1D DP (Min Cost)
- **Core Logic:**
```javascript
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
```
- **Key Insight:** Build up solutions for smaller amounts
**58. Unique Paths**
- **Pattern:** 2D DP (Grid)
- **Core Logic:**
```javascript
const dp = Array(m).fill().map(() => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
```
- **Key Insight:** Paths to cell = paths from above + paths from left
**59. House Robber**
- **Pattern:** 1D DP (Adjacent Constraint)
- **Core Logic:**
```javascript
let prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
```
- **Key Insight:** Max of (rob current + prev2) or (skip current)
**60. Longest Common Subsequence**
- **Pattern:** 2D DP (String Matching)
- **Core Logic:**
```javascript
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]);
}
```
- **Key Insight:** Match characters or take best from skipping either
**61. Longest Palindromic Substring**
- **Pattern:** Expand Around Centers
- **Core Logic:**
```javascript
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--; right++;
}
return right - left - 1;
}
// Try both odd and even length palindromes
```
- **Key Insight:** Every palindrome expands around its center
**62. Maximum Subarray**
- **Pattern:** Kadane's Algorithm
- **Core Logic:**
```javascript
let maxCurrent = nums[0], maxGlobal = nums[0];
for (let i = 1; i < nums.length; i++) {
maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
maxGlobal = Math.max(maxGlobal, maxCurrent);
}
```
- **Key Insight:** Either start new subarray or extend current
**63. 0/1 Knapsack**
- **Pattern:** 1D DP (Capacity Constraint)
- **Core Logic:**
```javascript
for (let i = 0; i < n; i++) {
for (let w = capacity; w >= weights[i]; w--) { // Backwards!
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
```
- **Key Insight:** Traverse backwards to avoid using item multiple times
## 1️⃣6️⃣ **GREEDY**
**64. Jump Game**
- **Pattern:** Greedy Reach Tracking
- **Core Logic:**
```javascript
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
```
- **Key Insight:** Track farthest reachable position
**65. Gas Station**
- **Pattern:** Greedy Reset Strategy
- **Core Logic:**
```javascript
let tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
```
- **Key Insight:** Reset start when tank goes negative
**66. Candy Distribution**
- **Pattern:** Two-Pass Greedy
- **Core Logic:**
```javascript
// Left to right: higher rating gets more candy
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
// Right to left: maintain left constraint
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) {
candies[i] = Math.max(candies[i], candies[i+1] + 1);
}
}
```
- **Key Insight:** Two passes ensure both neighbor constraints
## 1️⃣7️⃣ **SORTING**
**67. Sort List**
- **Pattern:** Merge Sort on Linked List
- **Core Logic:**
```javascript
// Find middle using slow/fast pointers
let slow = head, fast = head, prev = null;
while (fast && fast.next) {
prev = slow; slow = slow.next; fast = fast.next.next;
}
prev.next = null; // Split list
// Recursively sort both halves, then merge
```
- **Key Insight:** Use two pointers to find middle, then merge
**68. Kth Largest Element**
- **Pattern:** QuickSelect
- **Core Logic:**
```javascript
function quickSelect(left, right) {
const pivotIdx = partition(left, right);
if (pivotIdx === k) return nums[pivotIdx];
else if (pivotIdx < k) return quickSelect(pivotIdx + 1, right);
else return quickSelect(left, pivotIdx - 1);
}
```
- **Key Insight:** Only recurse on side containing kth element
## 1️⃣8️⃣ **BIT MANIPULATION**
**69. Number of 1 Bits**
- **Pattern:** Brian Kernighan's Algorithm
- **Core Logic:**
```javascript
while (n !== 0) {
n &= n - 1; // Remove rightmost 1 bit
count++;
}
```
- **Key Insight:** n & (n-1) removes the rightmost set bit
**70. Single Number**
- **Pattern:** XOR Properties
- **Core Logic:**
```javascript
let result = 0;
for (const num of nums) {
result ^= num; // XOR cancels duplicates
}
```
- **Key Insight:** XOR of identical numbers is 0, XOR with 0 is identity
## 1️⃣9️⃣ **MATH & GEOMETRY**
**71. Spiral Matrix**
- **Pattern:** Layer-by-Layer Traversal
- **Core Logic:**
```javascript
while (top <= bottom && left <= right) {
// Right, Down, Left, Up
for (let j = left; j <= right; j++) result.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
// Check bounds before left and up
}
```
- **Key Insight:** Process matrix in concentric layers
**72. Reverse Integer**
- **Pattern:** Digit Extraction with Overflow Check
- **Core Logic:**
```javascript
while (x !== 0) {
const digit = x % 10;
x = Math.floor(x / 10);
if (result > Math.floor(INT_MAX / 10) ||
(result === Math.floor(INT_MAX / 10) && digit > 7)) return 0;
result = result * 10 + digit;
}
```
- **Key Insight:** Check overflow before multiplying by 10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment