Array Logic Problems

Rotating an array right by k moves the last k elements to the front while shifting the rest to the right.

Use slice: take arr.slice(-k) for the tail, then arr.slice(0, -k) for the head. Use k % arr.length to handle rotations larger than the array size.

The spread approach creates a new array — for in-place rotation, use the reverse-reverse-reverse trick in O(1) extra space.

function rotateRight(arr, k) {
  k = k % arr.length;
  if (k === 0) return arr;
  return [...arr.slice(-k), ...arr.slice(0, -k)];
}
// Input: [1,2,3,4,5], k=2   => Output: [4,5,1,2,3]
// Input: [1,2,3], k=1        => Output: [3,1,2]
// Input: [1,2,3], k=4        => Output: [3,1,2] (k%3=1)

In-place O(1) space: reverse all → reverse first k → reverse remaining (3 reverse operations).

Always apply k = k % n first — rotating by n is a no-op, and k can be larger than the array.

A duplicate is an element that appears more than once. The first duplicate is the one whose second occurrence comes earliest in the array.

Use a Set to track seen values. The first time you encounter a value already in the Set, that's the first duplicate.

This O(n) approach with O(n) space is better than the O(n²) nested loop comparison approach.

function firstDuplicate(arr) {
  let seen = new Set();
  for (let val of arr) {
    if (seen.has(val)) return val;
    seen.add(val);
  }
  return -1;
}
// Input: [2,1,3,5,3,2]   => Output: 3  (first repeat)
// Input: [1,2,3,4]        => Output: -1 (no duplicate)
// Input: [1,1,2,3]        => Output: 1

Note: "First duplicate" means the element whose 2nd occurrence comes first — not the smallest duplicate.

If values are in range [1..n], use the array itself as a hash by negating visited indices in O(1) space.

Two Sum is a classic hash map problem: for each number, check if its complement (target - num) has already been seen.

Store each element in a Map with its index as value. When the complement is found in the Map, return both indices immediately.

This O(n) hash map approach is far better than the O(n²) brute force of checking all pairs.

function twoSum(nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let comp = target - nums[i];
    if (map.has(comp)) return [map.get(comp), i];
    map.set(nums[i], i);
  }
  return null;
}
// Input: [2,7,11,15], target=9   => Output: [0,1] (2+7=9)
// Input: [3,2,4], target=6       => Output: [1,2] (2+4=6)
// Input: [3,3], target=6         => Output: [0,1]

Time: O(n). Space: O(n) for the Map. Each element is processed exactly once.

The Map stores values as keys and indices as values — reversed from the array structure for fast complement lookup.

Kadane's Algorithm finds the contiguous subarray with the largest sum in O(n) time and O(1) space.

Track two values: cur (current running sum) and max (best seen so far). At each element: extend or restart the current subarray, then update max.

The key insight: if the current sum becomes negative, it's always better to start fresh from the next element.

function maxSubarray(arr) {
  let max = arr[0], cur = arr[0];
  for (let i = 1; i < arr.length; i++) {
    cur = Math.max(arr[i], cur + arr[i]);
    max = Math.max(max, cur);
  }
  return max;
}
// Input: [-2,1,-3,4,-1,2,1,-5,4]  => Output: 6  ([4,-1,2,1])
// Input: [1]                       => Output: 1
// Input: [-1,-2,-3]                => Output: -1 (all negative)

Time: O(n). Space: O(1). Handles all-negative arrays correctly (returns the least negative element).

To also return the actual subarray, track start/end indices when cur resets and when max updates.

Given two sorted arrays, merge them into a single sorted array without using built-in sort on the combined array.

Use two pointers starting at the beginning of each array. Compare elements at both pointers, push the smaller one into the result, and advance that pointer.

After the while loop, one array may have remaining elements — append them directly since they're already sorted.

function mergeSorted(a, b) {
  let res = [], i = 0, j = 0;
  while (i < a.length && j < b.length)
    res.push(a[i] < b[j] ? a[i++] : b[j++]);
  return [...res, ...a.slice(i), ...b.slice(j)];
}
// Input: [1,3,5], [2,4,6]   => Output: [1,2,3,4,5,6]
// Input: [1,2], [3,4]        => Output: [1,2,3,4]
// Input: [], [1,2,3]         => Output: [1,2,3]

Time: O(n + m). Space: O(n + m) for the result array.

This two-pointer merge is the core subroutine of merge sort and external sorting algorithms.

Rearrange the array so all non-zero elements appear first (in original order) and all zeros are pushed to the end.

Use a write pointer pos: copy each non-zero element to position pos and advance pos. Then fill from pos to the end with zeros.

This in-place approach is O(n) time and O(1) space — no extra array needed.

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

Two-pointer variation: swap arr[i] with arr[pos] to avoid overwriting zeros — preserves relative order too.

The relative order of non-zero elements is preserved — this distinguishes it from simple partitioning.

Find the second largest distinct element in a single pass by tracking two maximums simultaneously.

Maintain first and second maximums. When a new element exceeds first, update both. When it's between first and second (and distinct from first), update only second.

A single traversal is optimal — no sorting or partial sort needed.

function secondLargest(arr) {
  let first = -Infinity, second = -Infinity;
  for (let val of arr) {
    if (val > first) { second = first; first = val; }
    else if (val > second && val !== first) second = val;
  }
  return second === -Infinity ? null : second;
}
// Input: [3,1,4,1,5,9,2,6]   => Output: 6
// Input: [5,5,5]               => Output: null (all same)
// Input: [1,2]                 => Output: 1

Time: O(n). Space: O(1). Check val !== first to ensure the second largest is genuinely distinct.

Variation: if duplicates count separately ("second occurrence largest"), remove the val !== first check.

Frequency counting records how many times each unique value appears in an array — a fundamental technique for solving many array problems.

Use a plain object or a Map: for each element, check if a count already exists and increment it, or initialize it to 1.

This is the foundation for problems like finding the majority element, top-k frequent elements, and anagram checking.

function frequency(arr) {
  let map = {};
  for (let val of arr) map[val] = (map[val] || 0) + 1;
  return map;
}
// Using Map for non-string keys:
function frequencyMap(arr) {
  let map = new Map();
  for (let val of arr) map.set(val, (map.get(val) || 0) + 1);
  return map;
}
// Input: [1,2,2,3,3,3]   => Output: {1:1, 2:2, 3:3}
// Input: ['a','b','a']   => Output: {a:2, b:1}

Time: O(n). Space: O(k) where k is the number of unique values.

The (map[val] || 0) + 1 idiom handles the first occurrence cleanly without an if-else check.

The intersection of two arrays contains elements that appear in both — without duplicates in the result.

Convert the first array to a Set for O(1) lookup, then filter the second array keeping only values present in the Set.

Wrap the result in another Set to remove duplicates that might appear multiple times in array b.

function intersection(a, b) {
  let setA = new Set(a);
  return [...new Set(b.filter(v => setA.has(v)))];
}
// Input: [1,2,3], [2,3,4]     => Output: [2,3]
// Input: [1,2,2,3], [2,2,4]   => Output: [2]  (deduped)
// Input: [1,2], [3,4]          => Output: []

Time: O(n + m) where n and m are the array lengths. Space: O(n) for the Set.

For sorted arrays, use the two-pointer approach for O(n+m) time without extra space.

The union of two arrays contains all unique elements from both arrays combined.

The simplest approach: merge both arrays and pass them to a Set constructor, which automatically removes duplicates.

This leverages JavaScript's Set data structure which stores only unique values.

function union(a, b) {
  return [...new Set([...a, ...b])];
}
// Input: [1,2,3], [3,4,5]    => Output: [1,2,3,4,5]
// Input: [1,1,2], [2,3,3]    => Output: [1,2,3]
// Input: [1,2], []            => Output: [1,2]

Time: O(n + m). Space: O(n + m) for the Set and spread arrays.

For finding only elements in one array but NOT the other, use Set difference: a.filter(x => !setB.has(x)).

The majority element appears more than n/2 times in the array. Boyer-Moore Voting Algorithm finds it in O(n) time and O(1) space.

Maintain a candidate and a count: increment count if the current element matches candidate; otherwise decrement. When count reaches 0, update the candidate.

The key insight: if an element appears more than n/2 times, it will "survive" all cancellations and remain as the final candidate.

function majorityElement(nums) {
  let candidate = nums[0], count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) { candidate = nums[i]; count = 1; }
    else if (nums[i] === candidate) count++;
    else count--;
  }
  return candidate;
}
// Input: [3,2,3]              => Output: 3
// Input: [2,2,1,1,1,2,2]      => Output: 2
// Input: [1]                   => Output: 1

Boyer-Moore: O(n) time, O(1) space — optimal. Assumes majority element always exists.

If majority existence is not guaranteed, verify the candidate by counting its occurrences after the algorithm.

The Dutch National Flag problem partitions an array of 0s, 1s, and 2s into three sections without using extra space.

Use three pointers: low (next position for 0), mid (current element), high (next position for 2). Swap elements into correct regions while mid <= high.

This achieves a single O(n) pass with no extra space, unlike counting sort which requires two passes.

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

Three pointers: low tracks 0-boundary, high tracks 2-boundary, mid scans. After swap with high, don't increment mid.

This algorithm generalizes to sorting arrays with k distinct values using k-1 pointers.

For each position i, compute the product of all elements except nums[i] WITHOUT using division. This handles zeros correctly.

Two-pass approach: left pass fills a prefix products array; right pass multiplies each position by its suffix product.

This runs in O(n) time and O(1) extra space (not counting the output array).

function productExceptSelf(nums) {
  let n = nums.length, result = Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) { result[i] = left; left *= nums[i]; }
  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: [2,3,4,5]       => Output: [60,40,30,24]
// Input: [-1,1,0,-3,3]   => Output: [0,0,9,0,0]

Left pass: result[i] = product of all elements to the LEFT of i.

Right pass: multiplies each result[i] by the product of all elements to the RIGHT of i.

An equilibrium index is a position where the sum of elements to its left equals the sum of elements to its right.

Compute the total sum, then traverse the array maintaining a left sum. At each index i: right sum = total - leftSum - nums[i]. If leftSum === rightSum, i is the equilibrium index.

This single-pass approach avoids recomputing sums from scratch at each position.

function equilibrium(nums) {
  let total = nums.reduce((s, n) => s + n, 0), leftSum = 0;
  for (let i = 0; i < nums.length; i++) {
    let rightSum = total - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }
  return -1;
}
// Input: [1,7,3,6,5,6]   => Output: 3  (leftSum=11, rightSum=11)
// Input: [1,2,3]          => Output: -1 (no equilibrium)
// Input: [2,4,2]          => Output: 1  (leftSum=2, rightSum=2)

Time: O(n). Space: O(1). The total sum is computed first, then subtracted during traversal.

Multiple equilibrium points can exist — return first found or modify to return all indices.

Given a sorted array, remove duplicates such that each element appears only once, returning the new length.

Use a write pointer k starting at 1. For each element from index 1, if it differs from the previous unique element, write it to position k and increment k.

The in-place constraint means no extra arrays — just overwriting duplicates with the next unique value.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let k = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) nums[k++] = nums[i];
  }
  return k;
}
// Input: [1,1,2,3,3,4]    => Output: 4, array=[1,2,3,4,...]
// Input: [0,0,1,1,1,2]    => Output: 3, array=[0,1,2,...]
// Input: [1]               => Output: 1

Two-pointer pattern: slow pointer k tracks write position; fast pointer i scans the array.

Variation: allow at most k duplicates by changing the comparison to nums[i] !== nums[k-2].

An element is a leader if it's greater than all elements to its right. The rightmost element is always a leader.

Traverse right to left, maintaining the maximum seen so far. An element is a leader if it's greater than or equal to the current max.

This single right-to-left pass avoids comparing each element with all elements to its right (brute O(n²)).

function findLeaders(arr) {
  let leaders = [], maxRight = arr[arr.length - 1];
  leaders.push(maxRight);
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] > maxRight) {
      maxRight = arr[i];
      leaders.push(arr[i]);
    }
  }
  return leaders.reverse();
}
// Input: [16,17,4,3,5,2]   => Output: [17,5,2]
// Input: [1,2,3,4,5]        => Output: [5]  (only rightmost)
// Input: [5,4,3,2,1]        => Output: [5,4,3,2,1] (all leaders)

Time: O(n). Space: O(n) for result (O(1) extra if we just print).

The rightmost element is the guaranteed leader. Traverse right to left and update max to find others.

In a sorted array, use two pointers — one at the start, one at the end — to find a pair that sums to target in O(n) time.

If the sum equals target: return the pair. If less: move left pointer right to increase sum. If greater: move right pointer left to decrease sum.

The sorted property is essential — unsorted arrays require a hash set approach.

function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return null;
}
// Input: [1,2,3,4,6], target=6    => Output: [1,3] (indices 2+4=6)
// Input: [2,7,11,15], target=9    => Output: [0,1] (2+7=9)
// Input: [1,3,5,7], target=12     => Output: [2,3] (5+7=12)

Time: O(n). Two pointers converge toward each other — each step eliminates one element from consideration.

Works for exactly 2 elements. For 3-sum extend with an outer loop (O(n²)) to fix one element and two-sum the rest.

Find three elements a, b, c in an array such that a + b + c = 0. This is the classic 3Sum problem.

Sort the array. For each element a at index i, use two pointers (left=i+1, right=end) to find b and c such that b+c = -a.

Sorting enables the two-pointer technique and also makes it easy to skip duplicate triplets.

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  let result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue; // skip dups
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      let sum = nums[i] + nums[lo] + nums[hi];
      if (sum === 0) { result.push([nums[i],nums[lo],nums[hi]]); lo++; hi--; }
      else if (sum < 0) lo++;
      else hi--;
    }
  }
  return result;
}
// Input: [-1,0,1,2,-1,4]  => Output: [[-1,-1,2],[-1,0,1]]
// Input: [0,0,0]           => Output: [[0,0,0]]
// Input: [1,2,3]           => Output: []

Time: O(n²). Space: O(1) ignoring output. Sort + two-pointer is optimal for this problem.

Skip duplicate elements after processing each index to avoid duplicate triplets in the result.

Find the subarray of exactly k consecutive elements with the maximum sum, using the sliding window technique.

Compute the sum of the first k elements as the initial window. Then slide: add the next element and remove the first element of the previous window. Track the maximum.

The sliding window avoids recomputing sums from scratch at each position, reducing O(n*k) to O(n).

function maxSumK(nums, k) {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let max = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    max = Math.max(max, windowSum);
  }
  return max;
}
// Input: [2,3,4,1,5], k=3    => Output: 10 ([3,4,1+5]... actually [2,3,4]=9 vs [4,1,5]=10)
// Input: [1,4,2,10,23,3], k=4 => Output: 39 ([4,2,10,23])
// Input: [1,2,3,4,5], k=2     => Output: 9  ([4,5])

Window slide: windowSum += nums[i] - nums[i-k] adds new element to window and removes oldest.

This fixed-size sliding window pattern is the simplest variant — variable size windows are used for other constraints.

A nested array like [[1,[2]],3] needs flattening to [1,2,3]. JavaScript provides Array.flat(depth) but the recursive approach is educational.

Use recursion: for each element, if it's an array recurse deeper and spread/concat the result; otherwise push the element directly.

The depth parameter controls how many levels of nesting to flatten — Infinity flattens completely.

function flatten(arr, depth = Infinity) {
  let result = [];
  for (let item of arr) {
    if (Array.isArray(item) && depth > 0)
      result.push(...flatten(item, depth - 1));
    else result.push(item);
  }
  return result;
}
// Input: [1,[2,3],[4,[5,6]]]   => Output: [1,2,3,4,5,6]
// Input: [1,[2,[3,[4]]]], d=2  => Output: [1,2,3,[4]]
// Built-in: [1,[2]].flat(Infinity) => [1,2]

Array.flat(n) is built-in from ES2019. For n=1 it's a shallow flatten; for Infinity it's fully recursive.

Common in data processing pipelines where nested structures need to be collapsed before further operations.

Find the shortest contiguous subarray whose sum is ≥ target. This uses a variable-size sliding window.

Expand the window by moving the right pointer. When sum ≥ target, try shrinking from the left while still meeting the condition. Track the minimum length at each valid window.

This two-pointer sliding window approach is O(n) linear time — far better than the O(n²) brute force approach.

function minSubarrayLen(target, nums) {
  let left = 0, sum = 0, minLen = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left++];
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// Input: target=7, [2,3,1,2,4,3]    => Output: 2 ([4,3])
// Input: target=4, [1,4,4]           => Output: 1 ([4])
// Input: target=11, [1,1,1,1,1,1,1]  => Output: 0 (impossible)

Time: O(n) — each element is added and removed from the window at most once.

The inner while loop may run multiple times for a single right position but the total left movements across all iterations is still O(n).

Given a binary array (0s and 1s), find the length of the longest subarray with equal counts of 0 and 1.

Replace 0s with -1s. The problem becomes: find the longest subarray with sum = 0. Use a prefix sum hash map: store the first occurrence of each prefix sum.

When the same prefix sum appears again, the subarray between those indices has sum 0 (equal 0s and 1s).

function findMaxLength(nums) {
  let count = 0, maxLen = 0;
  let map = new Map([[0, -1]]); // sum 0 at index -1
  for (let i = 0; i < nums.length; i++) {
    count += nums[i] === 1 ? 1 : -1;
    if (map.has(count)) maxLen = Math.max(maxLen, i - map.get(count));
    else map.set(count, i);
  }
  return maxLen;
}
// Input: [0,1]           => Output: 2
// Input: [0,1,0]         => Output: 2
// Input: [0,0,1,0,0,0,1,1] => Output: 6

Key trick: map 0→-1 so equal 0s and 1s gives a net sum of 0. Initialize map with {0: -1} for subarrays starting at index 0.

This prefix sum pattern generalizes to find longest subarray with target sum difference between two value types.

Find all pairs (a, b) in an array where |a - b| = k. The pairs can appear in any order.

Use a Set for O(1) lookup. For each element x, check if x+k or x-k exists in the set. This finds both orientations efficiently.

This O(n) approach avoids the O(n²) nested loop comparison of all pairs.

function findPairs(nums, k) {
  let set = new Set(nums), pairs = [];
  let seen = new Set();
  for (let x of nums) {
    if (!seen.has(x) && set.has(x + k)) {
      pairs.push([x, x + k]);
      seen.add(x);
    }
  }
  return pairs;
}
// Input: [1,7,5,9,2,12,3], k=2  => Output: [[1,3],[7,9],[5,7],[3,5]]
// Input: [1,2,3,4,5], k=1        => Output: [[1,2],[2,3],[3,4],[4,5]]
// Input: [1,3,1,5,4], k=0         => Output: [[1,1]] (duplicate pair)

For k=0: finding pairs with difference 0 means finding duplicates. The seen Set prevents counting the same pair multiple times.

Sort + two-pointer also works in O(n log n) and handles k=0 naturally without extra bookkeeping.