Reverse the arrayEasy2 approaches
Problem
Given an array, reverse it in place so the first element becomes the last and so on. Return the same array.
Example 1
Input: [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1]
1. Two pointers (in place)
Time O(n)Space O(1)
Swap the ends and walk inward until the pointers meet.
function reverse(a) { let l = 0, r = a.length - 1; while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; } return a;}2. Recursion
Time O(n)Space O(n) call stack
Swap outermost pair, recurse on the inner subarray. Shows recursion but costs stack.
function reverse(a, l = 0, r = a.length - 1) { if (l >= r) return a; [a[l], a[r]] = [a[r], a[l]]; return reverse(a, l + 1, r - 1);}Kadane's AlgoMedium3 approaches
Problem
Given an integer array (it may contain negative numbers), find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.
Example 1
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6
The subarray [4, -1, 2, 1] has sum 6.
Example 2
Input: [-3, -1, -2] Output: -1
All negative: the best is the single largest element.
Also asked as: find Largest sum contiguous Subarray · largest sum contiguous subarray
1. Kadane (running sum)
Time O(n)Space O(1)
At each index keep the best subarray sum ending here: either extend the previous one or start fresh.
function maxSubArray(nums) { let best = nums[0], cur = nums[0]; for (let i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]); best = Math.max(best, cur); } return best;}To also return the indices, record start when cur resets and end when best updates.
2. Prefix sum + running minimum
Time O(n)Space O(1)
max subarray ending at i = prefix[i] − min(prefix[0..i−1]). Same complexity, useful when you already have prefix sums.
function maxSubArray(nums) { let prefix = 0, minPrefix = 0, best = -Infinity; for (const x of nums) { prefix += x; best = Math.max(best, prefix - minPrefix); minPrefix = Math.min(minPrefix, prefix); } return best;}3. Divide and conquer
Time O(n log n)Space O(log n)
Best subarray is entirely left, entirely right, or crosses the midpoint. Asked to test recursion/merge thinking.
function maxSubArray(nums, lo = 0, hi = nums.length - 1) { if (lo === hi) return nums[lo]; const mid = (lo + hi) >> 1; let leftBest = -Infinity, sum = 0; for (let i = mid; i >= lo; i--) { sum += nums[i]; leftBest = Math.max(leftBest, sum); } let rightBest = -Infinity; sum = 0; for (let i = mid + 1; i <= hi; i++) { sum += nums[i]; rightBest = Math.max(rightBest, sum); } return Math.max( maxSubArray(nums, lo, mid), maxSubArray(nums, mid + 1, hi), leftBest + rightBest, );}Best time to buy and Sell stockEasy2 approaches
Problem
prices[i] is a stock's price on day i. You may buy once and sell once, on a later day. Return the maximum profit you can make, or 0 if no profit is possible.
Example 1
Input: [7, 1, 5, 3, 6, 4] Output: 5
Buy on day 1 (price 1), sell on day 4 (price 6).
Example 2
Input: [7, 6, 4, 3, 1] Output: 0
Prices only fall, so do not trade.
1. One pass (track min price)
Time O(n)Space O(1)
Keep the lowest price seen so far; the best profit is the largest (price − minSoFar).
function maxProfit(prices) { let minPrice = Infinity, profit = 0; for (const p of prices) { minPrice = Math.min(minPrice, p); profit = Math.max(profit, p - minPrice); } return profit;}2. Brute force
Time O(n²)Space O(1)
Try every buy/sell pair. Only useful as the baseline you state before optimising.
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length; i++) for (let j = i + 1; j < prices.length; j++) profit = Math.max(profit, prices[j] - prices[i]); return profit;}find duplicate in an array of N+1 IntegersMedium3 approaches
Problem
An array has n + 1 integers, each in the range 1..n, so at least one value repeats. Exactly one value is repeated (possibly several times). Return it without modifying the array, using O(1) extra space.
Example 1
Input: [1, 3, 4, 2, 2] Output: 2
Example 2
Input: [3, 1, 3, 4, 2] Output: 3
Also asked as: find the duplicate number
1. Floyd's cycle detection
Time O(n)Space O(1)
Treat values as next-pointers. A duplicate creates a cycle; the entry to the cycle is the duplicate. No mutation, O(1) space.
function findDuplicate(nums) { let slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast); slow = nums[0]; while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; } return slow;}2. Marking with sign / index
Time O(n)Space O(1)
Walk the array; negate nums[|x|]. If already negative, |x| is the duplicate. Mutates the input.
function findDuplicate(nums) { for (const n of nums) { const i = Math.abs(n); if (nums[i] < 0) return i; nums[i] = -nums[i]; }}3. Hash set
Time O(n)Space O(n)
First value already in the set is the answer. Simplest; O(n) extra space.
function findDuplicate(nums) { const seen = new Set(); for (const n of nums) { if (seen.has(n)) return n; seen.add(n); }}Merge IntervalsMedium1 approach
Problem
Given a list of intervals [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals, sorted by start. Intervals that touch (one ends where the next starts) count as overlapping.
Example 1
Input: [[1,3], [2,6], [8,10], [15,18]] Output: [[1,6], [8,10], [15,18]]
[1,3] and [2,6] overlap, so they merge into [1,6].
Example 2
Input: [[1,4], [4,5]] Output: [[1,5]]
Also asked as: Merge Overlapping Intervals
1. Sort by start, then sweep
Time O(n log n)Space O(n)
After sorting, an interval either extends the last merged one (overlap) or starts a new one.
function merge(intervals) { intervals.sort((a, b) => a[0] - b[0]); const res = [intervals[0]]; for (let i = 1; i < intervals.length; i++) { const last = res[res.length - 1]; if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]); else res.push(intervals[i]); } return res;}Trapping Rain water problemHard3 approaches
Problem
height[i] is the height of a bar of width 1. After it rains, water collects between taller bars. Return the total units of water trapped.
Example 1
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Water above each bar = min(tallest bar to its left, tallest to its right) − its own height, if positive.
1. Prefix max arrays
Time O(n)Space O(n)
Water above bar i = min(maxLeft[i], maxRight[i]) − height[i]. Precompute both in two passes.
function trap(h) { const n = h.length; const left = Array(n), right = Array(n); left[0] = h[0]; for (let i = 1; i < n; i++) left[i] = Math.max(left[i - 1], h[i]); right[n - 1] = h[n - 1]; for (let i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], h[i]); let water = 0; for (let i = 0; i < n; i++) water += Math.min(left[i], right[i]) - h[i]; return water;}2. Two pointers
Time O(n)Space O(1)
Move the side with the smaller running max inward; that side bounds the water. Drops space to O(1).
function trap(h) { let l = 0, r = h.length - 1, lMax = 0, rMax = 0, water = 0; while (l < r) { if (h[l] < h[r]) { lMax = Math.max(lMax, h[l]); water += lMax - h[l++]; } else { rMax = Math.max(rMax, h[r]); water += rMax - h[r--]; } } return water;}3. Monotonic stack
Time O(n)Space O(n)
Keep a decreasing stack of indices; when a taller bar arrives, pop and add the water trapped in the "valley".
function trap(h) { const st = []; let water = 0; for (let i = 0; i < h.length; i++) { while (st.length && h[i] > h[st[st.length - 1]]) { const bottom = st.pop(); if (!st.length) break; const width = i - st[st.length - 1] - 1; const bounded = Math.min(h[i], h[st[st.length - 1]]) - h[bottom]; water += width * bounded; } st.push(i); } return water;}find all pairs on integer array whose sum is equal to given numberEasy2 approaches
Problem
Given an array of integers and a target sum k, count (or list) all pairs of indices i < j with arr[i] + arr[j] = k. Equal values at different indices form separate pairs.
Example 1
Input: arr = [1, 5, 7, 1], k = 6 Output: 2
Pairs (1,5) at indices (0,1) and (5,1) at indices (1,3).
Example 2
Input: arr = [1, 1, 1, 1], k = 2 Output: 6
Also asked as: two sum · pair with given sum
1. Hash set (unsorted)
Time O(n)Space O(n)
For each x check if (target − x) was already seen.
function pairs(a, target) { const seen = new Set(), out = []; for (const x of a) { if (seen.has(target - x)) out.push([target - x, x]); seen.add(x); } return out;}2. Sort + two pointers
Time O(n log n)Space O(1)
Sort, then shrink from both ends. O(1) extra space; also lists pairs in order.
function pairs(a, target) { a.sort((x, y) => x - y); let l = 0, r = a.length - 1; const out = []; while (l < r) { const s = a[l] + a[r]; if (s === target) { out.push([a[l], a[r]]); l++; r--; } else if (s < target) l++; else r--; } return out;}find maximum product subarrayMedium1 approach
Problem
Given an integer array that may contain negatives and zeros, find the contiguous subarray with the largest product and return that product.
Example 1
Input: [2, 3, -2, 4] Output: 6
[2, 3] gives 6. Including -2 makes the product negative.
Example 2
Input: [-2, 3, -4] Output: 24
Two negatives multiply to a positive: the whole array.
1. Track running max and min
Time O(n)Space O(1)
A negative number swaps max and min, so carry both. Best answer is the running max.
function maxProduct(nums) { let maxP = nums[0], minP = nums[0], res = nums[0]; for (let i = 1; i < nums.length; i++) { const x = nums[i]; if (x < 0) [maxP, minP] = [minP, maxP]; maxP = Math.max(x, maxP * x); minP = Math.min(x, minP * x); res = Math.max(res, maxP); } return res;}Find the maximum and minimum element in an arrayEasy2 approaches
Problem
Given an array of integers, return its minimum and maximum values. The follow-up asks you to use as few comparisons as possible.
Example 1
Input: [3, 5, 4, 1, 9] Output: min = 1, max = 9
Also asked as: Maximum and minimum of an array using minimum number of comparisons
1. Single pass
Time O(n)Space O(1)
Track the running min and max in one sweep.
function minMax(a) { let mn = a[0], mx = a[0]; for (const x of a) { if (x < mn) mn = x; if (x > mx) mx = x; } return { min: mn, max: mx };}2. Pairwise comparison (fewer comparisons)
Time O(n)Space O(1)
Compare elements in pairs first, then each to min/max — ~3n/2 comparisons instead of 2n.
function minMax(a) { let i = 0, mn, mx; if (a.length % 2) { mn = mx = a[0]; i = 1; } else { [mn, mx] = a[0] < a[1] ? [a[0], a[1]] : [a[1], a[0]]; i = 2; } for (; i < a.length; i += 2) { const [lo, hi] = a[i] < a[i + 1] ? [a[i], a[i + 1]] : [a[i + 1], a[i]]; if (lo < mn) mn = lo; if (hi > mx) mx = hi; } return { min: mn, max: mx };}Sort an array of 0s, 1s and 2sMedium2 approaches
Problem
The array contains only 0, 1 and 2. Sort it in place in a single pass, without a library sort and without counting then rewriting (the Dutch National Flag problem).
Example 1
Input: [0, 2, 1, 2, 0] Output: [0, 0, 1, 2, 2]
Also asked as: Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo
1. Dutch National Flag (one pass)
Time O(n)Space O(1)
Three pointers: everything before `low` is 0, after `high` is 2, `mid` scans the unknown middle.
function sort012(a) { let low = 0, mid = 0, high = a.length - 1; while (mid <= high) { if (a[mid] === 0) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; } else if (a[mid] === 1) mid++; else { [a[mid], a[high]] = [a[high], a[mid]]; high--; } } return a;}2. Counting sort
Time O(n)Space O(1)
Count 0s/1s/2s, then overwrite. Two passes, trivial to reason about.
function sort012(a) { const c = [0, 0, 0]; for (const x of a) c[x]++; let i = 0; for (let v = 0; v < 3; v++) while (c[v]-- > 0) a[i++] = v; return a;}Move all negative elements to one sideEasy1 approach
Problem
Rearrange the array so that all negative numbers come before all non-negative numbers. The relative order within each group does not need to be preserved. Use O(1) extra space.
Example 1
Input: [-12, 11, -13, -5, 6, -7, 5, -3, -6] Output: [-12, -13, -5, -7, -3, -6, 11, 6, 5]
Any order is fine as long as every negative comes first.
Also asked as: Move all the negative elements to one side of the array
1. Two pointers (order not preserved)
Time O(n)Space O(1)
Partition like quicksort: `j` tracks the boundary; swap each negative to the front.
function moveNegatives(a) { let j = 0; for (let i = 0; i < a.length; i++) { if (a[i] < 0) { [a[i], a[j]] = [a[j], a[i]]; j++; } } return a;}Preserving relative order in O(1) space needs the rotation trick and is O(n²); with O(n) space it is a stable two-bucket pass.
Union and Intersection of two sorted arraysEasy1 approach
Problem
Given two sorted arrays, return their union (every distinct value in either array) and their intersection (every distinct value in both), each in sorted order.
Example 1
Input: a = [1, 3, 4, 5, 7], b = [2, 3, 5, 6] Output: union = [1,2,3,4,5,6,7], intersection = [3, 5]
Also asked as: Find the Union and Intersection of the two sorted arrays
1. Merge-style two pointers
Time O(n + m)Space O(n + m) output
Advance the pointer at the smaller value; equal values go to the intersection (and once to the union).
function unionIntersection(a, b) { let i = 0, j = 0; const uni = [], inter = []; const pushUni = (x) => { if (uni[uni.length - 1] !== x) uni.push(x); }; while (i < a.length && j < b.length) { if (a[i] < b[j]) pushUni(a[i++]); else if (a[i] > b[j]) pushUni(b[j++]); else { pushUni(a[i]); inter.push(a[i]); i++; j++; } } while (i < a.length) pushUni(a[i++]); while (j < b.length) pushUni(b[j++]); return { union: uni, intersection: inter };}Cyclically rotate an arrayEasy2 approaches
Problem
Rotate the array to the right by one position: the last element moves to the front and every other element shifts one place right. The follow-up asks you to rotate by k positions in O(n) time and O(1) space.
Example 1
Input: [1, 2, 3, 4, 5] Output: [5, 1, 2, 3, 4]
Example 2
Input: [1, 2, 3, 4, 5], k = 2 Output: [4, 5, 1, 2, 3]
Also asked as: Write a program to cyclically rotate an array by one
1. Rotate by one (shift)
Time O(n)Space O(1)
Save the last element, shift everyone right by one, put it in front.
function rotateByOne(a) { const last = a[a.length - 1]; for (let i = a.length - 1; i > 0; i--) a[i] = a[i - 1]; a[0] = last; return a;}2. Rotate by k — reversal algorithm
Time O(n)Space O(1)
Reverse the whole array, then reverse the first k and the rest.
function rotate(a, k) { k %= a.length; const rev = (l, r) => { while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; } }; rev(0, a.length - 1); rev(0, k - 1); rev(k, a.length - 1); return a;}Minimise the maximum difference between heightsMedium1 approach
Problem
You are given tower heights and an integer k. You must change every tower exactly once, either adding k or subtracting k. Heights must not become negative. Return the smallest possible difference between the tallest and the shortest tower afterwards.
Example 1
Input: heights = [1, 5, 8, 10], k = 2 Output: 5
Becomes [3, 3, 6, 8]: 8 − 3 = 5.
Also asked as: Minimise the maximum difference between heights
1. Sort, then try every split point
Time O(n log n)Space O(1)
Sorted, add k to a prefix and subtract k from the suffix. For each split, the new range is max(a[i-1]+k, a[n-1]-k) − min(a[0]+k, a[i]-k).
function getMinDiff(a, k) { a.sort((x, y) => x - y); const n = a.length; let ans = a[n - 1] - a[0]; for (let i = 1; i < n; i++) { if (a[i] - k < 0) continue; const high = Math.max(a[i - 1] + k, a[n - 1] - k); const low = Math.min(a[0] + k, a[i] - k); ans = Math.min(ans, high - low); } return ans;}Minimum number of jumps to reach the endMedium1 approach
Problem
You start at index 0. arr[i] is the maximum number of steps you can jump forward from index i. Return the minimum number of jumps needed to reach the last index, or −1 if it cannot be reached.
Example 1
Input: [2, 3, 1, 1, 4] Output: 2
Jump 0 → 1 (1 step), then 1 → 4 (3 steps).
Example 2
Input: [1, 0, 3] Output: -1
Index 1 has value 0, so you are stuck.
Also asked as: Minimum no. of Jumps to reach end of an array · Minimum number of jumps to reach end
1. Greedy (BFS levels)
Time O(n)Space O(1)
Each "jump" covers a range; extend `farthest` while scanning it, and when you reach the current range end, take a jump.
function minJumps(a) { let jumps = 0, curEnd = 0, farthest = 0; for (let i = 0; i < a.length - 1; i++) { farthest = Math.max(farthest, i + a[i]); if (i === curEnd) { if (farthest <= i) return -1; // stuck jumps++; curEnd = farthest; } } return jumps;}Merge two sorted arrays without extra spaceHard1 approach
Problem
Two sorted arrays a (size n) and b (size m) are given. Rearrange their elements in place so that a holds the n smallest values and b holds the rest, both still sorted. Use O(1) extra space.
Example 1
Input: a = [1, 4, 7, 8, 10], b = [2, 3, 9] Output: a = [1, 2, 3, 4, 7], b = [8, 9, 10]
Also asked as: Merge 2 sorted arrays without using Extra space
1. Gap method (Shell-sort style)
Time O((n+m) log(n+m))Space O(1)
Start with gap = ceil((n+m)/2); compare and swap elements `gap` apart across both arrays; halve the gap until 1.
function mergeInPlace(a, b) { const n = a.length, m = b.length, total = n + m; const at = (i) => (i < n ? a[i] : b[i - n]); const set = (i, v) => { if (i < n) a[i] = v; else b[i - n] = v; }; let gap = Math.ceil(total / 2); while (gap > 0) { for (let i = 0; i + gap < total; i++) { if (at(i) > at(i + gap)) { const t = at(i); set(i, at(i + gap)); set(i + gap, t); } } gap = gap === 1 ? 0 : Math.ceil(gap / 2); }}Next PermutationMedium1 approach
Problem
Rearrange the array into the next lexicographically larger permutation of its values. If it is already the largest permutation, rearrange it into the smallest (sorted ascending). Do it in place with O(1) extra space.
Example 1
Input: [1, 2, 3] Output: [1, 3, 2]
Example 2
Input: [3, 2, 1] Output: [1, 2, 3]
Already the largest, so wrap around to the smallest.
Example 3
Input: [1, 3, 2] Output: [2, 1, 3]
Also asked as: Next Permutation
1. Pivot, swap, reverse suffix
Time O(n)Space O(1)
Find the rightmost `i` with a[i] < a[i+1]. Swap a[i] with the rightmost element greater than it, then reverse the suffix after i.
function nextPermutation(a) { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i >= 0) { let j = a.length - 1; while (a[j] <= a[i]) j--; [a[i], a[j]] = [a[j], a[i]]; } // reverse suffix let l = i + 1, r = a.length - 1; while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; } return a;}Count InversionsMedium1 approach
Problem
An inversion is a pair of indices i < j with arr[i] > arr[j]. It measures how far the array is from sorted. Return the number of inversions.
Example 1
Input: [2, 4, 1, 3, 5] Output: 3
The inversions are (2,1), (4,1) and (4,3).
Also asked as: Count Inversion · Findthe inversion count
1. Merge sort
Time O(n log n)Space O(n)
While merging two sorted halves, every time an element from the right half is picked before elements remain in the left, those remaining left elements are all inversions.
function countInversions(a) { let count = 0; const sort = (arr) => { if (arr.length < 2) return arr; const mid = arr.length >> 1; const L = sort(arr.slice(0, mid)); const R = sort(arr.slice(mid)); const merged = []; let i = 0, j = 0; while (i < L.length && j < R.length) { if (L[i] <= R[j]) merged.push(L[i++]); else { merged.push(R[j++]); count += L.length - i; } } return merged.concat(L.slice(i), R.slice(j)); }; sort(a.slice()); return count;}Common elements in three sorted arraysEasy1 approach
Problem
Given three arrays sorted in ascending order, return the distinct values that appear in all three, in sorted order.
Example 1
Input: a = [1, 5, 10, 20, 40, 80], b = [6, 7, 20, 80, 100], c = [3, 4, 15, 20, 30, 70, 80, 120] Output: [20, 80]
Also asked as: find common elements In 3 sorted arrays
1. Three pointers
Time O(n1 + n2 + n3)Space O(1)
If all three current values are equal, record it; otherwise advance the pointer with the smallest value.
function commonElements(a, b, c) { let i = 0, j = 0, k = 0; const res = []; while (i < a.length && j < b.length && k < c.length) { if (a[i] === b[j] && b[j] === c[k]) { if (res[res.length - 1] !== a[i]) res.push(a[i]); i++; j++; k++; } else if (a[i] <= b[j] && a[i] <= c[k]) i++; else if (b[j] <= a[i] && b[j] <= c[k]) j++; else k++; } return res;}Rearrange array in alternating positive and negative itemsHard1 approach
Problem
Rearrange the array so positive and negative numbers alternate, keeping their original relative order within each sign. If one sign runs out, append the leftovers at the end. Treat 0 as positive. The hard version asks for O(1) extra space.
Example 1
Input: [1, 2, 3, -4, -1, 4] Output: [-4, 1, -1, 2, 3, 4]
Also asked as: Rearrange the array in alternating positive and negative items with O(1) extra space
1. In-place rotation (order preserved)
Time O(n²)Space O(1)
Scan for the first out-of-place pair; right-rotate the subarray from that index to the wrong element so it slots in. O(n²) worst but O(1) space and stable.
function rearrange(a) { const rotateRight = (arr, lo, hi) => { const t = arr[hi]; for (let k = hi; k > lo; k--) arr[k] = arr[k - 1]; arr[lo] = t; }; let outOfPlace = -1; for (let i = 0; i < a.length; i++) { if (outOfPlace >= 0) { const wrongSign = (a[i] >= 0 && a[outOfPlace] < 0) || (a[i] < 0 && a[outOfPlace] >= 0); if (wrongSign) { rotateRight(a, outOfPlace, i); outOfPlace = i - outOfPlace >= 2 ? outOfPlace + 2 : -1; } } if (outOfPlace === -1) { const misplaced = (a[i] >= 0 && i % 2 === 1) || (a[i] < 0 && i % 2 === 0); if (misplaced) outOfPlace = i; } } return a;}If order need not be preserved: two-pointer partition into negatives/positives, then swap alternate elements — O(n), O(1).
Subarray with sum equal to 0Easy1 approach
Problem
Given an array of integers (it may contain negatives), return true if some non-empty contiguous subarray sums to 0.
Example 1
Input: [4, 2, -3, 1, 6] Output: true
[2, -3, 1] sums to 0.
Example 2
Input: [4, 2, 0, 1, 6] Output: true
The single element [0].
Example 3
Input: [-3, 2, 3, 1, 6] Output: false
Also asked as: Find if there is any subarray with sum equal to 0
1. Prefix sums in a set
Time O(n)Space O(n)
If the running prefix sum repeats (or is 0), the elements in between sum to 0.
function hasZeroSumSubarray(a) { const seen = new Set([0]); let sum = 0; for (const x of a) { sum += x; if (seen.has(sum)) return true; seen.add(sum); } return false;}Factorial of a large numberEasy1 approach
Problem
Given n (up to about 1000), return n! as a string or digit array. The result has far more digits than any built-in number type can hold, so you must do the arithmetic digit by digit.
Example 1
Input: n = 5 Output: 120
Example 2
Input: n = 25 Output: 15511210043330985984000000
Also asked as: Find factorial of a large number
1. Digit array multiplication
Time O(n · digits)Space O(digits)
Store the result least-significant-digit first; multiply the whole array by each k from 2..n, propagating carry.
function factorial(n) { let digits = [1]; for (let k = 2; k <= n; k++) { let carry = 0; for (let i = 0; i < digits.length; i++) { const prod = digits[i] * k + carry; digits[i] = prod % 10; carry = Math.floor(prod / 10); } while (carry) { digits.push(carry % 10); carry = Math.floor(carry / 10); } } return digits.reverse().join('');}In modern JS you can also just use BigInt: let f = 1n; for (let i = 2n; i <= BigInt(n); i++) f *= i;
Longest consecutive subsequenceMedium1 approach
Problem
Given an unsorted array of integers, return the length of the longest run of consecutive values (x, x+1, x+2, …). The values can appear in any order in the array. Aim for O(n) time.
Example 1
Input: [100, 4, 200, 1, 3, 2] Output: 4
The run 1, 2, 3, 4.
Also asked as: Find longest coinsecutive subsequence
1. Hash set, count from sequence starts
Time O(n)Space O(n)
Put all values in a set. A value begins a run only if value−1 is absent; from there count upward.
function longestConsecutive(nums) { const set = new Set(nums); let best = 0; for (const n of set) { if (set.has(n - 1)) continue; let len = 1; while (set.has(n + len)) len++; best = Math.max(best, len); } return best;}Elements appearing more than n/k timesMedium1 approach
Problem
Given an array of size n and an integer k, return every element that appears more than n/k times. At most k − 1 elements can qualify.
Example 1
Input: arr = [3, 1, 2, 2, 1, 2, 3, 3], k = 4 Output: [2, 3]
n/k = 2. The values 2 and 3 each appear 3 times.
Also asked as: Given an array of size n and a number k, fin all elements that appear more than " n/k " times
1. Generalised Boyer–Moore (k−1 counters)
Time O(n · k)Space O(k)
At most k−1 elements can exceed n/k. Keep k−1 candidate/count slots; a final pass verifies the true counts.
function moreThanNK(a, k) { const cnt = new Map(); // up to k-1 entries for (const x of a) { if (cnt.has(x)) cnt.set(x, cnt.get(x) + 1); else if (cnt.size < k - 1) cnt.set(x, 1); else { for (const key of [...cnt.keys()]) { cnt.set(key, cnt.get(key) - 1); if (cnt.get(key) === 0) cnt.delete(key); } } } const res = []; for (const key of cnt.keys()) { if (a.filter((v) => v === key).length > a.length / k) res.push(key); } return res;}Check whether an array is a subset of another arrayEasy1 approach
Problem
Given arrays a1 and a2, return true if every element of a2 is present in a1. If a value repeats in a2, a1 must contain it at least as many times.
Example 1
Input: a1 = [11, 1, 13, 21, 3, 7], a2 = [11, 3, 7, 1] Output: true
Example 2
Input: a1 = [10, 5, 2, 23, 19], a2 = [19, 5, 3] Output: false
3 is missing from a1.
Also asked as: Find whether an array is a subset of another array
1. Hash set
Time O(n + m)Space O(n)
Put the bigger array in a set; every element of the smaller must be present.
function isSubset(big, small) { const set = new Set(big); return small.every((x) => set.has(x));}Find a triplet that sums to a given valueMedium1 approach
Problem
Given an array and a target x, return true if some three distinct indices hold values that sum to exactly x (or return the triplet).
Example 1
Input: arr = [1, 4, 45, 6, 10, 8], x = 13 Output: true
1 + 4 + 8 = 13.
Also asked as: Find the triplet that sum to a given value · 3 sum
1. Sort + fix one + two pointers
Time O(n²)Space O(1)
Sort. Fix index i, then two-pointer the rest for (target − a[i]).
function findTriplet(a, target) { a.sort((x, y) => x - y); for (let i = 0; i < a.length - 2; i++) { let l = i + 1, r = a.length - 1; while (l < r) { const s = a[i] + a[l] + a[r]; if (s === target) return [a[i], a[l], a[r]]; s < target ? l++ : r--; } } return null;}Chocolate Distribution ProblemEasy1 approach
Problem
arr[i] is the number of chocolates in packet i. Give one packet to each of m students so that the difference between the largest and smallest packet handed out is as small as possible. Return that minimum difference.
Example 1
Input: arr = [7, 3, 2, 4, 9, 12, 56], m = 3 Output: 2
Choose packets 2, 3 and 4: 4 − 2 = 2.
Also asked as: Chocolate Distribution problem
1. Sort + sliding window of size m
Time O(n log n)Space O(1)
After sorting, the fairest set of m packets is a contiguous window; minimise (window max − window min).
function minDiff(a, m) { a.sort((x, y) => x - y); let best = Infinity; for (let i = 0; i + m - 1 < a.length; i++) { best = Math.min(best, a[i + m - 1] - a[i]); } return best;}Smallest subarray with sum greater than a given valueMedium1 approach
Problem
Given an array of positive integers and a value x, return the length of the smallest contiguous subarray whose sum is strictly greater than x, or 0 if none exists.
Example 1
Input: arr = [1, 4, 45, 6, 0, 19], x = 51 Output: 3
[4, 45, 6] sums to 55.
Also asked as: Smallest Subarray with sum greater than a given value
1. Sliding window (positive numbers)
Time O(n)Space O(1)
Grow the window on the right; whenever the sum exceeds x, shrink from the left while it still does, recording the length.
function smallestSubWithSum(a, x) { let sum = 0, start = 0, best = Infinity; for (let end = 0; end < a.length; end++) { sum += a[end]; while (sum > x) { best = Math.min(best, end - start + 1); sum -= a[start++]; } } return best === Infinity ? 0 : best;}Three-way partitioning around a rangeMedium1 approach
Problem
Given an array and a range [low, high], rearrange the array in place into three groups: elements smaller than low first, then elements within [low, high], then elements greater than high. Order inside each group does not matter. Use a single pass.
Example 1
Input: arr = [1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], low = 14, high = 20 Output: [1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54]
Also asked as: Three way partitioning of an array around a given value
1. Dutch-flag variant
Time O(n)Space O(1)
Elements < lowVal go left of `low`, elements > highVal go right of `high`, the rest stay in the middle.
function threeWayPartition(a, lowVal, highVal) { let low = 0, mid = 0, high = a.length - 1; while (mid <= high) { if (a[mid] < lowVal) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; } else if (a[mid] > highVal) { [a[mid], a[high]] = [a[high], a[mid]]; high--; } else mid++; } return a;}Minimum swaps to bring elements ≤ K togetherMedium1 approach
Problem
Given an array and a number k, return the minimum number of swaps needed to bring all elements less than or equal to k next to each other. They can end up anywhere in the array, as long as they are contiguous.
Example 1
Input: arr = [2, 1, 5, 6, 3], k = 3 Output: 1
Swap 5 and 3 to get [2, 1, 3, 6, 5].
Also asked as: Minimum swaps required bring elements less equal K together
1. Sliding window of "good" count
Time O(n)Space O(1)
Let `good` = count of elements ≤ K. Slide a window of size `good`; the answer is the minimum number of elements > K inside any such window.
function minSwaps(a, k) { const good = a.filter((x) => x <= k).length; let bad = 0; for (let i = 0; i < good; i++) if (a[i] > k) bad++; let best = bad; for (let i = good; i < a.length; i++) { if (a[i] > k) bad++; if (a[i - good] > k) bad--; best = Math.min(best, bad); } return best;}Minimum operations to make an array palindromeMedium1 approach
Problem
In one operation you may replace two adjacent elements with their sum. Return the minimum number of operations needed to turn the array into a palindrome.
Example 1
Input: [15, 4, 15] Output: 0
Example 2
Input: [1, 4, 5, 1] Output: 1
Merge 4 and 5 into 9: [1, 9, 1].
Also asked as: Minimum no. of operations required to make an array palindrome
1. Two pointers, merge the smaller side
Time O(n)Space O(1)
Compare ends. If equal, move both in. If left < right, merge a[l] into a[l+1] (one op). If left > right, merge a[r] into a[r−1].
function minOpsPalindrome(a) { let l = 0, r = a.length - 1, ops = 0; while (l < r) { if (a[l] === a[r]) { l++; r--; } else if (a[l] < a[r]) { a[l + 1] += a[l]; l++; ops++; } else { a[r - 1] += a[r]; r--; ops++; } } return ops;}Median of two sorted arraysHard1 approach
Problem
Given two sorted arrays of sizes m and n, return the median of all m + n values combined. With an even total, the median is the average of the two middle values. The target is O(log(min(m, n))) time.
Example 1
Input: a = [1, 3], b = [2] Output: 2
Example 2
Input: a = [1, 2], b = [3, 4] Output: 2.5
Merged [1, 2, 3, 4]: (2 + 3) / 2.
Also asked as: Median of 2 sorted arrays of equal size · Median of 2 sorted arrays of different size
1. Binary search on the partition of the smaller array
Time O(log min(n, m))Space O(1)
Choose how many of the first array go in the left half; derive the count from the second. Slide until maxLeft ≤ minRight on both sides.
function findMedianSortedArrays(a, b) { if (a.length > b.length) [a, b] = [b, a]; const n = a.length, m = b.length, half = (n + m + 1) >> 1; let lo = 0, hi = n; while (lo <= hi) { const i = (lo + hi) >> 1; // from a const j = half - i; // from b const aLeft = i > 0 ? a[i - 1] : -Infinity; const aRight = i < n ? a[i] : Infinity; const bLeft = j > 0 ? b[j - 1] : -Infinity; const bRight = j < m ? b[j] : Infinity; if (aLeft <= bRight && bLeft <= aRight) { if ((n + m) % 2) return Math.max(aLeft, bLeft); return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2; } if (aLeft > bRight) hi = i - 1; else lo = i + 1; } throw new Error('inputs not sorted');}Contains DuplicateEasy2 approaches
Problem
Return true if any value appears at least twice in the array, and false if every element is distinct.
Example 1
Input: [1, 2, 3, 1] Output: true
Example 2
Input: [1, 2, 3, 4] Output: false
1. Sort, compare neighbours
Time O(n log n)Space O(1) extra (mutates input)
After sorting, duplicates sit next to each other.
function containsDuplicate(nums) { nums.sort((a, b) => a - b); for (let i = 1; i < nums.length; i++) if (nums[i] === nums[i - 1]) return true; return false;}2. Hash set
Time O(n)Space O(n)
Return true the first time a value is already in the set.
function containsDuplicate(nums) { const seen = new Set(); for (const x of nums) { if (seen.has(x)) return true; seen.add(x); } return false;}One-liner: new Set(nums).size !== nums.length — but it cannot exit early.
Range Sum Query – ImmutableEasy1 approach
Problem
Given an array that never changes, answer many queries sumRange(l, r) — the sum of elements from index l to r inclusive — each in O(1).
Example 1
Input: nums = [-2, 0, 3, -5, 2, -1]; sumRange(0,2), sumRange(2,5), sumRange(0,5) Output: 1, -1, -3
1. Prefix sums
Time O(n) build, O(1) per querySpace O(n)
pre[i] = sum of the first i numbers; sum(l..r) = pre[r+1] − pre[l]. The leading zero removes the l = 0 special case.
class NumArray { constructor(nums) { this.pre = [0]; for (const x of nums) this.pre.push(this.pre[this.pre.length - 1] + x); } sumRange(l, r) { return this.pre[r + 1] - this.pre[l]; }}Subarray Sum Equals KMedium2 approaches
Problem
Return the number of contiguous subarrays whose sum equals k. The array can contain negative numbers.
Example 1
Input: nums = [1, 1, 1], k = 2 Output: 2
Example 2
Input: nums = [1, 2, 3], k = 3 Output: 2
[1, 2] and [3].
1. All start points
Time O(n²)Space O(1)
Fix a start, extend the end while keeping a running sum.
function subarraySum(nums, k) { let res = 0; for (let i = 0; i < nums.length; i++) { let sum = 0; for (let j = i; j < nums.length; j++) if ((sum += nums[j]) === k) res++; } return res;}2. Prefix sum counts in a map
Time O(n)Space O(n)
A subarray ending here sums to k when some earlier prefix equals sum − k. Count how many earlier prefixes had each value.
function subarraySum(nums, k) { const count = new Map([[0, 1]]); let sum = 0, res = 0; for (const x of nums) { sum += x; res += count.get(sum - k) ?? 0; count.set(sum, (count.get(sum) ?? 0) + 1); } return res;}Sliding window fails here because numbers can be negative — interviewers often ask why.
Continuous Subarray SumMedium1 approach
Problem
Return true if the array has a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple).
Example 1
Input: nums = [23, 2, 4, 6, 7], k = 6 Output: true
[2, 4] sums to 6.
Example 2
Input: nums = [23, 2, 6, 4, 7], k = 13 Output: false
1. Prefix remainders
Time O(n)Space O(min(n, k))
Two prefixes with the same remainder mod k bound a subarray whose sum is a multiple of k. Store the first index of each remainder; require length ≥ 2.
function checkSubarraySum(nums, k) { const first = new Map([[0, -1]]); // remainder -> earliest index let sum = 0; for (let i = 0; i < nums.length; i++) { sum = (sum + nums[i]) % k; if (first.has(sum)) { if (i - first.get(sum) >= 2) return true; } else first.set(sum, i); } return false;}Contiguous Array (equal 0s and 1s)Medium1 approach
Problem
Given a binary array, return the length of the longest contiguous subarray with an equal number of 0s and 1s.
Example 1
Input: [0, 1, 0] Output: 2
Example 2
Input: [0, 0, 1, 0, 0, 0, 1, 1] Output: 6
1. Treat 0 as −1, earliest prefix index
Time O(n)Space O(n)
With 0 → −1, equal counts mean a zero-sum subarray: the same running sum seen twice. Keep the earliest index for each sum to maximise length.
function findMaxLength(nums) { const first = new Map([[0, -1]]); let sum = 0, best = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i] === 1 ? 1 : -1; if (first.has(sum)) best = Math.max(best, i - first.get(sum)); else first.set(sum, i); } return best;}Subarray Sums Divisible by KMedium1 approach
Problem
Return the number of non-empty contiguous subarrays whose sum is divisible by k. Values can be negative.
Example 1
Input: nums = [4, 5, 0, -2, -3, 1], k = 5 Output: 7
1. Count prefix remainders
Time O(n)Space O(k)
Every pair of equal prefix remainders is one valid subarray. Normalise negative remainders with ((x % k) + k) % k.
function subarraysDivByK(nums, k) { const cnt = new Array(k).fill(0); cnt[0] = 1; let sum = 0, res = 0; for (const x of nums) { sum = (((sum + x) % k) + k) % k; res += cnt[sum]++; } return res;}Two Sum II – Input Array Is SortedMedium1 approach
Problem
The array is sorted in ascending order. Return the 1-based indices of the two numbers that add up to target (exactly one solution exists), using O(1) extra space.
Example 1
Input: numbers = [2, 7, 11, 15], target = 9 Output: [1, 2]
1. Two pointers from both ends
Time O(n)Space O(1)
Sum too small → move left up; too big → move right down. Sorting guarantees nothing is skipped. Answer is 1-indexed.
function twoSum(numbers, target) { let l = 0, r = numbers.length - 1; while (l < r) { const s = numbers[l] + numbers[r]; if (s === target) return [l + 1, r + 1]; s < target ? l++ : r--; } return [];}Container With Most WaterMedium2 approaches
Problem
height[i] is a vertical line at position i. Choose two lines that, together with the x-axis, hold the most water. The water level is set by the shorter line. Return the maximum amount.
Example 1
Input: [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49
Lines at indices 1 and 8: min(8, 7) × 7.
1. Every pair
Time O(n²)Space O(1)
Area = width × shorter height, for all pairs.
function maxArea(h) { let best = 0; for (let i = 0; i < h.length; i++) for (let j = i + 1; j < h.length; j++) best = Math.max(best, (j - i) * Math.min(h[i], h[j])); return best;}2. Two pointers, move the shorter side
Time O(n)Space O(1)
Moving the taller line can only shrink width without raising the limiting height, so always move the shorter one.
function maxArea(h) { let l = 0, r = h.length - 1, best = 0; while (l < r) { best = Math.max(best, (r - l) * Math.min(h[l], h[r])); h[l] < h[r] ? l++ : r--; } return best;}Remove Duplicates from Sorted ArrayEasy1 approach
Problem
Remove duplicates from a sorted array in place so that each value appears once, keeping the order. Return k, the number of unique values. The first k slots must hold them; what comes after does not matter.
Example 1
Input: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] Output: k = 5, array starts [0, 1, 2, 3, 4, …]
1. Slow write pointer
Time O(n)Space O(1)
k marks the end of the unique prefix; copy a value forward only when it differs from the last kept value.
function removeDuplicates(nums) { let k = 0; for (const x of nums) if (k === 0 || x !== nums[k - 1]) nums[k++] = x; return k;}Variant "allow at most two": compare with nums[k - 2] instead.
Move ZeroesEasy1 approach
Problem
Move every 0 to the end of the array in place, keeping the relative order of the non-zero elements.
Example 1
Input: [0, 1, 0, 3, 12] Output: [1, 3, 12, 0, 0]
1. Swap non-zeros forward
Time O(n)Space O(1)
Keep a write pointer for the next non-zero slot; swapping preserves the order of non-zeros and pushes zeros back.
function moveZeroes(nums) { let k = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] !== 0) { [nums[k], nums[i]] = [nums[i], nums[k]]; k++; } }}Missing NumberEasy2 approaches
Problem
The array holds n distinct numbers from the range 0..n, so exactly one is missing. Return it, in O(n) time and O(1) space.
Example 1
Input: [3, 0, 1] Output: 2
Example 2
Input: [9, 6, 4, 2, 3, 5, 7, 0, 1] Output: 8
1. Sum formula
Time O(n)Space O(1)
Expected sum of 0..n minus the actual sum.
function missingNumber(nums) { const n = nums.length; return (n * (n + 1)) / 2 - nums.reduce((a, b) => a + b, 0);}2. XOR
Time O(n)Space O(1)
XOR every index and every value; pairs cancel, the missing number remains. No overflow risk.
function missingNumber(nums) { let x = nums.length; for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]; return x;}Find All Numbers Disappeared in an ArrayEasy1 approach
Problem
An array of n integers has every value in 1..n, but some values repeat, so others are missing. Return every value in 1..n that does not appear, using O(1) extra space besides the output.
Example 1
Input: [4, 3, 2, 7, 8, 2, 3, 1] Output: [5, 6]
1. Mark by negating
Time O(n)Space O(1) extra
For each value v, negate nums[v − 1]. Indices still positive at the end were never visited.
function findDisappearedNumbers(nums) { for (const x of nums) { const i = Math.abs(x) - 1; if (nums[i] > 0) nums[i] = -nums[i]; } const res = []; for (let i = 0; i < nums.length; i++) if (nums[i] > 0) res.push(i + 1); return res;}Find All Duplicates in an ArrayMedium1 approach
Problem
An array of n integers has every value in 1..n, and each value appears once or twice. Return every value that appears twice, in O(n) time and O(1) extra space.
Example 1
Input: [4, 3, 2, 7, 8, 2, 3, 1] Output: [2, 3]
1. Mark by negating
Time O(n)Space O(1) extra
Visiting v flips nums[v − 1] negative; if it is already negative, v has been seen before.
function findDuplicates(nums) { const res = []; for (const x of nums) { const i = Math.abs(x) - 1; if (nums[i] < 0) res.push(i + 1); else nums[i] = -nums[i]; } return res;}First Missing PositiveHard2 approaches
Problem
Given an unsorted integer array, return the smallest positive integer that does not appear in it. It must run in O(n) time and O(1) extra space.
Example 1
Input: [1, 2, 0] Output: 3
Example 2
Input: [3, 4, -1, 1] Output: 2
Example 3
Input: [7, 8, 9, 11, 12] Output: 1
1. Hash set
Time O(n)Space O(n)
Put everything in a set, then test 1, 2, 3… — simple but O(n) space.
function firstMissingPositive(nums) { const s = new Set(nums); let i = 1; while (s.has(i)) i++; return i;}2. Cyclic sort
Time O(n) — each swap fixes one valueSpace O(1)
The answer is in 1..n+1. Swap each value v in range into index v − 1; the first index i with nums[i] ≠ i + 1 gives the answer.
function firstMissingPositive(nums) { const n = nums.length; for (let i = 0; i < n; i++) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) { const j = nums[i] - 1; [nums[i], nums[j]] = [nums[j], nums[i]]; } } for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1; return n + 1;}Max Consecutive Ones IIIMedium1 approach
Problem
Given a binary array and k, return the length of the longest run of 1s you can get by flipping at most k 0s.
Example 1
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6
1. Window with at most k zeros
Time O(n)Space O(1)
Expand right counting zeros; shrink left while more than k zeros are inside.
function longestOnes(nums, k) { let l = 0, zeros = 0, best = 0; for (let r = 0; r < nums.length; r++) { if (nums[r] === 0) zeros++; while (zeros > k) if (nums[l++] === 0) zeros--; best = Math.max(best, r - l + 1); } return best;}Fruit Into Baskets (at most k distinct)Medium1 approach
Problem
fruits[i] is the type of the ith tree in a row. You have two baskets, each holding one type (the general version allows k types). Start anywhere and pick one fruit from each tree moving right, stopping when a fruit fits no basket. Return the most fruit you can pick — the longest subarray with at most 2 distinct values.
Example 1
Input: [1, 2, 1] Output: 3
Example 2
Input: [1, 2, 3, 2, 2] Output: 4
[2, 3, 2, 2].
1. Window with a count map
Time O(n)Space O(k)
Longest subarray with at most 2 (generally k) distinct values: shrink while the map has more than k keys.
function totalFruit(fruits, k = 2) { const cnt = new Map(); let l = 0, best = 0; for (let r = 0; r < fruits.length; r++) { cnt.set(fruits[r], (cnt.get(fruits[r]) ?? 0) + 1); while (cnt.size > k) { const f = fruits[l++]; cnt.set(f, cnt.get(f) - 1); if (cnt.get(f) === 0) cnt.delete(f); } best = Math.max(best, r - l + 1); } return best;}Insert IntervalMedium1 approach
Problem
Given non-overlapping intervals sorted by start and a new interval, insert the new interval and merge wherever needed, so that the result is still sorted and non-overlapping.
Example 1
Input: intervals = [[1,3], [6,9]], new = [2,5] Output: [[1,5], [6,9]]
Example 2
Input: [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8] Output: [[1,2], [3,10], [12,16]]
1. Three phases in one pass
Time O(n)Space O(n)
Input is sorted and non-overlapping. Copy intervals ending before the new one, merge every interval that overlaps it, then copy the rest.
function insert(intervals, [s, e]) { const res = []; let i = 0; while (i < intervals.length && intervals[i][1] < s) res.push(intervals[i++]); while (i < intervals.length && intervals[i][0] <= e) { s = Math.min(s, intervals[i][0]); e = Math.max(e, intervals[i][1]); i++; } res.push([s, e]); while (i < intervals.length) res.push(intervals[i++]); return res;}Meeting RoomsEasy1 approach
Problem
Given meeting time intervals, return true if one person can attend all of them — that is, no two meetings overlap.
Example 1
Input: [[0,30], [5,10], [15,20]] Output: false
Example 2
Input: [[7,10], [2,4]] Output: true
1. Sort by start, check neighbours
Time O(n log n)Space O(1) extra
After sorting, a person can attend all meetings only if each starts no earlier than the previous one ends.
function canAttendMeetings(intervals) { intervals.sort((a, b) => a[0] - b[0]); for (let i = 1; i < intervals.length; i++) if (intervals[i][0] < intervals[i - 1][1]) return false; return true;}Meeting Rooms IIMedium1 approach
Problem
Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. A meeting ending at t frees its room for one starting at t.
Example 1
Input: [[0,30], [5,10], [15,20]] Output: 2
Example 2
Input: [[7,10], [2,4]] Output: 1
1. Sorted starts and ends (sweep)
Time O(n log n)Space O(n)
Walk starts in order. If a meeting has ended by this start, reuse its room (advance the end pointer); otherwise open a new room.
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, j = 0; for (const s of starts) { if (s < ends[j]) rooms++; else j++; } return rooms;}Equivalent: sort by start and keep a min-heap of end times; the heap size is the answer.