Array Operations
You know what an array is. Now you need to know what you can do with one. This page walks through every fundamental operation — traversal, insertion, deletion, search, sort, and rotation — with code, complexity analysis, and the patterns that show up in interview problems over and over again.
Traversal
Traversal means visiting every element exactly once. JavaScript gives you several ways to do it, each with different use-cases.
const nums = [10, 20, 30, 40, 50];
// 1. Classic for loop — use when you need the index
for (let i = 0; i < nums.length; i++) {
console.log(i, nums[i]);
}
// 2. for...of — cleaner when you only need the value
for (const n of nums) {
console.log(n);
}
// 3. forEach — functional style, cannot break out early
nums.forEach((value, index) => {
console.log(index, value);
});
// 4. map — traversal that produces a new array of the same length
const doubled = nums.map(n => n * 2); // [20, 40, 60, 80, 100]
// 5. Reverse traversal — useful for in-place deletion or right-to-left problems
for (let i = nums.length - 1; i >= 0; i--) {
console.log(nums[i]); // 50, 40, 30, 20, 10
}Insertion
There are three positions to insert into an array, each with a different cost.
At the end — O(1) amortised
The cheapest insertion. The engine may occasionally reallocate, but averaged over many appends the cost is constant.
const arr = [1, 2, 3]; arr.push(4); // [1, 2, 3, 4] — O(1) amortised // Manual equivalent (informative, not idiomatic) arr[arr.length] = 5; // [1, 2, 3, 4, 5] — O(1)
At the beginning — O(n)
Every existing element shifts one index to the right to make room at index 0.
const arr = [1, 2, 3];
arr.unshift(0); // [0, 1, 2, 3] — O(n): shifts all elements
// Manual shift-right (shows what unshift does internally)
function insertAtStart(arr, val) {
for (let i = arr.length; i > 0; i--) {
arr[i] = arr[i - 1]; // shift each element one right
}
arr[0] = val;
return arr;
}In the middle — O(n)
Elements after the insertion point shift right. On average, n/2 elements move.
const arr = [1, 2, 4, 5];
arr.splice(2, 0, 3); // [1, 2, 3, 4, 5] — O(n): shifts 4 and 5
// Manual middle insert
function insertAt(arr, index, val) {
for (let i = arr.length; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = val;
return arr;
}
console.log(insertAt([1, 2, 4, 5], 2, 3)); // [1, 2, 3, 4, 5]Deletion
Deletion mirrors insertion — position determines cost.
From the end — O(1)
const arr = [1, 2, 3, 4]; const last = arr.pop(); // removes and returns 4 → arr is [1, 2, 3]
From the beginning — O(n)
const arr = [1, 2, 3, 4]; const first = arr.shift(); // removes and returns 1 → arr is [2, 3, 4] // Every remaining element shifts one index left — O(n)
From the middle — O(n)
const arr = [1, 2, 3, 4, 5];
arr.splice(2, 1); // remove 1 element at index 2 → [1, 2, 4, 5]
// Manual middle delete
function deleteAt(arr, index) {
for (let i = index; i < arr.length - 1; i++) {
arr[i] = arr[i + 1]; // shift elements left
}
arr.length--; // trim the last slot
return arr;
}
console.log(deleteAt([1, 2, 3, 4, 5], 2)); // [1, 2, 4, 5]Linear Search
Linear search scans every element from left to right until it finds the target or exhausts the array. It works on any array — sorted or unsorted.
Time: O(n) worst case, O(1) best case. Space: O(1).
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i; // found — return index
}
return -1; // not found
}
console.log(linearSearch([5, 3, 8, 1, 9], 8)); // 2
console.log(linearSearch([5, 3, 8, 1, 9], 7)); // -12 -1
Binary Search
Binary search works exclusively on sorted arrays. Instead of scanning element by element, it repeatedly halves the search space by comparing the target to the middle element.
- If the middle element equals the target — done.
- If the target is smaller — discard the right half.
- If the target is larger — discard the left half.
Each step eliminates half the remaining candidates, giving O(log n) time.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// Avoid integer overflow: use (left + (right - left) / 2) in other languages
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid; // found
if (arr[mid] < target) left = mid + 1; // target is in right half
else right = mid - 1; // target is in left half
}
return -1; // not found
}
const sorted = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sorted, 7)); // 3
console.log(binarySearch(sorted, 6)); // -1
console.log(binarySearch(sorted, 1)); // 0 — first element
console.log(binarySearch(sorted, 13)); // 6 — last element3 -1 0 6
Algorithm | Prerequisite | Time | Space | Use when |
|---|---|---|---|---|
Linear search | None | O(n) | O(1) | Array is unsorted or small |
Binary search | Array must be sorted | O(log n) | O(1) | Large sorted array, frequent queries |
Sorting
JavaScript's built-in Array.prototype.sort uses TimSort (a hybrid of merge sort and insertion sort). It runs in O(n log n) in all practical cases and sorts in-place.
Critical gotcha: Without a comparator, sort converts elements to strings and sorts lexicographically. [10, 9, 2].sort() gives [10, 2, 9], not [2, 9, 10]. Always pass a numeric comparator.
const nums = [64, 3, 25, 12, 22, 11];
// Wrong — lexicographic sort
console.log([10, 9, 2].sort()); // [10, 2, 9] ❌
// Correct — numeric ascending
const asc = [...nums].sort((a, b) => a - b);
console.log(asc); // [3, 11, 12, 22, 25, 64] ✓
// Numeric descending
const desc = [...nums].sort((a, b) => b - a);
console.log(desc); // [64, 25, 22, 12, 11, 3] ✓
// Sort objects by a field
const people = [
{ name: 'Alice', age: 30 },
{ name: 'Bob', age: 25 },
{ name: 'Carol', age: 35 },
];
people.sort((a, b) => a.age - b.age);
console.log(people.map(p => p.name)); // ['Bob', 'Alice', 'Carol'][10, 2, 9] [3, 11, 12, 22, 25, 64] [64, 25, 22, 12, 11, 3] ['Bob', 'Alice', 'Carol']
Reversing
Two approaches: in-place (O(1) space) or creating a new reversed array (O(n) space).
// In-place reverse — swap elements from both ends toward the middle
function reverseInPlace(arr) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]; // ES6 destructure swap
left++;
right--;
}
return arr;
}
const a = [1, 2, 3, 4, 5];
console.log(reverseInPlace(a)); // [5, 4, 3, 2, 1] (original mutated)
// Built-in — also in-place, mutates the original
const b = [1, 2, 3, 4, 5];
b.reverse();
console.log(b); // [5, 4, 3, 2, 1]
// Non-mutating — spread then reverse
const c = [1, 2, 3, 4, 5];
const reversed = [...c].reverse();
console.log(c); // [1, 2, 3, 4, 5] — original intact
console.log(reversed); // [5, 4, 3, 2, 1]Array Rotation
Rotation shifts elements cyclically. A left rotation by k moves each element k positions to the left; elements that fall off the left end wrap around to the right. A right rotation goes the other direction.
Naive approach (O(k×n)): Rotate one step at a time, k times.
Optimal approach (O(n)) — the reversal trick:
To right-rotate an array by k steps:
- Reverse the entire array.
- Reverse the first k elements.
- Reverse the remaining n-k elements.
function reverse(arr, left, right) {
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
// Right-rotate arr by k positions — O(n) time, O(1) space
function rotateRight(arr, k) {
const n = arr.length;
k = k % n; // handle k > n
if (k === 0) return arr;
reverse(arr, 0, n - 1); // step 1: reverse entire array
reverse(arr, 0, k - 1); // step 2: reverse first k elements
reverse(arr, k, n - 1); // step 3: reverse remaining n-k elements
return arr;
}
console.log(rotateRight([1, 2, 3, 4, 5, 6, 7], 3));
// Original: [1, 2, 3, 4, 5, 6, 7]
// After step 1: [7, 6, 5, 4, 3, 2, 1]
// After step 2: [5, 6, 7, 4, 3, 2, 1]
// After step 3: [5, 6, 7, 1, 2, 3, 4] ✓
// Left rotation — right-rotate by (n - k)
function rotateLeft(arr, k) {
return rotateRight(arr, arr.length - (k % arr.length));
}
console.log(rotateLeft([1, 2, 3, 4, 5], 2)); // [3, 4, 5, 1, 2][5, 6, 7, 1, 2, 3, 4] [3, 4, 5, 1, 2]
Frequency Count Pattern
Counting how often each element appears is one of the most reused patterns in DSA. It converts an O(n²) "check every pair" approach into an O(n) single-pass.
Use a plain object when keys are integers or strings you control; use a Map when keys could be any value or when insertion-order matters.
// Count frequencies with a plain object
function frequencyCount(arr) {
const freq = {};
for (const val of arr) {
freq[val] = (freq[val] || 0) + 1;
}
return freq;
}
console.log(frequencyCount(['a', 'b', 'a', 'c', 'b', 'a']));
// { a: 3, b: 2, c: 1 }
// Count frequencies with a Map (preserves any key type)
function frequencyMap(arr) {
const map = new Map();
for (const val of arr) {
map.set(val, (map.get(val) || 0) + 1);
}
return map;
}
// Find the most frequent element
function mostFrequent(arr) {
const freq = frequencyCount(arr);
let maxCount = 0;
let result = null;
for (const [key, count] of Object.entries(freq)) {
if (count > maxCount) {
maxCount = count;
result = key;
}
}
return result;
}
console.log(mostFrequent([1, 2, 2, 3, 3, 3, 4])); // '3' (returned as string key){ a: 3, b: 2, c: 1 }
3In-Place Modification Pattern
Many problems ask you to modify an array without using extra space (O(1) space constraint). The key idea: use a write pointer that tracks where the next valid element should go. A read pointer scans all elements; when it finds a valid one, it writes it at the write pointer location.
// Remove all occurrences of val from nums in-place
// Returns the new length; elements beyond that length don't matter
function removeElement(nums, val) {
let writePtr = 0;
for (let readPtr = 0; readPtr < nums.length; readPtr++) {
if (nums[readPtr] !== val) {
nums[writePtr] = nums[readPtr];
writePtr++;
}
}
return writePtr;
}
const arr = [3, 2, 2, 3, 4, 3, 5];
const newLen = removeElement(arr, 3);
console.log(arr.slice(0, newLen)); // [2, 2, 4, 5]Partitioning
Partitioning rearranges an array so that elements meeting a condition appear before elements that do not — without necessarily sorting. The Dutch National Flag problem (three-way partitioning) is a classic example. Simpler two-way partitioning looks like this:
// Partition: all even numbers before all odd numbers
// Two-pointer approach — O(n) time, O(1) space
function partitionEvenOdd(arr) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
while (left < right && arr[left] % 2 === 0) left++; // skip even
while (left < right && arr[right] % 2 !== 0) right--; // skip odd
if (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return arr;
}
console.log(partitionEvenOdd([3, 1, 2, 4, 7, 6])); // [6, 4, 2, 1, 7, 3] (order within groups may vary)Problem 1 — Rotate Array (LeetCode 189)
LeetCode 189 · Medium
Given an integer array nums, rotate the array to the right by k steps.
We already covered the reversal trick above. Here it is in its interview-ready form.
function rotate(nums, k) {
const n = nums.length;
k = k % n; // k could be larger than n
if (k === 0) return;
const rev = (l, r) => {
while (l < r) {
[nums[l], nums[r]] = [nums[r], nums[l]];
l++; r--;
}
};
rev(0, n - 1); // reverse whole array
rev(0, k - 1); // reverse first k
rev(k, n - 1); // reverse rest
}
const a = [1, 2, 3, 4, 5, 6, 7];
rotate(a, 3);
console.log(a); // [5, 6, 7, 1, 2, 3, 4]
const b = [-1, -100, 3, 99];
rotate(b, 2);
console.log(b); // [3, 99, -1, -100][5, 6, 7, 1, 2, 3, 4] [3, 99, -1, -100]
Problem 2 — Move Zeroes (LeetCode 283)
LeetCode 283 · Easy
Move all zeros to the end of the array while maintaining the relative order of the non-zero elements. Do it in-place with the minimum number of operations.
Use the write-pointer pattern: scan with a read pointer; every time you find a non-zero, write it at the write pointer and advance it. Then fill the remainder of the array with zeros.
function moveZeroes(nums) {
let writePtr = 0;
// Phase 1: compact non-zero elements to the front
for (let readPtr = 0; readPtr < nums.length; readPtr++) {
if (nums[readPtr] !== 0) {
nums[writePtr] = nums[readPtr];
writePtr++;
}
}
// Phase 2: fill the rest with zeros
for (let i = writePtr; i < nums.length; i++) {
nums[i] = 0;
}
}
const a = [0, 1, 0, 3, 12];
moveZeroes(a);
console.log(a); // [1, 3, 12, 0, 0]
const b = [0, 0, 1];
moveZeroes(b);
console.log(b); // [1, 0, 0][1, 3, 12, 0, 0] [1, 0, 0]
Problem 3 — Find the Duplicate Number
LeetCode 287 · Medium
Given an array of n+1 integers where each integer is in the range [1, n] inclusive, find the one duplicate. Only one number is repeated, but it may appear more than twice.
Constraint that makes this interesting: You must not modify the array and use only O(1) extra space.
Solution — Floyd's cycle detection (tortoise and hare): Treat array values as "next pointers" (index i points to nums[i]). Because one value is duplicated, two indices point to the same next index, creating a cycle. Floyd's algorithm finds the cycle entrance, which is the duplicate.
function findDuplicate(nums) {
// Phase 1: find the intersection point inside the cycle
let slow = nums[0];
let fast = nums[0];
do {
slow = nums[slow]; // move one step
fast = nums[nums[fast]]; // move two steps
} while (slow !== fast);
// Phase 2: find the cycle entrance (= the duplicate number)
slow = nums[0]; // reset slow to start
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast]; // both move one step now
}
return slow;
}
console.log(findDuplicate([1, 3, 4, 2, 2])); // 2
console.log(findDuplicate([3, 1, 3, 4, 2])); // 32 3
Problem 4 — Maximum Product Subarray
LeetCode 152 · Medium
Find the contiguous subarray within an array that has the largest product.
Why this is tricky: Multiplying two negatives gives a positive, so the minimum product so far could suddenly become the maximum when multiplied by a negative number.
Key insight: Track both the maximum and minimum product ending at each position. At each step, swap them if the current element is negative.
function maxProduct(nums) {
let maxSoFar = nums[0];
let minSoFar = nums[0]; // minimum matters because of negative × negative
let result = nums[0];
for (let i = 1; i < nums.length; i++) {
const n = nums[i];
// When n is negative, max and min swap roles
const tempMax = Math.max(n, maxSoFar * n, minSoFar * n);
const tempMin = Math.min(n, maxSoFar * n, minSoFar * n);
maxSoFar = tempMax;
minSoFar = tempMin;
result = Math.max(result, maxSoFar);
}
return result;
}
console.log(maxProduct([2, 3, -2, 4])); // 6 (subarray [2,3])
console.log(maxProduct([-2, 0, -1])); // 0 (subarray [0])
console.log(maxProduct([-2, 3, -4])); // 24 (subarray [-2,3,-4])6 0 24
Complexity Summary
Operation | Time | Space | Notes |
|---|---|---|---|
Traversal (for/forEach/map) | O(n) | O(1) or O(n) | O(n) space only if producing new array |
Insert at end (push) | O(1) amortised | O(1) | Occasional O(n) resize |
Insert at start (unshift) | O(n) | O(1) | Shifts all elements |
Insert at middle (splice) | O(n) | O(1) | Shifts n/2 elements on average |
Delete at end (pop) | O(1) | O(1) | Always constant |
Delete at start (shift) | O(n) | O(1) | Shifts all elements |
Delete at middle (splice) | O(n) | O(1) | Shifts remaining elements |
Linear search | O(n) | O(1) | Works on any array |
Binary search | O(log n) | O(1) | Requires sorted array |
Sort (built-in) | O(n log n) | O(log n) | V8 TimSort; log n stack space |
Reverse | O(n) | O(1) | Two-pointer swap |
Rotation (reversal trick) | O(n) | O(1) | Three reverse passes |
Frequency count | O(n) | O(k) | k = number of distinct values |
In-place write-pointer | O(n) | O(1) | Classic pattern for compaction problems |
Summary
Traversal is O(n) regardless of style; use for...of for values, classic for when you need the index
Insertion and deletion cost depends entirely on position — end is O(1), anywhere else is O(n)
Binary search is O(log n) but requires a sorted array — always verify this precondition
The reversal trick rotates an array in O(n) time and O(1) space with three reverse passes
Frequency maps turn O(n²) pairwise comparisons into O(n) single-pass solutions
The write-pointer (two-pointer) pattern enables O(1)-space in-place compaction and partitioning
Track both max and min products simultaneously when an array contains negative numbers