Arrays
Arrays in JavaScript for DSA
Almost every DSA problem starts with an array. Knowing which of its methods are cheap and which quietly cost O(n) is most of what separates a fast solution from a slow one.
What an array actually is
A JavaScript array is an indexed list. Reading items[5] does not search - it jumps straight there. That is why index access is O(1) however long the array is.
Everything else follows from that one fact.
The costs you have to know
Cheap and expensive operations
javascript
const items = [10, 20, 30, 40, 50]
// O(1) — the end of the array is right there.
items[2] // read by index
items.push(60) // add to the end
items.pop() // remove from the end
// O(n) — everything after the change shifts along.
items.shift() // remove from the front
items.unshift(5) // add to the front
items.splice(2, 0, 25) // insert in the middle
// O(n) — has to look at every element.
items.indexOf(30)
items.includes(30)
items.find((n) => n > 25)
console.log(items) // the array after the operations abovepush and pop are fast because nothing else moves. shift and unshift are slow because every remaining element slides one place.
The mistake this causes
Draining a queue with shift() looks natural and is quadratic:
The slow queue and the fast one
javascript
// O(n squared) overall — every shift() moves the whole array.
function drainSlow(items) {
const out = []
while (items.length) out.push(items.shift())
return out
}
// O(n) overall — move a pointer instead of the data.
function drainFast(items) {
const out = []
for (let i = 0; i < items.length; i++) out.push(items[i])
return out
}
console.log(drainSlow([1, 2, 3])) // [1, 2, 3]
console.log(drainFast([1, 2, 3])) // [1, 2, 3]On a hundred items you will never notice. On a hundred thousand, the first takes minutes and the second takes milliseconds.
Copying is not free
slice, spread and concat each build a new array, so each is O(n) in time and space. One inside a loop is a common accidental O(n squared):
An accidental quadratic
javascript
const items = [1, 2, 3, 4, 5]
// Looks harmless. Is O(n squared).
let result = []
for (const n of items) {
result = [...result, n] // a fresh copy every iteration
}
// O(n).
const result2 = []
for (const n of items) {
result2.push(n)
}
console.log(result) // [1, 2, 3, 4, 5]
console.log(result2) // [1, 2, 3, 4, 5]Rule of thumb
- Work at the end of an array whenever you can - push and pop are free.
- Removing from the front repeatedly means you want a pointer or a queue, not
shift(). - Any method returning a new array costs O(n). Never put one inside a loop.
Holes and why they hurt
JavaScript arrays can be sparse - const a = []; a[1000] = 1 creates one element, not 1001. Engines store dense arrays in a fast, contiguous form and quietly downgrade sparse ones to a dictionary, which makes every access slower.
Do not create holes
javascript
// Downgrades the array to dictionary mode.
const slow = []
slow[500] = "x"
// Stays fast: fill first, then write.
const fast = new Array(501).fill(null)
fast[500] = "x"
// delete leaves a hole. Use splice or a filter instead.
const items = [1, 2, 3]
delete items[1] // [1, <empty>, 3] — avoid
items.splice(1, 1) // [1, 3] — fine
console.log(slow.length, "with a hole at index 0:", 0 in slow) // 501 false
console.log(fast.length, "no hole:", 0 in fast) // 501 true
console.log(items)The practical rule: build arrays by pushing from empty, or preallocate with new Array(n).fill(...). Never assign past the end, and never delete an element.
Length is writable
Setting items.length = 0 empties an array in place, and items.length = 3 truncates it. This is genuinely useful when you must keep the same array reference - a read-and-write-pointer pass ends with exactly this move.