🎯 Top 40 JavaScript Array Interview Questions

Index: Questions Index | Parent: JS Array Index

---

How to Use This Guide

For every question, follow this 3-step process before looking at the code:

1. Read the problem — understand input/output
2. Read the "How to Approach" — understand the pattern and thinking
3. Try coding it yourself — then compare with the solution

---

Pattern Recognition Quick Guide

---

Easy Level

---

Q1. Find All Duplicates in Array [E][FB]

Problem: Array with values in range 1..n. Find all numbers that appear twice. O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values are 1..n → index negation trick. Use the array itself as a visited marker.

Step 2 — Brute force:

Use a Set to track seen values. O(n) time, O(n) space — violates O(1) space constraint.

Step 3 — Optimal insight:

For value v, treat index v-1 as its "home". Negate arr[v-1] to mark "seen". If already negative, v appeared before → it's a duplicate.

Step 4 — Algorithm:

1. For each element num (use Math.abs since we negate):

2. idx = Math.abs(num) - 1

3. If arr[idx] < 0 → duplicate found, push Math.abs(num)

4. Else arr[idx] = -arr[idx] → mark visited

Step 5 — Edge cases:

- Always use Math.abs(num) because previous iterations may have negated it

- O(1) space: result array doesn't count as extra

// Method 1: O(1) extra space — index negation
function findDuplicates(nums) {
  const result = [];
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    if (nums[idx] < 0) {
      result.push(Math.abs(num)); // already marked → duplicate
    } else {
      nums[idx] = -nums[idx]; // mark visited
    }
  }
  return result;
}

// Method 2: O(n) space — cleaner with Set
function findDuplicatesSet(nums) {
  const seen = new Set();
  return nums.filter(n => seen.has(n) || !seen.add(n) && false);
  // cleaner:
}
function findDuplicatesSetClear(nums) {
  const seen = new Set(), result = [];
  for (const n of nums) {
    if (seen.has(n)) result.push(n);
    else seen.add(n);
  }
  return result;
}

console.log(findDuplicates([4,3,2,7,8,2,3,1])); // [2,3]

Time: O(n) | Space: O(1) for in-place version

---

Q2. Find Missing Number [E][FB]

Problem: Array has n distinct numbers from 0 to n with one missing. Find it.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

We know the complete set should be {0,1,...,n}. Find the one absent value.

Step 2 — Two great approaches:

Approach A — Sum formula: Expected sum = n*(n+1)/2. Missing = expected - actual.

Approach B — XOR: XOR all indices (0..n) with all values. Pairs cancel. Missing number remains.

Step 3 — Why XOR is sometimes better:

For very large n, sum could overflow 32-bit integers. XOR avoids this.

Step 4 — Algorithm (XOR):

1. Start xor = n (start with the "extra" index)

2. For i from 0 to n-1: xor = xor XOR i XOR nums[i]

3. Return xor

Step 5 — Edge cases:

- Missing 0: formula works (expected includes 0)

- Missing n: formula works too

// Method 1: Sum formula — readable
function missingNumber(nums) {
  const n = nums.length;
  const expected = n * (n + 1) / 2;
  return expected - nums.reduce((a, b) => a + b, 0);
}

// Method 2: XOR — no overflow
function missingNumberXOR(nums) {
  let xor = nums.length;
  nums.forEach((num, i) => { xor ^= i ^ num; });
  return xor;
}

// Method 3: Math.max approach with Set (less optimal but intuitive)
function missingNumberSet(nums) {
  const set = new Set(nums);
  for (let i = 0; i <= nums.length; i++) {
    if (!set.has(i)) return i;
  }
}

console.log(missingNumber([3,0,1]));   // 2
console.log(missingNumber([0,1]));     // 2
console.log(missingNumber([9,6,4,2,3,5,7,0,1])); // 8

Time: O(n) | Space: O(1)

---

Q3. Single Number — Find Non-Duplicate [E][FB]

Problem: Every element appears twice except one. Find it. O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Every element twice except one" → XOR property: a XOR a = 0, a XOR 0 = a.

Step 2 — Why XOR works:

XOR all elements. Every pair cancels out (becomes 0). Only the unique element remains.

Order doesn't matter (XOR is commutative and associative):

2 XOR 3 XOR 2 = (2 XOR 2) XOR 3 = 0 XOR 3 = 3

Step 3 — Algorithm:

Single line: reduce all elements with XOR, starting from 0.

Step 4 — Edge cases:

- Single element array → return it

- Works regardless of order, no sorting needed

// Elegant one-liner
const singleNumber = nums => nums.reduce((xor, n) => xor ^ n, 0);

// Equivalent explicit version
function singleNumberExplicit(nums) {
  let result = 0;
  for (const num of nums) result ^= num;
  return result;
}

console.log(singleNumber([2,2,1]));     // 1
console.log(singleNumber([4,1,2,1,2])); // 4
console.log(singleNumber([1]));         // 1

Time: O(n) | Space: O(1)

---

Q4. Plus One [E]

Problem: Array represents a number digit by digit: [1,2,9] = 129. Add 1. Return new array.

---

🧠 How to Approach This

Step 1 — Simulate carry:

Process right to left (least significant digit first). Add 1 with carry logic.

Step 2 — Three cases:

- Digit 0-8: just increment → done, return immediately

- Digit 9: becomes 0, carry continues left

- All 9s: all become 0, prepend 1 at the front

Step 3 — Algorithm:

1. Loop i from end to start

2. If digits[i] < 9: increment and return

3. Set digits[i] = 0 (carry continues)

4. After loop: return [1, ...digits] (all-nines case)

function plusOne(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;       // no carry, done immediately
    }
    digits[i] = 0;         // was 9, set to 0, carry left
  }
  return [1, ...digits];   // all digits were 9: [9,9] → [1,0,0]
}

console.log(plusOne([1,2,3])); // [1,2,4]
console.log(plusOne([1,2,9])); // [1,3,0]
console.log(plusOne([9,9,9])); // [1,0,0,0]

Time: O(n) worst | Space: O(1) most cases, O(n) for all-nines

---

Q5. Maximum Product of Two Elements [E]

Problem: Find (nums[i]-1) * (nums[j]-1) for the maximum result.

---

🧠 How to Approach This

Step 1 — What are we maximizing?

(max1 - 1) × (max2 - 1). Find the two largest values.

Step 2 — Two approaches:

- Sort descending → take first two O(n log n)

- Single pass tracking max1 and max2 → O(n)

Step 3 — Algorithm (O(n)):

1. Track max1 (largest) and max2 (second largest)

2. If num > max1: max2 = max1, max1 = num; else if num > max2: max2 = num

3. Return (max1-1) * (max2-1)

function maxProduct(nums) {
  // O(n log n) — clear
  nums.sort((a, b) => b - a);
  return (nums[0] - 1) * (nums[1] - 1);
}

function maxProductLinear(nums) {
  // O(n) — optimal
  let max1 = 0, max2 = 0;
  for (const n of nums) {
    if (n >= max1) { max2 = max1; max1 = n; }
    else if (n > max2) max2 = n;
  }
  return (max1 - 1) * (max2 - 1);
}

console.log(maxProduct([3,4,5,2])); // 12  (5-1)*(4-1)
console.log(maxProduct([1,5,4,5])); // 16  (5-1)*(5-1)

Time: O(n) for linear | Space: O(1)

---

Medium Level

---

Q6. Best Time to Buy and Sell Stock [M][FB]

Problem: Array of prices. Find maximum profit from one buy (must happen before sell).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Profit = sell - buy. To maximize: buy at lowest historical price, sell at current price.

Step 2 — Brute force:

Check every (buy, sell) pair: O(n²). Too slow for large arrays.

Step 3 — Single-pass with min-tracking:

As you scan left to right, track the minimum price seen so far.

At each day: if you sold today, profit = currentPrice - minSoFar.

Track the maximum of all these potential profits.

Step 4 — Algorithm:

1. minPrice = Infinity, maxProfit = 0

2. For each price: update minPrice; update maxProfit = max(maxProfit, price - minPrice)

3. Return maxProfit

Step 5 — Edge cases:

- Prices only falling → maxProfit stays 0 (don't buy)

- Single price → profit = 0

```

[7, 1, 5, 3, 6, 4]

↑ min=1

↑ profit=4 max so far

↑ profit=5 ← answer

```

function maxProfit(prices) {
  let minPrice = Infinity, maxProfit = 0;
  for (const price of prices) {
    minPrice  = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
}

console.log(maxProfit([7,1,5,3,6,4])); // 5  (buy 1, sell 6)
console.log(maxProfit([7,6,4,3,1]));   // 0  (prices falling)
console.log(maxProfit([1,2]));          // 1

Time: O(n) | Space: O(1)

---

Q7. Find All Numbers Disappeared in Array [M]

Problem: Array 1..n with some duplicates. Find all numbers in [1..n] that don't appear. O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values are 1..n → index negation trick (mark visited positions by negating).

Step 2 — Key insight:

After marking all "present" positions by negating, scan for positions still positive → those index+1 values are missing.

Step 3 — Algorithm:

1. For each num: negate arr[Math.abs(num)-1] (only if positive)

2. Scan: collect i+1 for every positive arr[i]

Step 4 — Edge cases:

- Must use Math.abs() because previous elements may already be negated

function findDisappearedNumbers(nums) {
  // Mark visited
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    if (nums[idx] > 0) nums[idx] = -nums[idx];
  }
  // Positive index → that number is missing
  return nums.reduce((acc, val, i) =>
    val > 0 ? [...acc, i + 1] : acc, []);
}

// Cleaner with filter (same logic)
function findDisappearedNumbersClean(nums) {
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    nums[idx] = -Math.abs(nums[idx]);
  }
  return nums.map((v, i) => i + 1).filter((_, i) => nums[i] > 0);
}

console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]
console.log(findDisappearedNumbers([1,1]));              // [2]

Time: O(n) | Space: O(1)

---

Q8. Majority Element — Boyer-Moore [M][FB]

Problem: Find element appearing more than n/2 times. O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

O(1) space with majority constraint → Boyer-Moore Voting.

Step 2 — Intuition:

Imagine the majority element as a "champion". Every fight against a different element results in both dying. Since the champion appears > n/2 times, it always has more fighters than all others combined → it survives.

Step 3 — Algorithm:

1. candidate = null, count = 0

2. For each num:

- if count == 0: candidate = num (new champion)

- if num == candidate: count++ (reinforce champion)

- else: count-- (fight — both die)

3. Return candidate

Step 4 — Trace through example:

```

[2, 2, 1, 1, 1, 2, 2]

cand=2, count=1

cand=2, count=2

count=1 (1 fights 2)

count=0 (1 fights 2 — both die)

cand=1, count=1 (new champion)

count=0 (2 fights 1 — both die)

cand=2, count=1 (new champion)

Result: 2 ✅ (2 is majority)

```

Step 5 — Edge cases:

- Single element: returns it immediately

- Guarantee: majority MUST exist for this to be correct

function majorityElement(nums) {
  let candidate = null, count = 0;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}

console.log(majorityElement([3,2,3]));         // 3
console.log(majorityElement([2,2,1,1,1,2,2])); // 2

Time: O(n) | Space: O(1)

---

Q9. Jump Game — Can Reach End [M][FB]

Problem: nums[i] is max jump from i. Return whether you can reach the last index.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Greedy — track maximum reachable position.

Step 2 — Brute force:

Try every possible jump sequence (DFS/BFS). Exponential time.

Step 3 — Greedy insight:

You don't need to enumerate paths. Just track maxReach — the furthest index reachable from any index we've visited so far. If you reach an index beyond maxReach, you're stuck.

Step 4 — Algorithm:

1. maxReach = 0

2. For each index i (0 to n-1):

- If i > maxReach: impossible to reach here → false

- maxReach = max(maxReach, i + nums[i])

3. Return true

Step 5 — Edge cases:

- Single element: trivially reachable (return true)

- Zero at start with n > 1: false

- Last index doesn't need to be jumped FROM — just reached

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // can't even reach this index
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false (stuck at index 3 which is 0)
console.log(canJump([0]));          // true  (already at last index)

Time: O(n) | Space: O(1)

---

Q10. Spiral Matrix [M]

Problem: Return all elements of an m×n matrix in clockwise spiral order.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Simulation with shrinking boundaries. After visiting each "ring", shrink the boundary.

Step 2 — Key insight:

Maintain 4 boundaries: top, bottom, left, right. Traverse in order: right → down → left → up. After each direction, shrink that boundary.

Step 3 — Algorithm:

1. top=0, bottom=rows-1, left=0, right=cols-1

2. While top <= bottom AND left <= right:

- Top row (left to right), then top++

- Right column (top to bottom), then right--

- Check top<=bottom: Bottom row (right to left), then bottom--

- Check left<=right: Left column (bottom to top), then left++

Step 4 — Edge cases:

- Single row: only "top row" traversal, no other directions

- Single column: only "right column" traversal

- 1×1 matrix: single element

function spiralOrder(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++)    result.push(matrix[top][c]);   top++;
    for (let r = top;  r <= bottom; r++)   result.push(matrix[r][right]); right--;
    if (top <= bottom)
      for (let c = right; c >= left; c--)  result.push(matrix[bottom][c]); bottom--;
    if (left <= right)
      for (let r = bottom; r >= top; r--)  result.push(matrix[r][left]);  left++;
  }
  return result;
}

console.log(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]));
// [1,2,3,6,9,8,7,4,5]
console.log(spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]));
// [1,2,3,4,8,12,11,10,9,5,6,7]

Time: O(m×n) | Space: O(1) extra

---

Q11. Rotate Matrix 90 Degrees [M][FB]

Problem: Rotate an n×n matrix 90° clockwise in-place.

---

🧠 How to Approach This

Step 1 — Math observation:

Element at [row][col] after 90° CW rotation goes to [col][n-1-row].

Step 2 — Two-step trick (Transpose + Reverse):

- Transpose: [row][col] ↔ [col][row]

- Reverse each row: [col][row] → [col][n-1-row]

Combined: [row][col] → [col][n-1-row] ✓ (matches 90° CW formula)

```

Original: Transpose: Reverse each row:

1 2 3 1 4 7 7 4 1

4 5 6 → 2 5 8 → 8 5 2 ← 90° CW ✓

7 8 9 3 6 9 9 6 3

```

Step 3 — Algorithm:

1. Transpose: swap matrix[i][j] with matrix[j][i] for all j > i

2. Reverse each row

Step 4 — Edge cases:

- 1×1 matrix: no-op

- For 90° CCW: reverse each row first, then transpose

function rotate(matrix) {
  const n = matrix.length;
  // Step 1: Transpose (upper triangle only)
  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 (const row of matrix) row.reverse();
  return matrix;
}

console.log(rotate([[1,2,3],[4,5,6],[7,8,9]]));
// [[7,4,1],[8,5,2],[9,6,3]]

Time: O(n²) | Space: O(1)

---

Q12. Longest Consecutive Sequence [M][FB]

Problem: Unsorted array. Find length of longest sequence of consecutive integers. O(n).

---

🧠 How to Approach This

Step 1 — Brute force:

Sort → O(n log n). Question asks O(n).

Step 2 — Hash Set insight:

Add all numbers to a Set (O(1) lookup). Only START counting a sequence if (n-1) is NOT in the Set — meaning n is the beginning. Then count up: n, n+1, n+2...

Step 3 — Why this is O(n):

Each number is visited at most twice — once checking if it's a start, once while counting from a start. Total work = O(n).

Step 4 — Algorithm:

1. Add all to Set

2. For each num: if num-1 not in Set (it's a start):

3. Count while (num+length) in Set

4. Update maxLen

Step 5 — Edge cases:

- Duplicate numbers: Set deduplicates automatically

- Negative numbers: works fine

function longestConsecutive(nums) {
  const set = new Set(nums); // deduplicates
  let maxLen = 0;

  for (const num of set) {
    if (!set.has(num - 1)) {  // only start counting at sequence beginnings
      let len = 1;
      while (set.has(num + len)) len++;
      maxLen = Math.max(maxLen, len);
    }
  }
  return maxLen;
}

console.log(longestConsecutive([100,4,200,1,3,2]));        // 4  [1,2,3,4]
console.log(longestConsecutive([0,3,7,2,5,8,4,6,0,1]));    // 9

Time: O(n) | Space: O(n)

---

Q13. Merge Intervals [M][FB]

Problem: Array of [start,end] intervals. Merge all overlapping intervals.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Sort by start. Once sorted, overlapping intervals are always adjacent.

Step 2 — Key insight:

Two intervals [a,b] and [c,d] overlap if c <= b. Merged = [a, max(b,d)].

Step 3 — Algorithm:

1. Sort by start: intervals.sort((a,b) => a[0] - b[0])

2. result = [first interval]

3. For each interval:

- If start <= result.last.end → merge (extend end)

- Else → add as new interval

Step 4 — Edge cases:

- Single interval: return as-is

- All intervals overlap: merge into one

- No overlaps: all intervals returned unchanged

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const curr = intervals[i];

    if (curr[0] <= last[1]) {
      last[1] = Math.max(last[1], curr[1]); // MERGE
    } else {
      result.push(curr);                     // NO overlap: add new
    }
  }
  return result;
}

console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]
console.log(merge([[1,4],[4,5]]));
// [[1,5]]

Time: O(n log n) | Space: O(n)

---

Q14. Group Anagrams [M][FB]

Problem: Group strings that are anagrams of each other.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Group by canonical key. All anagrams share the same sorted characters.

Step 2 — Key insight:

Sort the characters of each word → anagrams produce identical sorted strings → use as Map key.

```

"eat" → sort → "aet"

"tea" → sort → "aet" ← same group

"tan" → sort → "ant" ← different group

```

Step 3 — Algorithm:

1. Create a Map

2. For each string: sort characters → key

3. Group strings by their key

4. Return Map values

Step 4 — Edge cases:

- Empty string: key = "", valid anagram group by itself

- Single chars: each is its own group

function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

Time: O(n·k·log k) where k = max length | Space: O(n·k)

---

Q15. Next Permutation [M]

Problem: Rearrange array to next lexicographic permutation. In-place.

---

🧠 How to Approach This

Step 1 — Think of it like incrementing a number:

Find rightmost "digit" that can increase, increase it minimally, make everything after as small as possible.

Step 2 — Three-step algorithm:

Step A — Find the pivot (where sequence is no longer descending from right):

Scan from right, find first i where nums[i] < nums[i+1].

Step B — Find the swap target:

Find rightmost j where nums[j] > nums[i] (smallest value bigger than pivot).

Step C — Swap and sort suffix:

Swap nums[i] and nums[j]. Then reverse everything after i (already in descending order → reverse gives ascending).

Step 3 — Trace example:

```

[1, 3, 2]

↑ pivot=1 (index 0, since nums[0]=1 < nums[1]=3)

↑ swap target (nums[2]=2 > nums[0]=1, rightmost)

After swap: [2, 3, 1]

Reverse after 0: [2, 1, 3] ← next permutation ✓

```

Step 4 — Edge cases:

- Descending array [3,2,1]: no pivot → reverse entire array → [1,2,3] (wraps around)

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;

  // Step A: Find pivot
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  if (i >= 0) {
    // Step B: Find swap target
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]]; // swap
  }

  // Step C: Reverse suffix
  let left = i + 1, right = n - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++; right--;
  }
  return nums;
}

console.log(nextPermutation([1,2,3])); // [1,3,2]
console.log(nextPermutation([3,2,1])); // [1,2,3]  (wraps)
console.log(nextPermutation([1,1,5])); // [1,5,1]

Time: O(n) | Space: O(1)

---

Hard Level

---

Q16. First Missing Positive [H][FB]

Problem: Find smallest missing positive integer in O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Key observation:

Answer is in range [1, n+1] (where n = array.length). This lets us use the array as a lookup table.

Step 2 — Cyclic Sort:

Place each number at its "correct" index: value 1 → index 0, value 2 → index 1, etc.

After sorting: first position where arr[i] ≠ i+1 is the answer.

Step 3 — Algorithm:

1. For each index i:

- While nums[i] is in [1..n] AND nums[nums[i]-1] ≠ nums[i]: swap to correct position

2. Scan: first i where nums[i] ≠ i+1 → return i+1

3. If all match: return n+1

Step 4 — Why the while condition works:

- nums[i] > 0 && nums[i] <= n: only care about values in valid range

- nums[nums[i]-1] !== nums[i]: avoid infinite loops for duplicates

Step 5 — Edge cases:

- All negatives: answer is 1

- [1,2,3]: answer is 4

- Has duplicates: condition handles them

function firstMissingPositive(nums) {
  const n = nums.length;

  // Cyclic sort: put each number in its correct spot
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const idx = nums[i] - 1;
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
    }
  }

  // First mismatch is the answer
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

console.log(firstMissingPositive([1,2,0]));    // 3
console.log(firstMissingPositive([3,4,-1,1])); // 2
console.log(firstMissingPositive([7,8,9,11]))); // 1

Time: O(n) | Space: O(1)

---

Q17. Median of Two Sorted Arrays [H][FB]

Problem: Find the median of two sorted arrays in O(log(m+n)) time.

---

🧠 How to Approach This

Step 1 — Understand median:

Median splits a sequence into two equal halves. Left half ≤ right half.

Step 2 — Brute force:

Merge both arrays, find middle. O(m+n). Need O(log(m+n)).

Step 3 — Binary search on partition:

Use binary search to find the right cut in the smaller array. If we take px elements from nums1's left and py elements from nums2's left (where px+py = half of total), we need:

- maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1

If maxLeft1 > minRight2: took too many from nums1 → shrink (right = px-1)

If maxLeft2 > minRight1: took too few from nums1 → grow (left = px+1)

Step 4 — Algorithm:

1. Ensure nums1 is smaller (swap if not)

2. Binary search: left=0, right=m

3. For each partition: compute boundary values (use ±Infinity for edges)

4. If valid partition: compute median from boundary values

Step 5 — Edge cases:

- Partition at edge (0 or m): use -Infinity or +Infinity

- Odd total: median = min(minRight1, minRight2)

- Even total: average of max(maxLeft1, maxLeft2) and min(minRight1, minRight2)

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

  const m = nums1.length, n = nums2.length;
  let left = 0, right = m;

  while (left <= right) {
    const px = Math.floor((left + right) / 2);
    const py = Math.floor((m + n + 1) / 2) - px;

    const maxL1 = px === 0 ? -Infinity : nums1[px - 1];
    const minR1 = px === m ?  Infinity : nums1[px];
    const maxL2 = py === 0 ? -Infinity : nums2[py - 1];
    const minR2 = py === n ?  Infinity : nums2[py];

    if (maxL1 <= minR2 && maxL2 <= minR1) {
      // Correct partition found
      if ((m + n) % 2 === 1) return Math.max(maxL1, maxL2);
      return (Math.max(maxL1, maxL2) + Math.min(minR1, minR2)) / 2;
    } else if (maxL1 > minR2) {
      right = px - 1; // too many from nums1
    } else {
      left = px + 1;  // too few from nums1
    }
  }
}

console.log(findMedianSortedArrays([1,3], [2]));     // 2.0
console.log(findMedianSortedArrays([1,2], [3,4]));   // 2.5

Time: O(log(min(m,n))) | Space: O(1)

---

Q18. Subarray with Equal 0s and 1s [M]

Problem: Binary array. Find length of longest subarray with equal 0s and 1s.

---

🧠 How to Approach This

Step 1 — Transformation trick:

Replace 0 with -1. "Equal 0s and 1s" becomes "subarray sum = 0".

Step 2 — Prefix sum insight:

If prefix sum at index i equals prefix sum at index j (j > i), then subarray [i+1..j] has sum 0.

Step 3 — Algorithm:

1. Map: prefix_sum → first index where it appeared

2. Initialize map with {0: -1} (handles subarrays starting from index 0)

3. For each element: update running sum; if sum seen before: update maxLen

Step 4 — Edge cases:

- Initialize map[0] = -1 (not 0!) so subarrays from start are handled correctly

- Don't overwrite first occurrence → we want maximum length

function findMaxLength(nums) {
  const map = new Map([[0, -1]]); // prefixSum → first index
  let maxLen = 0, sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 1 ? 1 : -1; // 0 becomes -1
    if (map.has(sum)) {
      maxLen = Math.max(maxLen, i - map.get(sum));
    } else {
      map.set(sum, i); // store first occurrence only
    }
  }
  return maxLen;
}

console.log(findMaxLength([0,1]));           // 2
console.log(findMaxLength([0,1,0,1,1,0]));   // 6  (entire array)
console.log(findMaxLength([0,0,1,0,0,1,1])); // 6

Time: O(n) | Space: O(n)

---

Additional Questions

---

Q19. Maximum Product Subarray [M][FB]

Problem: Find contiguous subarray with the largest product.

---

🧠 How to Approach This

Step 1 — Why this is tricky:

Negative × negative = positive! A large negative can flip to become the max.

Step 2 — Track both max AND min:

At each position, keep track of the maximum AND minimum product ending here (because a large negative can become large positive if multiplied by another negative).

Step 3 — Algorithm:

1. For each num: compute candidates = {num, maxPrev×num, minPrev×num}

2. newMax = max of candidates; newMin = min of candidates

3. Update global result = max(result, newMax)

Step 4 — Edge cases:

- Zero resets everything (no carry-over through zeros)

- Single element: return it

function maxProduct(nums) {
  let maxProd = nums[0], minProd = nums[0], result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    const tempMax = Math.max(n, maxProd * n, minProd * n);
    minProd = Math.min(n, maxProd * n, minProd * n);
    maxProd = tempMax;
    result  = Math.max(result, maxProd);
  }
  return result;
}

console.log(maxProduct([2,3,-2,4]));   // 6   subarray [2,3]
console.log(maxProduct([-2,0,-1]));    // 0
console.log(maxProduct([-2,3,-4]));    // 24  full array

Time: O(n) | Space: O(1)

---

Q20. Trapping Rain Water [H][FB]

Problem: Heights of walls. How much water is trapped after rain?

---

🧠 How to Approach This

Step 1 — Water above position i:

= min(maxLeftHeight, maxRightHeight) - height[i]

(bounded by shorter wall on either side)

Step 2 — Brute force:

For each position, scan left and right for max heights. O(n²).

Step 3 — Two Pointers (O(1) space):

Process from the side with the smaller maximum. That side's bound is certain — we know the limiting wall.

Step 4 — Algorithm:

1. L=0, R=n-1, leftMax=0, rightMax=0, water=0

2. While L < R:

- If height[L] < height[R]: process left side, L++

- Else: process right side, R--

Step 5 — Edge cases:

- Heights [1,0,1]: water = 1

- Monotonic array: no water trapped

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) leftMax = height[left];
      else water += leftMax - height[left];
      left++;
    } else {
      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
console.log(trap([4,2,0,3,2,5]));               // 9

Time: O(n) | Space: O(1)

---

Q21. 3Sum — All Triplets Summing to Zero [M][FB]

Problem: Find all unique triplets that sum to zero.

---

🧠 How to Approach This

Step 1 — Brute force: O(n³) — three nested loops. Too slow.

Step 2 — Sort + Two Pointers:

Sort array. For each nums[i], use two pointers to find pair summing to -nums[i].

Step 3 — Skip duplicates:

After fixing nums[i], skip duplicate values. After finding a triplet, skip duplicates at L and R too.

Step 4 — Algorithm:

1. Sort array

2. For each i: if nums[i] === nums[i-1]: skip (duplicate)

3. L=i+1, R=n-1; standard two-sum with two pointers

4. On match: skip duplicates, move both L and R

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate i

    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;   // skip dups
        while (left < right && nums[right] === nums[right - 1]) right--; // skip dups
        left++; right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

console.log(threeSum([-1,0,1,2,-1,-4])); // [[-1,-1,2],[-1,0,1]]

Time: O(n²) | Space: O(1) extra

---

Q22. Subarray Sum Equals K [M][FB]

Problem: Count the number of contiguous subarrays that sum to k.

---

🧠 How to Approach This

Step 1 — Brute force: O(n²) — compute sum for every subarray.

Step 2 — Prefix sum + Hash Map:

If prefixSum[j] - prefixSum[i] = k, then subarray [i+1..j] sums to k.

We want: how many i have prefixSum[i] = prefixSum[j] - k?

Step 3 — Algorithm:

1. Initialize map {0: 1} (empty prefix)

2. For each element: add to running sum

3. count += map.get(sum - k) || 0

4. map.set(sum, (map.get(sum) || 0) + 1)

Step 4 — Edge cases:

- k can be 0 or negative

- Initialize map[0]=1 for subarrays starting at index 0

function subarraySum(nums, k) {
  const map = new Map([[0, 1]]); // prefixSum → count
  let sum = 0, count = 0;

  for (const num of nums) {
    sum += num;
    count += map.get(sum - k) || 0;
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

console.log(subarraySum([1,1,1], 2)); // 2
console.log(subarraySum([1,2,3], 3)); // 2  ([1,2] and [3])

Time: O(n) | Space: O(n)

---

Q23. Product of Array Except Self [M][FB]

Problem: For each index, return product of all OTHER elements. No division allowed.

---

🧠 How to Approach This

Step 1 — Why no division? Division by zero breaks if 0 is in array.

Step 2 — Left×Right pass:

result[i] = (product of everything LEFT of i) × (product of everything RIGHT of i)

Step 3 — O(1) space algorithm:

1. Left pass: result[i] = product of all elements before i

2. Right pass (right to left): multiply result[i] by running right product

Step 4 — Edge cases:

- Contains 0: all positions where no 0 appears become 0 too

- Contains two zeros: all results are 0

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  // Left pass: result[i] = product of nums[0..i-1]
  let leftProd = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProd;
    leftProd *= nums[i];
  }

  // Right pass: multiply result[i] by product of nums[i+1..n-1]
  let rightProd = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProd;
    rightProd *= nums[i];
  }

  return result;
}

console.log(productExceptSelf([1,2,3,4]));     // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]

Time: O(n) | Space: O(1) extra

---

Q24. Container With Most Water [M][FB]

Problem: Heights array. Two lines form container. Maximize water volume.

---

🧠 How to Approach This

Step 1 — Brute force: Try every pair O(n²). Too slow.

Step 2 — Two Pointers insight:

Water = min(height[L], height[R]) × (R - L). As we move pointers in, width decreases. We should keep the TALLER wall and move the SHORTER one (it's our limiting factor — moving the taller one can only decrease water).

Step 3 — Algorithm:

1. L=0, R=n-1

2. Compute water, update max

3. Move shorter pointer inward

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left);
    maxWater = Math.max(maxWater, water);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return maxWater;
}

console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 49
console.log(maxArea([1,1]));               // 1

Time: O(n) | Space: O(1)

---

Q25. Find K-th Largest Element [M][FB]

Problem: Find the k-th largest element in an unsorted array in O(n) average.

---

🧠 How to Approach This

Step 1 — Simple approach: Sort → take index n-k. O(n log n).

Step 2 — Quick Select (O(n) average):

Partition around a pivot (like QuickSort). But only recurse into the side that contains the k-th element. Expected O(n) time.

Step 3 — Algorithm:

1. partition(): rearrange so elements < pivot are left, > pivot are right; return pivot's final index

2. If pivot index === k-1 (0-indexed for k-th largest): found

3. If pivot index < k-1: recurse right half

4. If pivot index > k-1: recurse left half

Step 4 — Edge cases:

- k=1: find maximum

- All same elements: pivot lands in middle

function findKthLargest(nums, k) {
  // Sort approach (simpler, OK in interviews)
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}

// Quick Select (O(n) average)
function findKthLargestOptimal(nums, k) {
  const target = nums.length - k; // k-th largest = (n-k)-th smallest (0-indexed)

  function partition(lo, hi) {
    const pivot = nums[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    return i;
  }

  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(lo, hi);
    if (p === target) return nums[p];
    else if (p < target) lo = p + 1;
    else hi = p - 1;
  }
}

console.log(findKthLargest([3,2,1,5,6,4], 2));    // 5
console.log(findKthLargest([3,2,3,1,2,4,5,5,6], 4)); // 4

Time: O(n) average, O(n²) worst | Space: O(1)

---

Q26. Sliding Window Maximum [H][FB]

Problem: Given array nums and window size k, return the max of each sliding window.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Maximum in every window of size k = Monotonic Deque. Key signals: "max/min in sliding window".

Step 2 — Brute force:

Find max in each of n-k+1 windows → O(n×k). Too slow for large k.

Step 3 — Monotonic Deque insight:

Maintain a deque of indices in decreasing value order. Front = current window max. When a new element arrives, remove all smaller back elements (they can never be max while this element is in the window).

Step 4 — Algorithm:

1. For each right: remove front if index < right-k+1 (out of window)

2. Remove back while nums[back] <= nums[right]

3. Push right to back; if right >= k-1: record nums[front]

Step 5 — Edge cases:

- k=1: each element is its own max

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque  = []; // stores indices

  for (let i = 0; i < nums.length; i++) {
    // Remove out-of-window indices from front
    if (deque.length && deque[0] < i - k + 1) deque.shift();
    // Remove smaller elements from back
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    deque.push(i);
    // Record max when first window is complete
    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]

Time: O(n) | Space: O(k)

---

Q27. Next Greater Element [M][FB]

Problem: For each element, find the next element to its right that is greater. Return -1 if none.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Next greater/smaller" = Monotonic Stack. Elements wait in the stack for their answer.

Step 2 — Brute force:

For each element scan right → O(n²). Too slow.

Step 3 — Monotonic Stack insight:

Stack stores indices whose "next greater" is unknown. When you reach element X: pop all stack elements smaller than X — X is their next greater. Remaining items → -1.

Step 4 — Algorithm:

1. Fill result with -1

2. For each i: while stack not empty AND nums[top] < nums[i] → result[pop] = nums[i]

3. Push i to stack

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack  = []; // indices waiting for next greater

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([2,1,2,4,3])); // [4,2,4,-1,-1]

Time: O(n) | Space: O(n)

---

Q28. Daily Temperatures [M][FB]

Problem: Return an array where each element is the number of days until a warmer temperature. 0 if never.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Days until next warmer" = Next Greater Element variant. Record index distance instead of value.

Step 2 — Monotonic Stack:

Stack stores indices. When today's temp is warmer than stack top, pop and record i - popped_index.

Step 3 — Edge cases:

- Last day: stays in stack, result defaults to 0

function dailyTemperatures(temps) {
  const result = new Array(temps.length).fill(0);
  const stack  = [];

  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const idx      = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }
  return result;
}

console.log(dailyTemperatures([73,74,75,71,69,72,76,73])); // [1,1,4,2,1,1,0,0]

Time: O(n) | Space: O(n)

---

Q29. Find the Duplicate Number [M][FB]

Problem: Array of n+1 integers with values 1–n. Exactly one is duplicated. Find it. No array modification, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values 1..n in array of n+1 = treat as linked list "next pointers" → Floyd's Cycle Detection.

Step 2 — Floyd's insight:

Duplicate value means two indices point to the same "next node", creating a cycle. Cycle entrance = duplicate.

Step 3 — Algorithm:

- Phase 1: slow = 1 step, fast = 2 steps → they meet inside cycle

- Phase 2: reset fast to start, both move 1 step → meet at cycle entrance = duplicate

function findDuplicate(nums) {
  let slow = nums[0], fast = nums[0];

  // Phase 1: detect cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Phase 2: find cycle entrance
  fast = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

console.log(findDuplicate([1,3,4,2,2])); // 2
console.log(findDuplicate([3,1,3,4,2])); // 3

Time: O(n) | Space: O(1)

---

Q30. Longest Increasing Subsequence (LIS) [M][FB]

Problem: Find the length of the longest strictly increasing subsequence.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Longest subsequence = DP. For O(n log n): patience sorting with binary search on tails[].

Step 2 — Patience sort O(n log n):

tails[i] = smallest ending value of all increasing subsequences of length i+1. Binary search to find where each number fits.

Step 3 — Edge cases:

- All decreasing: LIS = 1

- All equal: LIS = 1 (strictly increasing)

function lengthOfLIS(nums) {
  const tails = [];

  for (const num of nums) {
    // Binary search: find first tail >= num
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num; // replace or extend
  }
  return tails.length;
}

console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4  → [2,3,7,101]
console.log(lengthOfLIS([0,1,0,3,2,3]));           // 4

Time: O(n log n) | Space: O(n)

---

Q31. Gas Station [M][FB]

Problem: N gas stations in a circle. gas[i] available, cost[i] to travel to next. Find start station to complete the circuit, or -1.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Circular path with net gain/loss = Greedy (one pass).

Step 2 — Key insight 1:

If total gas >= total cost, a solution is guaranteed to exist (exactly one valid start).

Step 3 — Key insight 2:

If tank runs empty at X starting from S, no station between S and X can be a valid start. Reset start to X+1.

Step 4 — Algorithm:

1. tank=0, total=0, start=0

2. diff = gas[i]-cost[i]; tank += diff; total += diff

3. If tank < 0: start = i+1, tank = 0

4. Return total >= 0 ? start : -1

function canCompleteCircuit(gas, cost) {
  let total = 0, tank = 0, start = 0;

  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    tank  += diff;
    total += diff;
    if (tank < 0) {
      start = i + 1;
      tank  = 0;
    }
  }
  return total >= 0 ? start : -1;
}

console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3
console.log(canCompleteCircuit([2,3,4],     [3,4,3]));      // -1

Time: O(n) | Space: O(1)

---

Q32. Candy Distribution [H][FB]

Problem: N children with ratings. Each gets ≥1 candy. Higher-rated child must get more candies than adjacent lower-rated neighbor. Minimize total candies.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Two directional constraints → Two-pass greedy.

Step 2 — Why one pass fails:

Left-to-right handles "greater than left neighbor". We also need "greater than right neighbor" — requires a separate right-to-left pass.

Step 3 — Algorithm:

- Pass 1 (L→R): if ratings[i] > ratings[i-1], candies[i] = candies[i-1]+1, else candies[i]=1

- Pass 2 (R→L): if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1]+1)

Step 4 — Edge cases:

- All equal: 1 candy each

- Strictly decreasing: n,n-1,...,2,1

function candy(ratings) {
  const n       = ratings.length;
  const candies = new Array(n).fill(1);

  // Pass 1: left to right
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
  }

  // Pass 2: right to left
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((a, b) => a + b, 0);
}

console.log(candy([1, 0, 2])); // 5  → [2,1,2]
console.log(candy([1, 2, 2])); // 4  → [1,2,1]

Time: O(n) | Space: O(n)

---

Q33. Meeting Rooms II [M][FB]

Problem: Given meeting intervals [start, end], find the minimum number of rooms required.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Minimum rooms = maximum overlapping intervals = Sweep Line.

Step 2 — Key insight:

Separate and sort start/end times independently. Two pointers: rooms++ on new start, rooms-- on ended meeting.

Step 3 — Algorithm:

1. Sort starts[], sort ends[] separately

2. s=0, e=0, rooms=0, maxRooms=0

3. If starts[s] < ends[e]: rooms++, s++; else rooms--, e++

4. maxRooms = max(maxRooms, rooms)

function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends   = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, maxRooms = 0, s = 0, e = 0;

  while (s < intervals.length) {
    if (starts[s] < ends[e]) {
      rooms++;
      s++;
    } else {
      rooms--;
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2
console.log(minMeetingRooms([[7,10],[2,4]]));           // 1

Time: O(n log n) | Space: O(n)

---

Q34. K Closest Points to Origin [M][FB]

Problem: Given 2D points, find the K closest to origin (0,0).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

K smallest from N items = sort or max-heap of size K.

Step 2 — Simple O(n log n):

Sort by distance², take first k. Fine in most JS interviews.

Step 3 — Optimal O(n log k):

Maintain max-heap of size k. If new point is closer than heap's max, replace it.

Step 4 — Distance formula:

dist² = x² + y² (no sqrt needed for comparison)

function kClosest(points, k) {
  // Sort by distance squared — O(n log n)
  return points
    .sort((a, b) => (a[0]**2 + a[1]**2) - (b[0]**2 + b[1]**2))
    .slice(0, k);
}

// Quick Select approach O(n) average
function kClosestQuickSelect(points, k) {
  const dist = p => p[0]**2 + p[1]**2;
  let lo = 0, hi = points.length - 1;

  while (lo < hi) {
    const pivot = dist(points[hi]);
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (dist(points[j]) <= pivot) [points[i++], points[j]] = [points[j], points[i]];
    }
    [points[i], points[hi]] = [points[hi], points[i]];
    if (i === k) break;
    else if (i < k) lo = i + 1;
    else hi = i - 1;
  }
  return points.slice(0, k);
}

console.log(kClosest([[1,3],[-2,2]], 1));         // [[-2,2]]
console.log(kClosest([[3,3],[5,-1],[-2,4]], 2));  // [[3,3],[-2,4]]

Time: O(n log n) sort / O(n) QuickSelect | Space: O(1)

---

Q35. Set Matrix Zeroes [M][FB]

Problem: If any cell in an m×n matrix is 0, set its entire row and column to 0. In-place, O(1) extra space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

In-place matrix modification. Use first row/column as flags to mark which rows/cols to zero.

Step 2 — O(1) insight:

matrix[i][0]=0 → "zero row i". matrix[0][j]=0 → "zero col j". First row/col need separate booleans since they double as the flag storage.

Step 3 — Algorithm:

1. Check if row 0 or col 0 originally have zeros (save booleans)

2. Scan i,j > 0: if matrix[i][j]=0, set matrix[i][0]=0 and matrix[0][j]=0

3. Apply flags: zero cells where row flag or col flag is set

4. Zero row 0 / col 0 using saved booleans

function setZeroes(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  let zeroFirstRow = matrix[0].some(v => v === 0);
  let zeroFirstCol = matrix.some(r => r[0] === 0);

  // Mark
  for (let i = 1; i < rows; i++)
    for (let j = 1; j < cols; j++)
      if (matrix[i][j] === 0) { matrix[i][0] = 0; matrix[0][j] = 0; }

  // Zero cells
  for (let i = 1; i < rows; i++)
    for (let j = 1; j < cols; j++)
      if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;

  if (zeroFirstRow) for (let j = 0; j < cols; j++) matrix[0][j] = 0;
  if (zeroFirstCol) for (let i = 0; i < rows; i++) matrix[i][0] = 0;
}

Time: O(m×n) | Space: O(1)

---

Q36. Maximum Sum Circular Subarray [M][FB]

Problem: Find the maximum subarray sum in a circular array (subarray may wrap around).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Circular max = max(normal Kadane's, total − min Kadane's).

Step 2 — Key insight:

A wrapping subarray = total sum minus the middle portion. Minimizing that middle = run Kadane's for minimum.

Step 3 — Algorithm:

1. maxSum = Kadane's max subarray

2. minSum = Kadane's min subarray

3. Return maxSum > 0 ? max(maxSum, total − minSum) : maxSum

Step 4 — Edge cases:

- All negative: skip circular option (it becomes 0, which is invalid)

function maxSubarraySumCircular(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  let maxSum = nums[0], minSum = nums[0];
  let curMax = nums[0], curMin = nums[0];

  for (let i = 1; i < nums.length; i++) {
    curMax = Math.max(nums[i], curMax + nums[i]);
    maxSum = Math.max(maxSum, curMax);
    curMin = Math.min(nums[i], curMin + nums[i]);
    minSum = Math.min(minSum, curMin);
  }

  return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}

console.log(maxSubarraySumCircular([1,-2,3,-2]));  // 3
console.log(maxSubarraySumCircular([5,-3,5]));     // 10
console.log(maxSubarraySumCircular([-3,-2,-3]));   // -2

Time: O(n) | Space: O(1)

---

Q37. Minimum Arrows to Burst Balloons [M]

Problem: Balloons have extents [start, end]. Arrow at x bursts all balloons covering x. Return minimum arrows.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Minimum shots to cover all intervals = Greedy interval scheduling (sort by end).

Step 2 — Key insight:

Shoot at the rightmost point of the first unbursted balloon's range. This bursts as many overlapping balloons as possible. A new arrow is only needed when a balloon starts after the current arrow position.

Step 3 — Algorithm:

1. Sort by end coordinate

2. arrows=1, pos=balloons[0][1]

3. For each balloon: if start > pos → new arrow, pos = balloon[1]

function findMinArrowShots(points) {
  if (!points.length) return 0;
  points.sort((a, b) => a[1] - b[1]); // sort by end

  let arrows = 1;
  let arrowPos = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) {
      arrows++;
      arrowPos = points[i][1];
    }
  }
  return arrows;
}

console.log(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])); // 2
console.log(findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]));    // 4

Time: O(n log n) | Space: O(1)

---

Q38. Subarray Sum Divisible by K [M][FB]

Problem: Count subarrays whose sum is divisible by K.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count subarrays with sum%k=0 = Prefix Sum + Modular Arithmetic + Map.

Step 2 — Key insight:

prefixSum[i]%k = prefixSum[j]%k means sum[j+1..i] % k = 0. Count pairs with same remainder.

Step 3 — Algorithm:

1. remCount = {0:1} (prefix sum 0 seen once before start)

2. sum += num; rem = ((sum%k)+k)%k (normalize negatives)

3. count += remCount[rem]; remCount[rem]++

Step 4 — Edge cases:

- Negative numbers: ((sum%k)+k)%k keeps remainder non-negative

function subarraysDivByK(nums, k) {
  let count = 0, sum = 0;
  const remCount = new Map([[0, 1]]);

  for (const num of nums) {
    sum += num;
    const rem = ((sum % k) + k) % k;
    count += remCount.get(rem) ?? 0;
    remCount.set(rem, (remCount.get(rem) ?? 0) + 1);
  }
  return count;
}

console.log(subarraysDivByK([4,5,0,-2,-3,1], 5)); // 7
console.log(subarraysDivByK([5], 9));              // 0

Time: O(n) | Space: O(k)

---

Q39. Find Minimum in Rotated Sorted Array [M][FB]

Problem: Find the minimum in a rotated sorted array (no duplicates) in O(log n).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Find rotation pivot = Binary Search.

Step 2 — Key insight:

If nums[mid] > nums[right], the min is in the RIGHT half (rotation happened there). Otherwise it's in the LEFT half (including mid).

Step 3 — Algorithm:

1. left=0, right=n-1

2. While left < right: mid = (left+right)>>1

3. If nums[mid] > nums[right]: left = mid+1

4. Else: right = mid

5. Return nums[left]

function findMin(nums) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid;
  }
  return nums[left];
}

console.log(findMin([3,4,5,1,2]));     // 1
console.log(findMin([4,5,6,7,0,1,2])); // 0
console.log(findMin([11,13,15,17]));   // 11

Time: O(log n) | Space: O(1)

---

Q40. Wiggle Subsequence [M]

Problem: A wiggle sequence alternates between increasing and decreasing. Return the length of the longest wiggle subsequence.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count direction changes (peaks + valleys) = Greedy.

Step 2 — Key insight:

Every time the direction flips, we can include that element. Track up (length ending with rise) and down (length ending with fall).

Step 3 — Algorithm:

1. up = down = 1

2. If nums[i] > nums[i-1]: up = down + 1

3. If nums[i] < nums[i-1]: down = up + 1

4. Return max(up, down)

Step 4 — Edge cases:

- All equal: length 1

- Already perfect wiggle: length = n

function wiggleMaxLength(nums) {
  if (nums.length < 2) return nums.length;
  let up = 1, down = 1;

  for (let i = 1; i < nums.length; i++) {
    if      (nums[i] > nums[i - 1]) up   = down + 1;
    else if (nums[i] < nums[i - 1]) down = up   + 1;
  }
  return Math.max(up, down);
}

console.log(wiggleMaxLength([1,7,4,9,2,5]));              // 6
console.log(wiggleMaxLength([1,2,3,4,5,6]));              // 2
console.log(wiggleMaxLength([1,17,5,10,13,15,10,5,16,8])); // 7

Time: O(n) | Space: O(1)

---

Summary: Pattern → When to Use

---

Easy Questions

---

Q1. Find All Duplicates in Array [E][FB]

Way of Thinking: Use a Set — add each number; if already in set, it's a duplicate. O(n) time and space.

function findDuplicates(nums) {
  const seen = new Set();
  const result = [];
  for (const num of nums) {
    if (seen.has(num)) result.push(num);
    else seen.add(num);
  }
  return result;
}

// In-place O(1) space: for 1..n array, negate visited index
function findDuplicatesInPlace(nums) {
  const result = [];
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    if (nums[idx] < 0) result.push(Math.abs(num));
    else nums[idx] = -nums[idx];
  }
  return result;
}

console.log(findDuplicates([4,3,2,7,8,2,3,1])); // [2,3]

---

Q2. Find Missing Number [E][FB]

Way of Thinking: Expected sum = n*(n+1)/2. Subtract actual sum to find missing. XOR method also works (XOR all indices + values → missing number remains).

// Method 1: Sum formula
function missingNumber(nums) {
  const n = nums.length;
  const expected = n * (n + 1) / 2;
  const actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}

// Method 2: XOR
function missingNumberXOR(nums) {
  let xor = nums.length;
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i];
  }
  return xor;
}

console.log(missingNumber([3,0,1])); // 2
console.log(missingNumber([0,1]));   // 2

---

Q3. Single Number — Find Non-Duplicate [E][FB]

Way of Thinking: XOR all numbers. Any number XOR itself = 0. XOR with 0 = the number itself. So the lone number remains.

function singleNumber(nums) {
  return nums.reduce((xor, n) => xor ^ n, 0);
}

console.log(singleNumber([2,2,1]));       // 1
console.log(singleNumber([4,1,2,1,2]));   // 4

---

Q4. Plus One [E]

Way of Thinking: Process from right. If digit < 9, just increment and return. If 9, set to 0 and carry. If all were 9s, prepend 1.

function plusOne(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }
  return [1, ...digits]; // all digits were 9
}

console.log(plusOne([1,2,3])); // [1,2,4]
console.log(plusOne([9,9,9])); // [1,0,0,0]

---

Q5. Maximum Product of Two Elements [E]

function maxProduct(nums) {
  nums.sort((a, b) => b - a);
  return (nums[0] - 1) * (nums[1] - 1);
}

// O(n) without sort
function maxProductLinear(nums) {
  let max1 = 0, max2 = 0;
  for (const n of nums) {
    if (n > max1) { max2 = max1; max1 = n; }
    else if (n > max2) max2 = n;
  }
  return (max1 - 1) * (max2 - 1);
}

console.log(maxProduct([3,4,5,2])); // 12  (4-1)*(5-1)

---

Medium Questions

---

Q6. Best Time to Buy and Sell Stock [M][FB]

Way of Thinking: Track minimum price seen so far. At each day, profit = current - minPrice. Track max profit.

function maxProfit(prices) {
  let minPrice = Infinity, maxProfit = 0;
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
}

console.log(maxProfit([7,1,5,3,6,4])); // 5  (buy 1, sell 6)
console.log(maxProfit([7,6,4,3,1]));   // 0  (no profit possible)

---

Q7. Find All Numbers Disappeared in Array [M]

Way of Thinking: Mark visited by negating value at index (num-1). Numbers at un-negated indices are missing.

function findDisappearedNumbers(nums) {
  // Mark visited
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    nums[idx] = -Math.abs(nums[idx]);
  }
  // Collect indices still positive
  return nums.reduce((acc, val, i) =>
    val > 0 ? [...acc, i + 1] : acc, []);
}

console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]

---

Q8. Majority Element — Boyer-Moore [M][FB]

Way of Thinking: Boyer-Moore voting: candidate and count. If count=0, new candidate. If same as candidate, count++. else count--. The majority element will survive.

function majorityElement(nums) {
  let candidate = null, count = 0;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}

console.log(majorityElement([3,2,3]));         // 3
console.log(majorityElement([2,2,1,1,1,2,2])); // 2

---

Q9. Jump Game — Can Reach End [M][FB]

Way of Thinking: Track the furthest reachable index. If current index is beyond it, we're stuck. If furthest >= last index, return true.

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

console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

---

Q10. Spiral Matrix [M]

Way of Thinking: Track four boundaries: top, bottom, left, right. Traverse each boundary, then shrink it. Stop when boundaries cross.

function spiralOrder(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;
    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }
  return result;
}

console.log(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]));
// [1,2,3,6,9,8,7,4,5]

---

Q11. Rotate Matrix 90 Degrees [M][FB]

Way of Thinking: Step 1: Transpose (swap matrix[i][j] with matrix[j][i]). Step 2: Reverse each row.

function rotate(matrix) {
  const n = matrix.length;
  // 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]];
    }
  }
  // Reverse each row
  for (const row of matrix) row.reverse();
  return matrix;
}

console.log(rotate([[1,2,3],[4,5,6],[7,8,9]]));
// [[7,4,1],[8,5,2],[9,6,3]]

---

Q12. Longest Consecutive Sequence [M][FB]

Way of Thinking: Add all to a Set. Only start counting from a number with no left neighbour (n-1 not in set). Count streak.

function longestConsecutive(nums) {
  const set = new Set(nums);
  let maxLen = 0;

  for (const num of set) {
    if (!set.has(num - 1)) { // start of sequence
      let len = 1;
      while (set.has(num + len)) len++;
      maxLen = Math.max(maxLen, len);
    }
  }
  return maxLen;
}

console.log(longestConsecutive([100,4,200,1,3,2])); // 4  [1,2,3,4]

---

Q13. Merge Intervals [M][FB]

Way of Thinking: Sort by start. For each interval, if it overlaps with last in result (start <= last.end), merge. Otherwise add new.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]); // merge
    } else {
      result.push(intervals[i]);
    }
  }
  return result;
}

console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

---

Q14. Group Anagrams [M][FB]

Way of Thinking: Sort each word's characters → anagrams produce the same key. Group by key in a Map.

function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

---

Q15. Next Permutation [M]

Way of Thinking:

1. Find rightmost index i where nums[i] < nums[i+1]. 2. Find rightmost index j where nums[j] > nums[i]. 3. Swap i and j. 4. Reverse everything after i.

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;

  // Find first decreasing from right
  while (i >= 0 && nums[i] >= nums[i+1]) i--;

  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // Reverse from i+1 to end
  let left = i + 1, right = n - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++; right--;
  }
  return nums;
}

console.log(nextPermutation([1,2,3])); // [1,3,2]
console.log(nextPermutation([3,2,1])); // [1,2,3]

---

Hard Questions

---

Q16. First Missing Positive [H][FB]

Way of Thinking: Cyclic sort: place each number at index (num-1) if 1 <= num <= n. Then scan — first index where arr[i] != i+1 is the answer.

function firstMissingPositive(nums) {
  const n = nums.length;

  // Place numbers in correct positions
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] !== nums[i]) {
      [nums[i], nums[nums[i]-1]] = [nums[nums[i]-1], nums[i]];
    }
  }

  // Find first missing
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

console.log(firstMissingPositive([1,2,0]));   // 3
console.log(firstMissingPositive([3,4,-1,1])); // 2
console.log(firstMissingPositive([7,8,9,11])); // 1

---

Q17. Median of Two Sorted Arrays [H][FB]

Way of Thinking: Binary search on the smaller array's partition point. Ensure left halves of both arrays together = right halves. Check boundary conditions.

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

  const m = nums1.length, n = nums2.length;
  let left = 0, right = m;

  while (left <= right) {
    const px = Math.floor((left + right) / 2);
    const py = Math.floor((m + n + 1) / 2) - px;

    const maxLeftX  = px === 0 ? -Infinity : nums1[px-1];
    const minRightX = px === m ?  Infinity : nums1[px];
    const maxLeftY  = py === 0 ? -Infinity : nums2[py-1];
    const minRightY = py === n ?  Infinity : nums2[py];

    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 1) return Math.max(maxLeftX, maxLeftY);
      return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
    } else if (maxLeftX > minRightY) right = px - 1;
    else left = px + 1;
  }
}

console.log(findMedianSortedArrays([1,3],[2]));     // 2.0
console.log(findMedianSortedArrays([1,2],[3,4]));   // 2.5

---

Q18. Subarray with Equal 0s and 1s [M]

Way of Thinking: Replace 0s with -1s. Find longest subarray with sum = 0 using prefix sum + Map.

function findMaxLength(nums) {
  const map = new Map([[0, -1]]);
  let maxLen = 0, sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 1 ? 1 : -1;
    if (map.has(sum)) {
      maxLen = Math.max(maxLen, i - map.get(sum));
    } else {
      map.set(sum, i);
    }
  }
  return maxLen;
}

console.log(findMaxLength([0,1]));         // 2
console.log(findMaxLength([0,1,0,1,1,0])); // 6