Leetcode/Guide

Contents

The Ultimate LeetCode Fight Guide! (in JavaScript)

Sharpen your JS sword. This is the “newbie-friendly, exam-day-ready” playbook: battle-tested patterns, tiny templates, and plain-English advice to smash the most common coding test questions — fast and confidently.

Detailed Explanations

1. Two Pointers
2. Sliding Window
3. Binary Search
4. BFS
5. DFS
6. Greedy
7. Strings
8. Mathematics

---

🧭 Game Plan — How to win interviews without panic

1) Classify first, code second.
Before typing, ask: Which pattern is this? (Window? Stack? DP? Graph?) Getting the pattern right = 80% done.

2) Pick the correct weapon (DS/Algo).
Arrays, hash maps, stacks, heaps, graphs, union-find, recursion/DP — each solves specific shapes of problems. Don’t brute force it; choose the tool that fits the pattern.

3) Prove it (lightweight).
One sentence is fine: state an invariant (what stays true while you loop) or a recurrence (how subproblems build the solution). That shows correctness and guides your code.

4) Squeeze complexity.
Start from naive → improve: O(n²) → O(n log n) → O(n). Use sorting to unlock greedy; use hashing to drop to O(n); use prefix sums to avoid nested loops, etc.

5) Code from a template.
Keep small, memorized skeletons. Swap in the problem’s logic. Then test edge cases and state big-O clearly.

Pro tip: Narrate your thought process out loud. “This is a sliding window with at most K distinct…” Interviewers love clarity.

---

⚙️ Setup Snippets (JS) — little helpers you’ll reuse

These are your speed boosters for Node/JS.

// Fast I/O (Node local)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);

// Frequency map
const freq = s => {
  const m = new Map();
  for (const ch of s) m.set(ch, (m.get(ch) || 0) + 1);
  return m;
};

// Priority Queue (min-heap) using binary heap
class MinHeap {
  constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
  size(){ return this.a.length; }
  top(){ return this.a[0]; }
  push(x){ this.a.push(x); this._up(this.size()-1); }
  pop(){ const r = this.top(); const x = this.a.pop();
    if (this.size()) { this.a[0] = x; this._down(0); } return r; }
  _up(i){ const {a, cmp}=this; while(i){ let p=(i-1)>>1; if(cmp(a[i],a[p])>=0) break;
    [a[i],a[p]]=[a[p],a[i]]; i=p; } }
  _down(i){ const {a, cmp}=this; for(;;){ let l=i*2+1, r=l+1, m=i;
    if(l<a.length && cmp(a[l],a[m])<0) m=l;
    if(r<a.length && cmp(a[r],a[m])<0) m=r;
    if(m===i) break; [a[i],a[m]]=[a[m],a[i]]; i=m; } }
}

Why these matter

• Map over plain objects: faster and safe for non-string keys.
• Heap: unlocks Dijkstra, top-K, meeting rooms, merging k lists.
• freq is your Swiss army knife for anagrams, counters, and windows.

---

🧩 Pattern 1: Two Pointers

More on Leetcode/Guide/Two Pointers

Recognize by: “sorted array,” “pair/sum difference,” “move from both ends,” “dedupe in place.”

Mental model: Place two runners (i at start, j at end) or a read/write pair. You shrink/expand towards the answer while maintaining a simple invariant.

// Remove duplicates from sorted array, return new length
function removeDup(nums){
  let w = 0;
  for (let r = 0; r < nums.length; r++){
    if (r === 0 || nums[r] !== nums[r-1]) nums[w++] = nums[r];
  }
  return w; // first w are unique
}

// 2Sum in sorted array
function twoSumSorted(a, target){
  let i = 0, j = a.length - 1;
  while (i < j){
    const s = a[i] + a[j];
    if (s === target) return [i, j];
    s < target ? i++ : j--;
  }
  return [-1, -1];
}

Invariant:

• Dedupe: nums[0..w-1] is always unique and sorted.
• 2Sum: If sum too small, left++ increases it; if too big, right-- decreases it.

Complexity: O(n) time, O(1) space.

Common gotchas:

• Forgetting array is sorted. If not sorted → use hash map or sort first.
• Off-by-one when writing back.

---

🪟 Pattern 2: Sliding Window

More on Leetcode/Guide/Sliding Window

Recognize by: “longest/shortest subarray/substring with … constraints,” “at most K distinct,” “sum ≤ K.”

Mental model: Expand right to gain, shrink left to fix violations. Track counts in a hash map. For “longest valid,” shrink until valid; for “count subarrays,” add (right-left+1) when valid.

// Longest substring without repeating chars
function lengthOfLongestSubstring(s){
  const pos = new Map();
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++){
    const ch = s[right];
    if (pos.has(ch) && pos.get(ch) >= left) left = pos.get(ch) + 1;
    pos.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

// At most K distinct (template)
function atMostK(s, K){
  const m = new Map(); let left = 0, distinct = 0, ans = 0;
  for (let right = 0; right < s.length; right++){
    m.set(s[right], (m.get(s[right]) || 0) + 1);
    if (m.get(s[right]) === 1) distinct++;
    while (distinct > K){
      m.set(s[left], m.get(s[left]) - 1);
      if (m.get(s[left]) === 0) { m.delete(s[left]); distinct--; }
      left++;
    }
    ans += right - left + 1; // for counting subarrays; use Math.max for longest
  }
  return ans;
}

Invariant: Window [left..right] always satisfies the constraint after the inner while.

Common gotchas:

• Forgetting to update the map when shrinking.
• Mixing “at most K” vs “exactly K.” Use exactlyK = atMostK(K) - atMostK(K-1).

---

🔎 Pattern 3: Binary Search (on the answer)

More on Leetcode/Guide/Binary Search

Recognize by: “min capacity,” “min speed,” “kth day,” “smallest x such that condition holds.”

Mental model: Search a numeric range where a predicate is monotonic: F F F T T T. Find first T.

// Generic binary search (first true)
function firstTrue(lo, hi, pred){
  while (lo < hi){
    const mid = (lo + hi) >> 1;
    if (pred(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

// Example: Koko Eating Bananas
function minEatingSpeed(piles, h){
  const ok = k => piles.reduce((t, x) => t + Math.ceil(x/k), 0) <= h;
  return firstTrue(1, Math.max(...piles), ok);
}

Checklist:

• Define search bounds correctly.
• Make predicate cheap and monotonic.
• Avoid infinite loops; make progress (lo = mid+1 or hi = mid).

Complexity: O(log R * check).

---

🧵 Pattern 4: Prefix Sum / Difference Array

Recognize by: “how many subarrays sum to k,” “range sums quickly,” “balance +1/-1.”

Mental model: Track running sum pre. Two positions with the same pre imply the subarray between them sums to 0; generalize for k using a map.

// Count subarrays with sum = k
function subarraySum(nums, k){
  const map = new Map([0,1](/wiki/0,1));
  let pre = 0, ans = 0;
  for (const x of nums){
    pre += x;
    ans += map.get(pre - k) || 0;
    map.set(pre, (map.get(pre) || 0) + 1);
  }
  return ans;
}

Common gotchas:

• Initialize map with {0:1} to count subarrays starting at index 0.
• For mod problems (e.g., sum % k), store pre % k normalized to [0..k-1].

---

🧱 Pattern 5: Stack & Monotonic Stack

Recognize by: “valid parentheses,” “next greater element,” “largest rectangle,” “daily temperatures.”

Mental model:

• Plain stack validates nesting (push opens, match closes).
• Monotonic stack keeps indices with increasing/decreasing values to find next greater/smaller.

// Valid parentheses
function isValid(s){
  const st = [], pair = {')':'(',']':'[','}':'{'};
  for (const ch of s){
    if (ch in pair){
      if (!st.length || st.pop() !== pair[ch]) return false;
    } else st.push(ch);
  }
  return st.length === 0;
}

// Largest rectangle in histogram
function largestRectangleArea(h){
  const st = []; let ans = 0;
  h.push(0);
  for (let i = 0; i < h.length; i++){
    while (st.length && h[st.at(-1)] > h[i]){
      const height = h[st.pop()];
      const left = st.length ? st.at(-1) : -1;
      ans = Math.max(ans, height * (i - left - 1));
    }
    st.push(i);
  }
  h.pop();
  return ans;
}

Gotchas:

• Add sentinel (0) to flush remaining bars.
• Store indices (not values) for width math.

---

🌲 Pattern 6: Trees (DFS/BFS)

More on Leetcode/Guide/BFS and Leetcode/Guide/DFS

Recognize by: “max depth,” “level order,” “path sum,” “LCA.”

Mental model:

• DFS recursion: combine left/right results.
• BFS: queue nodes level by level (great for zigzag / level sums).

// DFS recursion (binary tree)
function maxDepth(root){
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS level order
function levelOrder(root){
  if (!root) return [];
  const q = [root], res = [];
  while (q.length){
    const size = q.length, lvl = [];
    for (let i = 0; i < size; i++){
      const n = q.shift();
      lvl.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(lvl);
  }
  return res;
}

// LCA (BST)
function lowestCommonAncestor(root, p, q){
  let cur = root;
  while (cur){
    if (p.val < cur.val && q.val < cur.val) cur = cur.left;
    else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
    else return cur;
  }
}

Gotchas:

• For general binary trees (not BST), LCA requires recursive return-up logic, not value comparisons.
• For BFS in JS, shift() is O(n). Use head pointer (see O(1) queue later) if performance is tight.

---

🔗 Pattern 7: Graphs (BFS/DFS/Topo/Shortest Path)

More on Leetcode/Guide/BFS and Leetcode/Guide/DFS

Recognize by: “number of components,” “minimum steps,” “course schedule,” “clones,” “grid problems.”

Mental model:

• Build adjacency list.
• BFS for unweighted shortest path.
• Topo sort (Kahn or DFS) to detect cycles and order tasks.

// Build adjacency list
function build(n, edges, directed=false){
  const g = Array.from({length:n},()=>[]);
  for (const [u,v] of edges){
    g[u].push(v);
    if (!directed) g[v].push(u);
  }
  return g;
}

// BFS shortest path (unweighted)
function shortest(n, edges, src){
  const g = build(n, edges), dist = Array(n).fill(Infinity);
  const q = [src]; dist[src] = 0;
  for (let i=0;i<q.length;i++){
    const u = q[i];
    for (const v of g[u]) if (dist[v] === Infinity){
      dist[v] = dist[u] + 1; q.push(v);
    }
  }
  return dist;
}

// Topological sort (Kahn)
function topo(n, edges){
  const g = build(n, edges, true), indeg = Array(n).fill(0);
  for (let u=0;u<n;u++) for (const v of g[u]) indeg[v]++;
  const q = []; for (let i=0;i<n;i++) if (!indeg[i]) q.push(i);
  const order = [];
  for (let i=0;i<q.length;i++){
    const u = q[i]; order.push(u);
    for (const v of g[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === n ? order : []; // empty = cycle
}

Gotchas:

• For grid BFS/DFS, convert to graph by neighbor moves (up/down/left/right) and bounds checks.
• Cycle detection in directed graphs: topo returns empty if cycle exists.

---

🧭 Pattern 8: Dijkstra / Heap (non-negative weights)

Recognize by: “min cost path,” “shortest travel time,” “network delay,” “k-route cost.”

Mental model: Distance array + min-heap. Pop smallest distance, relax neighbors.

function dijkstra(n, edges, src){
  const g = Array.from({length:n},()=>[]);
  for (const [u,v,w] of edges){ g[u].push([v,w]); g[v].push([u,w]); }
  const dist = Array(n).fill(Infinity); dist[src]=0;
  const pq = new MinHeap((a,b)=>a[0]-b[0]); // [dist,node]
  pq.push([0,src]);
  while (pq.size()){
    const [d,u]=pq.pop(); if (d!==dist[u]) continue;
    for (const [v,w] of g[u]){
      if (d + w < dist[v]){
        dist[v] = d + w; pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Gotchas:

• Negative edges? Use Bellman-Ford or SPFA (or make it DAG + topo DP).
• For directed graphs, don’t add the reverse edge.

---

🧮 Pattern 9: Backtracking

More on Leetcode/Guide/DFS

Recognize by: “generate all subsets,” “permutations,” “combination sum,” “N-queens.”

Mental model: Build a path, choose/not choose, undo (backtrack). Use pruning to cut dead branches.

// Subsets
function subsets(nums){
  const res = [], path = [];
  (function dfs(i){
    if (i === nums.length){ res.push([...path]); return; }
    path.push(nums[i]); dfs(i+1); path.pop();
    dfs(i+1);
  })(0);
  return res;
}

// Permutations
function permute(nums){
  const res = [], used = Array(nums.length).fill(false), path = [];
  (function dfs(){
    if (path.length === nums.length){ res.push([...path]); return; }
    for (let i=0;i<nums.length;i++){
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      dfs();
      path.pop(); used[i] = false;
    }
  })();
  return res;
}

Gotchas:

• For duplicate numbers, sort first and skip duplicates when used[i-1] == false.
• Watch recursion depth; iterative alternatives exist for big N.

---

🧠 Pattern 10: Dynamic Programming (1D/2D)

Recognize by: “max/min ways,” “min edits,” “knapsack,” “palindromes,” “grid paths.” Has optimal substructure + overlapping subproblems.

// 1D DP: House Robber
function rob(nums){
  let take = 0, skip = 0;
  for (const x of nums){
    const ntake = skip + x;
    skip = Math.max(skip, take);
    take = ntake;
  }
  return Math.max(take, skip);
}

// 2D DP: Edit Distance
function minDistance(a, b){
  const m=a.length, n=b.length;
  const dp = Array.from({length:m+1},()=>Array(n+1).fill(0));
  for (let i=0;i<=m;i++) dp[i][0]=i;
  for (let j=0;j<=n;j++) dp[0][j]=j;
  for (let i=1;i<=m;i++){
    for (let j=1;j<=n;j++){
      if (a[i-1]===b[j-1]) dp[i][j]=dp[i-1][j-1];
      else dp[i][j]=1+Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
  }
  return dp[m][n];
}

DP checklist:

• Define state: dp[i] or dp[i][j] meaning.
• Transition: how to build from smaller states.
• Base: edges for i=0 or j=0.
• Order: ensure dependencies computed first.
• Space cut: often 2 rows or 1D rolling array.

---

🧮 Pattern 11: Greedy

More on Leetcode/Guide/Greedy

Recognize by: “interval scheduling,” “minimum arrows,” “jump reachability,” “choose max with simple rule.”

Mental model: Pick the locally best option that can be proven globally optimal (exchange argument).

// Interval scheduling: max non-overlapping
function eraseOverlapIntervals(iv){
  iv.sort((a,b)=>a[1]-b[1]);
  let cnt = 0, end = -Infinity;
  for (const [s,e] of iv){
    if (s >= end){ cnt++; end = e; }
  }
  return iv.length - cnt;
}

// Jump Game (reachability)
function canJump(nums){
  let far = 0;
  for (let i=0;i<nums.length;i++){
    if (i > far) return false;
    far = Math.max(far, i + nums[i]);
  }
  return true;
}

Gotchas:

• If “min jumps” (not just reachability), you need a layered BFS/greedy level pass.

---

🧰 Bit Tricks (Quick Wins)

Tiny tricks that solve certain problems instantly.

// Count set bits (Brian Kernighan)
function popcount(x){ let c=0; while(x){ x&=x-1; c++; } return c; }

// Single number (every other appears twice)
function singleNumber(a){ return a.reduce((acc,x)=>acc^x,0); }

Use cases:

• Parity, masks, subsets by mask loops, toggling flags, dedupe by XOR.

---

🧩 Union-Find (Disjoint Set)

Recognize by: “number of islands,” “connected components,” “friend circles,” “Kruskal MST.”

Mental model: Group elements by parent; find with path compression + union by rank.

class DSU{
  constructor(n){ this.p=Array.from({length:n},(_,i)=>i); this.r=Array(n).fill(0); }
  find(x){ return this.p[x]===x? x : (this.p[x]=this.find(this.p[x])); }
  union(a,b){
    a=this.find(a); b=this.find(b); if(a===b) return false;
    if(this.r[a]<this.r[b]) [a,b]=[b,a];
    this.p[b]=a; if(this.r[a]===this.r[b]) this.r[a]++; return true;
  }
}

Gotchas:

• Always compress paths in find for near O(α(n)) speed.
• Map 2D grid to 1D id: id = r * cols + c.

---

🧪 Testing Edge Cases (Interview Checklist)

• Empty input / single element
• All equal / strictly increasing / strictly decreasing
• Duplicates & extremes (min/max int)
• Negative numbers / zeros
• Large sizes (n = 1e5) for performance
• Off-by-one boundaries (index 0 / last index)
• For strings: Unicode? spaces? punctuation?
• For graphs: isolated nodes? multiple components?

Quick sanity: Print small trace or assert invariants while coding.

---

⏱️ Complexity Cheats (speak interviewer language)

• HashMap/Set ops: average O(1)
• Heap ops: O(log n)
• Sort: O(n log n)
• BFS/DFS graph: O(n + m)
• Monotonic stack patterns: O(n)
• DP table m×n: O(mn), often O(min(m,n)) space with rolling

Talk track example: “Time O(n log n) from sorting; scan is linear; space O(1) apart from output.”

---

🧑‍💻 10 Practice Staples (JS-First)

1. Two Sum / 3Sum / 4Sum — hash vs two pointers on sorted.
2. Longest Substring Without Repeating — sliding window with last-seen map.
3. Merge Intervals / Insert Interval — sort + greedy merging.
4. Product of Array Except Self — prefix/suffix without division.
5. Valid Parentheses / Daily Temperatures — stack & monotonic stack.
6. Binary Tree Level Order / Zigzag — BFS with queue.
7. Number of Islands — DFS/BFS/Union-Find.
8. Kth Largest Element — heap or quickselect.
9. Coin Change / Climbing Stairs — DP (unbounded vs Fibonacci).
10. Word Ladder — BFS on implicit graph; and LRU Cache (Map + doubly list).

---

🧷 Common Pitfalls (JS Edition)

• Map/Set vs Object: Prefer Map/Set for speed and non-string keys.
• Shallow vs Deep copy: Arrays/objects share references — clone when needed (slice, spread).
• Sorting numbers: Must use arr.sort((a,b)=>a-b) (default is lexicographic).
• Large sums: JS Number is 53-bit safe. For extra large integers, consider BigInt.
• Queue performance: Avoid shift() in tight loops; use head pointer:

// O(1) queue
const q = []; let head = 0;
const enqueue = x => q.push(x);
const dequeue = () => head < q.length ? q[head++] : undefined;

---

🧠 Strategy Patterns (Identify by Keywords)

---

🧭 Final Boss Checklist (the 1-minute self-review)

• Pattern picked? Say it out loud.
• Invariant/recurrence? One sentence proof sketch.
• Handles edges? Empty, duplicates, negatives, boundaries.
• Complexity good? Aim ≤ O(n log n), space minimized.
• Explainable? Can you teach it in 60–120 seconds?
• Tiny tests? Run through a small example by hand.

---

💡 Bonus Mini-Templates (quick paste-ins)

1) Quickselect (kth largest) outline

function kthLargest(a, k){
  k = a.length - k; // kth largest → index k (0-based) after sort
  let l=0, r=a.length-1;
  while(l<=r){
    const p = partition(a, l, r);
    if (p === k) return a[p];
    if (p < k) l = p + 1; else r = p - 1;
  }
}
function partition(a, l, r){
  const pivot = a[r]; let i=l;
  for (let j=l;j<r;j++) if (a[j] <= pivot) [a[i],a[j]]=[a[j],a[i]], i++;
  [a[i],a[r]]=[a[r],a[i]]; return i;
}

2) Grid BFS (islands/shortest path)

function gridBfs(grid, sr, sc){
  const m=grid.length, n=grid[0].length;
  const q=[sr,sc](/wiki/sr,sc), seen=Array.from({length:m},()=>Array(n).fill(false));
  seen[sr][sc]=true;
  for(let i=0;i<q.length;i++){
    const [r,c]=q[i];
    for (const [dr,dc] of [1,0],[-1,0],[0,1],[0,-1](/wiki/1,0],[-1,0],[0,1],[0,-1)){
      const nr=r+dr, nc=c+dc;
      if (nr<0||nr>=m||nc<0||nc>=n||seen[nr][nc]) continue;
      // if grid[nr][nc] is valid to step on...
      seen[nr][nc]=true; q.push([nr,nc]);
    }
  }
}

3) Two-heap median of data stream

const max = new MinHeap((a,b)=>b-a), min = new MinHeap();
function addNum(x){
  max.push(x); min.push(max.pop());
  if (min.size() > max.size()) max.push(min.pop());
}
function findMedian(){
  return max.size() > min.size() ? max.top() : (max.top()+min.top())/2;
}

---

🏁 How to practice (and actually improve)

1. Drill the patterns. Pick a pattern, solve 3–5 problems in that family back-to-back.
2. Timebox: 15–20 min for approach, 20–30 min to code + test. Then read editorial/solutions for one better trick.
3. Make your own crib notes: Save tiny templates from this doc into your snippets.
4. Explain out loud: Pretend you’re teaching a junior. If you can teach it, you own it.
5. Revisit misses: Turn every bug into a checklist item (“remember to init map with {0:1}”).

You’ve got this — pattern first, code second, explain clearly, and ship.