Arrays

Common array operation complexities:

• Access by index: O(1)
• Search (unsorted): O(n)
• Search (sorted, binary search): O(log n)
• Insert at end: O(1) amortized
• Insert at beginning/middle: O(n)
• Delete at end: O(1)
• Delete at beginning/middle: O(n)

Insertions and deletions in the middle require shifting elements, leading to O(n) time.

The Two Sum problem asks: given an array and a target, find two indices whose values sum to the target. Use a hash map for O(n) time.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}
// twoSum([2,7,11,15], 9) => [0, 1]

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

Use the two-pointer technique: swap elements from the start and end, moving inward until the pointers meet.

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr;
}
// reverseArray([1,2,3,4,5]) => [5,4,3,2,1]

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

Use a Set to track seen elements. If an element is already in the Set, it is a duplicate.

function findDuplicates(arr) {
    const seen = new Set();
    const duplicates = [];
    for (const num of arr) {
        if (seen.has(num)) {
            duplicates.push(num);
        } else {
            seen.add(num);
        }
    }
    return duplicates;
}
// findDuplicates([1,3,4,2,3,1]) => [3, 1]

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

Rotate an array to the right by k positions using the reversal algorithm: reverse the whole array, then reverse the first k and remaining elements.

function rotateArray(arr, k) {
    k = k % arr.length;
    reverse(arr, 0, arr.length - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, arr.length - 1);
    return arr;
}

function reverse(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start++;
        end--;
    }
}
// rotateArray([1,2,3,4,5], 2) => [4,5,1,2,3]

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

Kadane's Algorithm finds the contiguous subarray with the largest sum in O(n) time. It keeps a running sum and resets when it drops below zero.

function maxSubarraySum(arr) {
    let maxSum = arr[0];
    let currentSum = arr[0];
    for (let i = 1; i < arr.length; i++) {
        currentSum = Math.max(arr[i], currentSum + arr[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}
// maxSubarraySum([-2,1,-3,4,-1,2,1,-5,4]) => 6

Key idea: At each position, decide whether to extend the current subarray or start a new one.

Use two pointers, one for each array, and compare elements to build the merged result.

function mergeSorted(a, b) {
    const result = [];
    let i = 0, j = 0;
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            result.push(a[i++]);
        } else {
            result.push(b[j++]);
        }
    }
    while (i < a.length) result.push(a[i++]);
    while (j < b.length) result.push(b[j++]);
    return result;
}
// mergeSorted([1,3,5], [2,4,6]) => [1,2,3,4,5,6]

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

Use a slow/fast pointer approach. The slow pointer tracks the position of the next unique element.

function removeDuplicates(arr) {
    if (arr.length === 0) return 0;
    let slow = 0;
    for (let fast = 1; fast < arr.length; fast++) {
        if (arr[fast] !== arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1; // length of unique portion
}
// removeDuplicates([1,1,2,2,3]) => 3, arr becomes [1,2,3,...]

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

Use a pointer to track the next non-zero position. Move all non-zero elements forward, then fill the rest with zeros.

function moveZeros(arr) {
    let insertPos = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
            [arr[insertPos], arr[i]] = [arr[i], arr[insertPos]];
            insertPos++;
        }
    }
    return arr;
}
// moveZeros([0,1,0,3,12]) => [1,3,12,0,0]

Time: O(n)  |  Space: O(1). This preserves the relative order of non-zero elements.

Track both the maximum and minimum product ending at each position because a negative × negative can become the largest product.

function maxProduct(nums) {
    let maxProd = nums[0], minProd = nums[0], result = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const candidates = [nums[i], maxProd * nums[i], minProd * nums[i]];
        maxProd = Math.max(...candidates);
        minProd = Math.min(...candidates);
        result = Math.max(result, maxProd);
    }
    return result;
}
// Input:  [2, 3, -2, 4]   => Output: 6  (subarray [2,3])
// Input:  [-2, 0, -1]     => Output: 0
// Input:  [-2, 3, -4]     => Output: 24 (entire array)

Time: O(n)  |  Space: O(1)
Key insight: Always track both max and min because a negative times a negative flips to positive.

Use the sum formula: expected sum of 0..n is n*(n+1)/2. Subtract the actual sum to get the missing value.

function missingNumber(nums) {
    const n = nums.length;
    const expected = n * (n + 1) / 2;
    const actual = nums.reduce((sum, x) => sum + x, 0);
    return expected - actual;
}
// Input:  [3, 0, 1]       => Output: 2
// Input:  [0, 1]          => Output: 2
// Input:  [9,6,4,2,3,5,7,0,1] => Output: 8

Time: O(n)  |  Space: O(1)
Alternative: XOR all indices 0..n with all array values — the missing number is the only one without a pair.

Precompute prefix max sums from left and suffix max sums from right, then combine at each split point.

function maxSumTwoNoOverlap(nums, L, M) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

    const sum = (i, len) => prefix[i + len] - prefix[i];

    let res = 0, maxL = 0, maxM = 0;
    for (let i = L + M; i <= n; i++) {
        maxL = Math.max(maxL, sum(i - L - M, L));
        maxM = Math.max(maxM, sum(i - L - M, M));
        res = Math.max(res, maxL + sum(i - M, M), maxM + sum(i - L, L));
    }
    return res;
}
// Input: nums=[0,6,5,2,2,5,1,9,4], L=1, M=2 => Output: 20

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

Use a Set to track seen numbers. For each element check if its complement exists.

function findAllPairs(arr, target) {
    const seen = new Set();
    const pairs = [];
    for (const num of arr) {
        const comp = target - num;
        if (seen.has(comp)) {
            pairs.push([comp, num]);
        }
        seen.add(num);
    }
    return pairs;
}
// Input: arr=[1,2,3,4,5,6], target=7  => Output: [[1,6],[2,5],[3,4]]
// Input: arr=[1,5,3,3,3],   target=6  => Output: [[3,3]]

Time: O(n)  |  Space: O(n)
Note: For unique pairs only, avoid adding a pair twice by storing visited complements.

Use three pointers: low, mid, high. The mid pointer walks forward — place 0s before low, 2s after high.

function sortColors(arr) {
    let low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++; mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
    return arr;
}
// Input:  [2, 0, 2, 1, 1, 0]  => Output: [0, 0, 1, 1, 2, 2]
// Input:  [2, 0, 1]           => Output: [0, 1, 2]

Time: O(n)  |  Space: O(1) — single pass, no extra storage

Put all numbers into a Set. For each number that is the start of a sequence (num-1 not in set), count how far the sequence extends.

function longestConsecutive(nums) {
    const set = new Set(nums);
    let best = 0;
    for (const num of set) {
        if (!set.has(num - 1)) { // start of a sequence
            let cur = num, streak = 1;
            while (set.has(cur + 1)) { cur++; streak++; }
            best = Math.max(best, streak);
        }
    }
    return best;
}
// Input:  [100,4,200,1,3,2]  => Output: 4  (sequence: 1,2,3,4)
// Input:  [0,3,7,2,5,8,4,6,0,1] => Output: 9

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

Use the Boyer-Moore Voting Algorithm. Cancel out pairs of different elements — the majority element remains.

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;
}
// Input:  [3, 2, 3]                   => Output: 3
// Input:  [2, 2, 1, 1, 1, 2, 2]       => Output: 2
// Input:  [6, 5, 5]                   => Output: 5

Time: O(n)  |  Space: O(1)
Key insight: If majority element exists, it can never be fully cancelled out by minority elements.

Convert the first array to a Set, then check each element of the second array against it.

function intersection(a, b) {
    const setA = new Set(a);
    return [...new Set(b.filter(x => setA.has(x)))];
}
// Input:  a=[1,2,2,1], b=[2,2]     => Output: [2]
// Input:  a=[4,9,5],   b=[9,4,9,8,4] => Output: [4,9]

// For intersection WITH duplicates (each appearing min times):
function intersectWithDups(a, b) {
    const freq = {};
    for (const x of a) freq[x] = (freq[x] || 0) + 1;
    const res = [];
    for (const x of b) {
        if (freq[x] > 0) { res.push(x); freq[x]--; }
    }
    return res;
}
// Input:  a=[1,2,2,1], b=[2,2]   => Output: [2,2]

Time: O(n + m)  |  Space: O(min(n, m))

Build a prefix products array and a suffix products array. The answer for each index is prefix[i] × suffix[i].

function productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n).fill(1);
    // Left pass — prefix products
    let left = 1;
    for (let i = 0; i < n; i++) {
        result[i] = left;
        left *= nums[i];
    }
    // Right pass — multiply suffix products
    let right = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    return result;
}
// Input:  [1, 2, 3, 4]  => Output: [24, 12, 8, 6]
// Input:  [-1, 1, 0,-3,3] => Output: [0, 0, 9, 0, 0]

Time: O(n)  |  Space: O(1) extra (output array not counted)

Use the array itself as a hash map: place each number x at index x-1 if 1 ≤ x ≤ n. Then the first index where arr[i] ≠ i+1 gives the answer.

function firstMissingPositive(nums) {
    const n = nums.length;
    // Place each number in its correct position
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return n + 1;
}
// Input:  [1, 2, 0]       => Output: 3
// Input:  [3, 4, -1, 1]   => Output: 2
// Input:  [7, 8, 9, 11]   => Output: 1

Time: O(n)  |  Space: O(1) — uses the input array in place

Use a prefix sum + hash map. At each index store the prefix sum. If prefixSum - target was seen before, a valid subarray exists.

function subarraySum(nums, target) {
    const map = new Map([[0, 1]]); // prefix sum => count
    let sum = 0, count = 0;
    for (const num of nums) {
        sum += num;
        count += (map.get(sum - target) || 0);
        map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
}
// Input: nums=[1,1,1], target=2     => Output: 2 (indices [0,1] and [1,2])
// Input: nums=[1,2,3], target=3     => Output: 2 ([1,2] and [3])
// Input: nums=[-1,-1,1], target=-1  => Output: 2

Time: O(n)  |  Space: O(n)
The trick: prefixSum[j] - prefixSum[i] = target means subarray from i+1 to j sums to target.

A sorted and rotated array has at most one descent (place where arr[i] > arr[i+1]). Count descents — if count > 1 it is not sorted+rotated.

function isSortedRotated(arr) {
    const n = arr.length;
    let descents = 0;
    for (let i = 0; i < n; i++) {
        if (arr[i] > arr[(i + 1) % n]) descents++;
        if (descents > 1) return false;
    }
    return true;
}
// Input:  [3, 4, 5, 1, 2]  => Output: true  (one descent: 5→1)
// Input:  [2, 1, 3, 4]     => Output: false (two descents)
// Input:  [1, 2, 3]        => Output: true  (zero descents — already sorted)

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

Separate positives and negatives into two lists, then interleave them. Remaining elements go at the end.

function rearrange(arr) {
    const pos = arr.filter(x => x >= 0);
    const neg = arr.filter(x => x < 0);
    const result = [];
    let i = 0, j = 0;
    while (i < pos.length && j < neg.length) {
        result.push(pos[i++]);
        result.push(neg[j++]);
    }
    while (i < pos.length) result.push(pos[i++]);
    while (j < neg.length) result.push(neg[j++]);
    return result;
}
// Input:  [1, 2, -3, -1, -2, 3]  => Output: [1, -3, 2, -1, 3, -2]
// Input:  [-5, -2, 5, 2, 4, 7]   => Output: [5, -5, 2, -2, 4, 7]

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

Sort the array. Fix one element, then use two pointers on the rest to find pairs that sum to its negative.

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 duplicates
        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++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return result;
}
// Input:  [-1, 0, 1, 2, -1, -4]  => Output: [[-1,-1,2],[-1,0,1]]
// Input:  [0, 0, 0]               => Output: [[0,0,0]]

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

Process elements in pairs: compare the two with each other first, then update global min/max. This uses only 3n/2 - 2 comparisons instead of the naive 2n.

function minMax(arr) {
    let min = Infinity, max = -Infinity;
    let i = 0;
    if (arr.length % 2 !== 0) {
        min = max = arr[0];
        i = 1;
    }
    while (i < arr.length) {
        const [lo, hi] = arr[i] < arr[i + 1]
            ? [arr[i], arr[i + 1]] : [arr[i + 1], arr[i]];
        min = Math.min(min, lo);
        max = Math.max(max, hi);
        i += 2;
    }
    return { min, max };
}
// Input:  [3, 5, 1, 8, 2, 7]  => Output: { min: 1, max: 8 }
// Input:  [9]                  => Output: { min: 9, max: 9 }

Comparisons: ~3n/2 (pairs trick) vs ~2n (naive)  |  Time: O(n)  |  Space: O(1)