Tracks

Full-Stack Interview Prep

AI Engineering Roadmap →

Searching & Sorting

35 problems · 40 approaches

← Checklist · All topics →

Find first and last positions of an element in a sorted arrayMedium1 approach

Problem

Given an array sorted in ascending order (it may contain duplicates) and a target, return the first and last indices of the target, or [−1, −1] if it is absent. Use O(log n) time.

Example 1

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Example 2

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

1. Two binary searches (lower / upper bound)

Time O(log n)Space O(1)

One search for the leftmost index ≥ target, another for the leftmost index > target.

function searchRange(nums, target) {
  const bound = (isLower) => {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] > target || (isLower && nums[mid] === target)) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  };
  const first = bound(true);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, bound(false) - 1];
}
Search in a rotated sorted arrayMedium1 approach

Problem

A sorted array of distinct values was rotated at some unknown pivot (for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Return the index of target, or −1 if it is absent, in O(log n) time.

Example 1

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Example 2

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

1. Modified binary search

Time O(log n)Space O(1)

One half [lo..mid] or [mid..hi] is always sorted. Check whether target lies in the sorted half and recurse there.

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) { // left half sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                     // right half sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
Kth smallest numberMedium3 approaches

Problem

Given an unsorted array and k, return the kth smallest element (k = 1 means the minimum). Sorting is O(n log n). Aim for O(n log k), or O(n) on average.

Example 1

Input:  arr = [7, 10, 4, 3, 20, 15], k = 3
Output: 7

Also asked as: kth smallest element · Find the Kth max and min element of an array · Kth smallest number again · Kth smallest number

1. Max-heap of size k

Time O(n log k)Space O(k)

Keep the k smallest seen so far in a max-heap; its root is the answer.

// uses the MinHeap/MaxHeap idea; here with a sorted array for brevity
function kthSmallest(a, k) {
  const heap = []; // acts as a max-heap of size k (kept sorted desc)
  for (const x of a) {
    if (heap.length < k) heap.push(x), heap.sort((p, q) => q - p);
    else if (x < heap[0]) { heap[0] = x; heap.sort((p, q) => q - p); }
  }
  return heap[0];
}

With a real binary max-heap the per-element work is O(log k) instead of O(k log k).

2. Quickselect

Time O(n) avg, O(n²) worstSpace O(1)

Partition like quicksort but only recurse into the side containing index k−1. Average linear.

function kthSmallest(a, k) {
  let lo = 0, hi = a.length - 1;
  const target = k - 1;
  while (lo < hi) {
    const pivot = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) if (a[j] < pivot) [a[i], a[j]] = [a[j], a[i]], i++;
    [a[i], a[hi]] = [a[hi], a[i]];
    if (i === target) return a[i];
    if (i < target) lo = i + 1; else hi = i - 1;
  }
  return a[lo];
}

3. Sort

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

Sort and index. Simplest; the baseline you state first.

const kthSmallest = (a, k) => [...a].sort((x, y) => x - y)[k - 1];
Find a fixed point (value equal to index)Easy1 approach

Problem

Given a sorted array of distinct integers, return an index i with arr[i] === i, or −1 if there is none.

Example 1

Input:  [-10, -5, 0, 3, 7]
Output: 3

Example 2

Input:  [-10, -5, 3, 4, 7, 9]
Output: -1

Also asked as: Find a Fixed Point (Value equal to index) in a given array

1. Binary search (distinct sorted array)

Time O(log n)Space O(1)

If a[mid] === mid you are done. If a[mid] < mid the fixed point can only be on the right, else on the left.

function fixedPoint(a) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === mid) return mid;
    a[mid] < mid ? (lo = mid + 1) : (hi = mid - 1);
  }
  return -1;
}
Integer square rootEasy1 approach

Problem

Given a non-negative integer x, return floor(√x) without using a built-in square-root function.

Example 1

Input:  x = 8
Output: 2

√8 ≈ 2.83.

Example 2

Input:  x = 16
Output: 4

Also asked as: square root of an integer

1. Binary search on the answer

Time O(log x)Space O(1)

Search 0..x for the largest m with m·m ≤ x.

function isqrt(x) {
  if (x < 2) return x;
  let lo = 1, hi = x, ans = 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (mid <= x / mid) { ans = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  return ans;
}
Find the repeating and the missing numberMedium1 approach

Problem

An array of size n should contain every number from 1 to n exactly once. Instead, one number appears twice and one is missing. Return both.

Example 1

Input:  [3, 1, 3]
Output: repeating = 3, missing = 2

Also asked as: Find the repeating and the missing

1. Sum and sum-of-squares

Time O(n)Space O(1)

Let S = Σa − Σ1..n = repeat − missing, and P = Σa² − Σi² = repeat² − missing². Solve the two equations.

function repeatAndMissing(a) {
  const n = a.length;
  let s = 0, p = 0;
  for (let i = 1; i <= n; i++) {
    s += a[i - 1] - i;
    p += a[i - 1] * a[i - 1] - i * i;
  }
  // s = r - m,  p = r^2 - m^2 = (r - m)(r + m)  =>  r + m = p / s
  const sum = p / s;
  const repeat = (s + sum) / 2;
  return { repeat, missing: repeat - s };
}

XOR method avoids overflow: xor all a and 1..n, isolate a set bit, bucket into two groups.

Majority element (> n/2 times)Easy1 approach

Problem

Return the element that appears more than n/2 times, or −1 if no such element exists. Aim for O(n) time and O(1) space.

Example 1

Input:  [2, 2, 1, 1, 1, 2, 2]
Output: 2

Example 2

Input:  [3, 1, 3, 3, 2]
Output: 3

Also asked as: find majority element

1. Boyer–Moore voting

Time O(n)Space O(1)

Keep a candidate and a count; +1 on a match, −1 otherwise; reset the candidate when count hits 0. A final scan verifies.

function majorityElement(a) {
  let cand = null, count = 0;
  for (const x of a) {
    if (count === 0) cand = x;
    count += x === cand ? 1 : -1;
  }
  return a.filter((x) => x === cand).length > a.length / 2 ? cand : -1;
}
Search in an array where adjacent elements differ by at most kEasy1 approach

Problem

Adjacent elements of the array differ by at most k. Return the first index of x, doing better than checking every element in turn.

Example 1

Input:  arr = [4, 5, 6, 7, 6], k = 1, x = 6
Output: 2

Also asked as: Searching in an array where adjacent differ by at most k

1. Jump by the guaranteed gap

Time O(n / k) roughlySpace O(1)

Since neighbours differ by ≤ k, the target is at least |a[i] − target| / k positions away — skip that many.

function search(a, k, target) {
  let i = 0;
  while (i < a.length) {
    if (a[i] === target) return i;
    i += Math.max(1, Math.floor(Math.abs(a[i] - target) / k));
  }
  return -1;
}
Find a pair with a given differenceEasy1 approach

Problem

Return true if there are two elements (at different indices) whose difference is exactly n.

Example 1

Input:  arr = [5, 20, 3, 2, 50, 80], n = 78
Output: true

80 − 2 = 78.

Also asked as: find a pair with a given difference

1. Sort + two pointers

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

Sort ascending. Move two pointers so that a[j] − a[i] converges on the target difference.

function pairWithDiff(a, d) {
  a.sort((x, y) => x - y);
  let i = 0, j = 1;
  while (i < a.length && j < a.length) {
    const diff = a[j] - a[i];
    if (i !== j && diff === d) return [a[i], a[j]];
    if (diff < d) j++;
    else i++;
  }
  return null;
}
Find four elements that sum to a given value (4-sum)Medium1 approach

Problem

Return every unique quadruplet of values (from distinct indices) that sums to target. Do not repeat the same set of values.

Example 1

Input:  nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]

Also asked as: find four elements that sum to a given value

1. Sort + fix two + two pointers

Time O(n³)Space O(1)

Two nested loops fix a and b; a two-pointer scan finds c, d for the remaining target. Skip duplicates.

function fourSum(a, target) {
  a.sort((x, y) => x - y);
  const res = [];
  const n = a.length;
  for (let i = 0; i < n - 3; i++) {
    if (i && a[i] === a[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && a[j] === a[j - 1]) continue;
      let l = j + 1, r = n - 1;
      while (l < r) {
        const s = a[i] + a[j] + a[l] + a[r];
        if (s === target) {
          res.push([a[i], a[j], a[l], a[r]]);
          while (l < r && a[l] === a[l + 1]) l++;
          while (l < r && a[r] === a[r - 1]) r--;
          l++; r--;
        } else if (s < target) l++;
        else r--;
      }
    }
  }
  return res;
}
Count triplets with sum smaller than a given valueMedium1 approach

Problem

Return the number of index triplets i < j < k with arr[i] + arr[j] + arr[k] < sum.

Example 1

Input:  arr = [-2, 0, 1, 3], sum = 2
Output: 2

(−2, 0, 1) and (−2, 0, 3).

Also asked as: Count triplet with sum smaller than a given value

1. Sort + two pointers

Time O(n²)Space O(1)

Fix i; with l = i+1 and r = end, if a[i]+a[l]+a[r] < target then all r−l triplets between l and r qualify — advance l; otherwise decrease r.

function countTriplets(a, target) {
  a.sort((x, y) => x - y);
  let count = 0;
  for (let i = 0; i < a.length - 2; i++) {
    let l = i + 1, r = a.length - 1;
    while (l < r) {
      if (a[i] + a[l] + a[r] < target) { count += r - l; l++; }
      else r--;
    }
  }
  return count;
}
Merge two sorted arrays into a new arrayEasy1 approach

Problem

Merge two sorted arrays into a single new sorted array.

Example 1

Input:  a = [1, 3, 5], b = [2, 4, 6, 8]
Output: [1, 2, 3, 4, 5, 6, 8]

Also asked as: merge 2 sorted arrays

1. Two pointers

Time O(n + m)Space O(n + m)

Repeatedly take the smaller head of the two arrays.

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}
Product array puzzle (product of all except self)Medium1 approach

Problem

Return an array whose ith element is the product of every element except nums[i]. Do not use division, and aim for O(n) time.

Example 1

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Example 2

Input:  [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Also asked as: Product array Puzzle

1. Prefix and suffix products, no division

Time O(n)Space O(1) extra

res[i] = (product of everything left of i) · (product of everything right of i). Two passes; reuse the output array.

function productExceptSelf(a) {
  const n = a.length, res = Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) { res[i] = prefix; prefix *= a[i]; }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= a[i]; }
  return res;
}
Sort an array by the number of set bitsEasy1 approach

Problem

Sort the integers in decreasing order of how many 1 bits their binary form has. Numbers with the same count keep their original relative order (a stable sort).

Example 1

Input:  [5, 2, 3, 9, 4, 6, 7, 15, 32]
Output: [15, 7, 5, 3, 9, 6, 2, 4, 32]

Also asked as: Sort array according to count of set bits

1. Stable sort with a popcount comparator

Time O(n log n)Space O(n)

Sort descending by popcount; ties keep their original order (use a stable sort or a secondary key).

const popcount = (x) => { let c = 0; while (x) { x &= x - 1; c++; } return c; };
function sortBySetBits(a) {
  return a
    .map((v, i) => [v, i, popcount(v)])
    .sort((p, q) => q[2] - p[2] || p[1] - q[1])
    .map((t) => t[0]);
}
Minimum number of swaps to sort an arrayMedium1 approach

Problem

The array holds distinct values. Return the minimum number of swaps (of any two elements) needed to sort it.

Example 1

Input:  [2, 8, 5, 4]
Output: 1

Swap 8 and 4.

Example 2

Input:  [10, 19, 6, 3, 5]
Output: 2

Also asked as: minimum no. of swaps required to sort the array

1. Cycle decomposition

Time O(n log n)Space O(n)

Pair each value with its target index; the permutation splits into cycles. A cycle of length L needs L−1 swaps.

function minSwaps(a) {
  const sorted = a.map((v, i) => [v, i]).sort((x, y) => x[0] - y[0]);
  const seen = Array(a.length).fill(false);
  let swaps = 0;
  for (let i = 0; i < a.length; i++) {
    if (seen[i] || sorted[i][1] === i) continue;
    let len = 0, j = i;
    while (!seen[j]) { seen[j] = true; j = sorted[j][1]; len++; }
    swaps += len - 1;
  }
  return swaps;
}
Bishu and SoldiersMedium1 approach

Problem

Bishu has power P. He defeats every soldier whose power is at most P. Given the soldiers' powers and several queries of P, report for each query how many soldiers he defeats and the sum of their powers.

Example 1

Input:  powers = [1, 2, 3, 4, 5, 6, 7], queries = [3, 10, 2]
Output: (3, 6), (7, 28), (2, 3)

Also asked as: Bishu and Soldiers

1. Sort + prefix sums + binary search per query

Time O(n log n + q log n)Space O(n)

Sort soldier powers, precompute prefix sums. For each round power P, binary-search the count of soldiers with power ≤ P and read the matching prefix sum.

function bishu(powers, queries) {
  powers.sort((a, b) => a - b);
  const prefix = [0];
  for (const p of powers) prefix.push(prefix[prefix.length - 1] + p);
  return queries.map((P) => {
    let lo = 0, hi = powers.length;
    while (lo < hi) { const mid = (lo + hi) >> 1; powers[mid] <= P ? (lo = mid + 1) : (hi = mid); }
    return { killed: lo, powerGained: prefix[lo] };
  });
}
Kth element of two sorted arraysMedium2 approaches

Problem

Given two sorted arrays, return the kth smallest element (1-indexed) of their combined sorted order, without merging them. Aim for O(log(min(m, n))).

Example 1

Input:  a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5
Output: 6

Also asked as: K-th Element of Two Sorted Arrays

1. Merge until k (simple)

Time O(k)Space O(1)

Two pointers; take k−1 smaller heads, the kth is the answer.

function kthElement(a, b, k) {
  let i = 0, j = 0;
  while (true) {
    if (i === a.length) return b[j + k - 1];
    if (j === b.length) return a[i + k - 1];
    if (k === 1) return Math.min(a[i], b[j]);
    a[i] <= b[j] ? i++ : j++;
    k--;
  }
}

2. Binary search on the split (O(log)

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

Same partition idea as "median of two sorted arrays": pick how many come from a, derive the rest from b, adjust until the split is valid.

function kthElement(a, b, k) {
  if (a.length > b.length) [a, b] = [b, a];
  let lo = Math.max(0, k - b.length), hi = Math.min(k, a.length);
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = k - i;
    const aL = i > 0 ? a[i - 1] : -Infinity;
    const aR = i < a.length ? a[i] : Infinity;
    const bL = j > 0 ? b[j - 1] : -Infinity;
    const bR = j < b.length ? b[j] : Infinity;
    if (aL <= bR && bL <= aR) return Math.max(aL, bL);
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
}
Binary search on the answer — Aggressive Cows, Book Allocation, Painter’s Partition, EKO, ROTI-PrataMedium3 approaches

Problem

A family of problems where you binary-search the answer itself:

Aggressive Cows — place c cows in n stalls (given positions) so that the minimum distance between any two cows is as large as possible. Return that distance.

Book Allocation / Painter's Partition — split an array into k contiguous parts so that the largest part-sum is as small as possible. Return that sum.

EKO — choose the tallest saw height H such that the wood cut from the tree tops above H is at least M.

ROTI-Prata — cooks with given ranks make p pratas together (a rank-r cook needs r, 2r, 3r… minutes for successive pratas). Return the minimum time.

Example 1

Input:  Cows: stalls = [1, 2, 4, 8, 9], cows = 3
Output: 3

Place them at 1, 4 and 8 (or 9).

Example 2

Input:  Books: pages = [12, 34, 67, 90], students = 2
Output: 113

[12, 34, 67] and [90].

Also asked as: Aggressive cows · Book Allocation Problem · Painters Partition Problem · EKOSPOJ · ROTI-Prata SPOJ · Job Scheduling Algo

1. The pattern

Time O(n · log(range))Space O(1)

These all ask for the min/max feasible value of some quantity. The feasibility check is monotonic, so binary-search the answer space and test each candidate greedily in O(n).

// generic driver
function binarySearchAnswer(lo, hi, feasible) {
  // finds the smallest value in [lo, hi] for which feasible() is true
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    feasible(mid) ? (hi = mid) : (lo = mid + 1);
  }
  return lo;
}

2. Aggressive Cows — maximise the minimum gap

Time O(n log n + n log(range))Space O(1)

Sort stalls. For a candidate min distance d, greedily place cows; feasible if you can place all C. Search for the largest feasible d.

function aggressiveCows(stalls, cows) {
  stalls.sort((a, b) => a - b);
  const canPlace = (d) => {
    let placed = 1, last = stalls[0];
    for (let i = 1; i < stalls.length; i++)
      if (stalls[i] - last >= d) { placed++; last = stalls[i]; }
    return placed >= cows;
  };
  let lo = 1, hi = stalls[stalls.length - 1] - stalls[0], ans = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (canPlace(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
  }
  return ans;
}

3. Book Allocation / Painter’s Partition — minimise the maximum load

Time O(n log(sum))Space O(1)

For a candidate max load per student/painter, greedily fill; feasible if the number of groups ≤ k. Search for the smallest feasible max.

function allocateBooks(pages, students) {
  const fits = (limit) => {
    let groups = 1, cur = 0;
    for (const p of pages) {
      if (p > limit) return false;
      if (cur + p > limit) { groups++; cur = p; } else cur += p;
    }
    return groups <= students;
  };
  let lo = Math.max(...pages), hi = pages.reduce((a, b) => a + b, 0), ans = hi;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (fits(mid)) { ans = mid; hi = mid - 1; } else lo = mid + 1;
  }
  return ans;
}

EKO (cut trees at height h so total wood ≥ M): binary-search h, feasibility = Σ max(0, tree − h) ≥ M. ROTI-Prata (finish P pratas in time T with cooks of rank r): binary-search T, feasibility = Σ (pratas each cook can make in T) ≥ P.

Find pivot (minimum) in a rotated sorted arrayMedium1 approach

Problem

A sorted array of distinct values was rotated at an unknown point. Return its minimum element (the rotation point) in O(log n) time.

Example 1

Input:  [3, 4, 5, 1, 2]
Output: 1

Example 2

Input:  [11, 13, 15, 17]
Output: 11

Not rotated.

Also asked as: Find pivot element in a sorted array

1. Binary search for the rotation point

Time O(log n)Space O(1)

If a[mid] > a[hi] the minimum is to the right of mid; otherwise it is mid or to the left.

function findMin(a) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] > a[hi]) lo = mid + 1;
    else hi = mid;
  }
  return a[lo]; // lo is the rotation (pivot) index
}
Missing number in an arithmetic progressionEasy1 approach

Problem

The array is an arithmetic progression with exactly one term missing from the middle. Return the missing term in O(log n) time.

Example 1

Input:  [2, 4, 8, 10, 12, 14]
Output: 6

Also asked as: Missing Number in AP

1. Binary search using the common difference

Time O(log n)Space O(1)

d = (last − first) / n (with one term missing there are n terms of an original n+1). The missing element is where a[mid] !== first + mid·d.

function missingInAP(a) {
  const n = a.length;
  const d = (a[n - 1] - a[0]) / n; // n gaps expected across n+1 terms
  let lo = 0, hi = n - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === a[0] + mid * d) lo = mid + 1;
    else hi = mid;
  }
  return a[0] + lo * d;
}
Smallest number whose factorial has at least n trailing zerosMedium1 approach

Problem

Return the smallest integer m such that m! ends with at least n zeros.

Example 1

Input:  n = 1
Output: 5

5! = 120.

Example 2

Input:  n = 6
Output: 25

25! has 6 trailing zeros, but 24! has only 4.

Also asked as: Smallest number with atleastn trailing zeroes infactorial

1. Binary search + Legendre's formula (count factors of 5)

Time O(log²(n))Space O(1)

Trailing zeros in m! = floor(m/5) + floor(m/25) + … Binary-search the smallest m whose count ≥ n.

function smallestFactorialWithZeros(n) {
  const zeros = (m) => { let c = 0; for (let p = 5; p <= m; p *= 5) c += Math.floor(m / p); return c; };
  let lo = 0, hi = 5 * n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    zeros(mid) < n ? (lo = mid + 1) : (hi = mid);
  }
  return lo;
}
DoubleHelix — maximum sum path across two arraysMedium1 approach

Problem

Two sorted arrays share some values ("intersection points"). You walk through one array from left to right, and at any shared value you may switch to the other array and continue from that value. Return the largest possible sum of the values you visit.

Example 1

Input:  a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62], b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100]
Output: 450

Also asked as: DoubleHelix SPOJ

1. Merge with segment sums, switch at common elements

Time O(n + m)Space O(1)

Walk both sorted arrays with two pointers, accumulating a running sum for each. At a common value, add the larger of the two running sums to the total and reset both.

function doubleHelix(a, b) {
  let i = 0, j = 0, sumA = 0, sumB = 0, total = 0;
  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) sumA += a[i++];
    else if (a[i] > b[j]) sumB += b[j++];
    else {
      total += Math.max(sumA, sumB) + a[i];
      sumA = sumB = 0; i++; j++;
    }
  }
  while (i < a.length) sumA += a[i++];
  while (j < b.length) sumB += b[j++];
  return total + Math.max(sumA, sumB);
}
Subset sums (all possible sums of subsets)Easy1 approach

Problem

Return the sums of all 2^n subsets of the array (including the empty subset, which sums to 0), in any order or sorted.

Example 1

Input:  [2, 3]
Output: [0, 2, 3, 5]

Also asked as: Subset Sums

1. Recurse: include / exclude each element

Time O(2ⁿ)Space O(n) recursion

At each index branch on taking the element into the running sum or not; record the sum at the leaves.

function subsetSums(a) {
  const res = [];
  const bt = (i, sum) => {
    if (i === a.length) { res.push(sum); return; }
    bt(i + 1, sum + a[i]);
    bt(i + 1, sum);
  };
  bt(0, 0);
  return res.sort((x, y) => x - y);
}
Implement in-place merge sortHard1 approach

Problem

Sort an array with merge sort, but merge the two halves inside the array itself rather than into an auxiliary array. Explain the time-and-space trade-off this makes.

Example 1

Input:  [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]

Also asked as: Implement Merge-sort in-place

1. Merge sort with the gap (Shell) merge

Time O(n log² n)Space O(log n) recursion

Standard recursive split, but merge the two halves in place using the decreasing-gap comparison-and-swap instead of a temp buffer.

function mergeSortInPlace(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const mid = (lo + hi) >> 1;
  mergeSortInPlace(a, lo, mid);
  mergeSortInPlace(a, mid + 1, hi);
  let gap = Math.ceil((hi - lo + 1) / 2);
  while (gap > 0) {
    for (let i = lo; i + gap <= hi; i++)
      if (a[i] > a[i + gap]) [a[i], a[i + gap]] = [a[i + gap], a[i]];
    gap = gap === 1 ? 0 : Math.ceil(gap / 2);
  }
  return a;
}
Sort an array with many repeated entries (3-way quicksort)Medium1 approach

Problem

Sort an array that has many duplicate values efficiently. Plain quicksort degrades to O(n²) on many equal keys. Partition into less than, equal to and greater than the pivot instead.

Example 1

Input:  [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4]
Output: [1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]

Also asked as: Partitioning and Sorting Arrays with Many Repeated Entries

1. 3-way (Dutch flag) quicksort

Time O(n log n), O(n·k) for k distinct keysSpace O(log n)

Partition into < pivot, === pivot, > pivot. The equal band is skipped entirely, so duplicates cost nothing — O(n) when few distinct keys.

function quicksort3(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const pivot = a[(lo + hi) >> 1];
  let lt = lo, gt = hi, i = lo;
  while (i <= gt) {
    if (a[i] < pivot) [a[lt++], a[i++]] = [a[i], a[lt]];
    else if (a[i] > pivot) [a[i], a[gt--]] = [a[gt], a[i]];
    else i++;
  }
  quicksort3(a, lo, lt - 1);
  quicksort3(a, gt + 1, hi);
  return a;
}
Optimum location of a point to minimise total distanceHard1 approach

Problem

Given points and a line ax + by + c = 0, find the point on the line that minimises the sum of Euclidean distances to all the points. Return that minimum sum. The sum is unimodal along the line, so ternary search works.

Example 1

Input:  line x − y − 3 = 0, points [(-3,-2), (-1,0), (-1,2), (1,2), (3,4)]
Output: ≈ 20.77

Also asked as: Optimum location of point to minimize total distance

1. Ternary search on the line (convex objective)

Time O(n · log(1/ε))Space O(1)

The sum of Euclidean distances from a point on a given line to fixed points is a convex function of the position along the line, so ternary-search the parameter.

function optimumLocation(points, line) { // line: [a, b, c] for ax + by + c = 0
  const [a, b, c] = line;
  const pointAt = (t) => {
    // parametrise the line; here assume b !== 0: x = t, y = -(a*t + c)/b
    return [t, -(a * t + c) / b];
  };
  const cost = (t) => {
    const [x, y] = pointAt(t);
    return points.reduce((s, [px, py]) => s + Math.hypot(px - x, py - y), 0);
  };
  let lo = -1e6, hi = 1e6;
  for (let iter = 0; iter < 200; iter++) {
    const m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
    if (cost(m1) < cost(m2)) hi = m2; else lo = m1;
  }
  return cost(lo);
}
Rasta and Kheshtak (largest common square submatrix pattern)Hard1 approach

Problem

Given two matrices of integers, return the side length of the largest square pattern that appears in both. Binary-search the side length and compare 2-D rolling hashes of the squares.

Example 1

Input:  two small matrices sharing a 2 × 2 block
Output: 2

Also asked as: Rasta and Kheshtak

1. Binary search on the square size + hashing

Time O(R·C·log(min(R,C)))Space O(R·C)

Binary-search the side length k. For each candidate k, hash every k×k submatrix of both grids (2-D rolling hash / prefix hashing) and check for a common hash. Largest k with an intersection is the answer.

// sketch — 2D prefix hashing
function has_common_square(A, B, k) {
  const hashesA = new Set();
  const grab = (G, out) => {
    for (let r = 0; r + k <= G.length; r++)
      for (let c = 0; c + k <= G[0].length; c++) {
        let h = '';
        for (let i = 0; i < k; i++) h += G[r + i].slice(c, c + k).join(',') + ';';
        out.add(h);
      }
  };
  grab(A, hashesA);
  const hashesB = new Set();
  grab(B, hashesB);
  for (const h of hashesB) if (hashesA.has(h)) return true;
  return false;
}

The string concatenation above is O(k²) per window; a real solution uses polynomial 2-D rolling hashes for O(1) per window.

Maximum sum such that no two elements are adjacent (House Robber)Easy1 approach

Problem

Pick elements of the array so that no two chosen elements are adjacent, maximising their sum. In House Robber the values are money in houses along a street.

Example 1

Input:  [2, 7, 9, 3, 1]
Output: 12

2 + 9 + 1.

Also asked as: maximum sum such that no 2 elements are adjacent · House Robber · Maximum sum such that no two are adjacent

1. Pick / skip DP, O(1) space

Time O(n)Space O(1)

best[i] = max(best[i-1], best[i-2] + a[i]) — either skip element i or take it and add the best up to i-2.

function maxNonAdjacentSum(a) {
  let incl = 0, excl = 0;
  for (const x of a) {
    const newExcl = Math.max(incl, excl);
    incl = excl + x;
    excl = newExcl;
  }
  return Math.max(incl, excl);
}
Find Peak ElementMedium1 approach

Problem

A peak is an element strictly greater than its neighbours. Imagine nums[−1] = nums[n] = −∞, and no two adjacent elements are equal. Return the index of any peak, in O(log n) time.

Example 1

Input:  [1, 2, 3, 1]
Output: 2

Example 2

Input:  [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5

1. Binary search on the slope

Time O(log n)Space O(1)

If nums[mid] < nums[mid + 1] a peak lies to the right (the sequence must come down eventually); otherwise one lies at mid or to the left.

function findPeakElement(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
Time Based Key-Value StoreMedium1 approach

Problem

Design a store with set(key, value, timestamp) and get(key, timestamp). get returns the value from the latest set for that key whose timestamp is ≤ the given timestamp, or "" if there is none. Timestamps for set arrive in strictly increasing order.

Example 1

Input:  set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5)
Output: "bar", "bar", "bar2", "bar2"

1. Per-key list + upper-bound search

Time set O(1), get O(log n)Space O(n)

Timestamps arrive increasing, so each key’s list is already sorted. get finds the last entry with timestamp ≤ t.

class TimeMap {
  constructor() { this.m = new Map(); }
  set(key, value, t) {
    if (!this.m.has(key)) this.m.set(key, []);
    this.m.get(key).push([t, value]);
  }
  get(key, t) {
    const a = this.m.get(key) ?? [];
    let lo = 0, hi = a.length; // first index with time > t
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (a[mid][0] <= t) lo = mid + 1;
      else hi = mid;
    }
    return lo === 0 ? '' : a[lo - 1][1];
  }
}
Koko Eating BananasMedium1 approach

Problem

There are piles of bananas and h hours. Each hour Koko picks one pile and eats k bananas from it (or the whole pile if it has fewer). Return the minimum integer speed k that lets her finish every pile within h hours.

Example 1

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4

Example 2

Input:  piles = [30, 11, 23, 4, 20], h = 5
Output: 30

1. Binary search on the speed

Time O(n log max)Space O(1)

Hours needed falls as speed rises (monotonic). Find the smallest speed in [1, max pile] that finishes within h.

function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const k = (lo + hi) >> 1;
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);
    if (hours <= h) hi = k;
    else lo = k + 1;
  }
  return lo;
}
Capacity To Ship Packages Within D DaysMedium1 approach

Problem

Packages must be shipped in the given order. Each day the ship carries a prefix of the remaining packages, with total weight at most its capacity. Return the minimum capacity that ships everything within days days.

Example 1

Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

[1–5], [6, 7], [8], [9], [10].

1. Binary search on capacity + greedy check

Time O(n log sum)Space O(1)

Capacity lies between the heaviest package and the total weight. For a guess, greedily fill each day and count days.

function shipWithinDays(weights, days) {
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);
  const daysNeeded = (cap) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d;
  };
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (daysNeeded(mid) <= days) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}
Minimum Number of Days to Make m BouquetsMedium1 approach

Problem

Flower i blooms on day bloomDay[i]. A bouquet needs k adjacent bloomed flowers, and each flower can be used once. Return the minimum day by which you can make m bouquets, or −1 if it is impossible.

Example 1

Input:  bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Output: 3

Example 2

Input:  bloomDay = [1, 10, 3, 10, 2], m = 3, k = 2
Output: -1

That needs 6 flowers, but there are only 5.

1. Binary search on the day

Time O(n log max)Space O(1)

By day d every flower with bloomDay ≤ d is open; count runs of k adjacent open flowers. More days never means fewer bouquets.

function minDays(bloomDay, m, k) {
  if (m * k > bloomDay.length) return -1;
  const canMake = (day) => {
    let bouquets = 0, run = 0;
    for (const b of bloomDay) {
      run = b <= day ? run + 1 : 0;
      if (run === k) { bouquets++; run = 0; }
    }
    return bouquets >= m;
  };
  let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canMake(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}