What array operations cost
Picture a row of cinema seats, numbered from 0, with no gaps allowed. Finding seat 12 is instant: you walk straight to it. A new person sitting at the end of the row is easy too. But if someone wants to sit at seat 0, everyone already seated has to move one seat to the right. And if the person in seat 0 leaves, everyone moves one seat left to close the gap.
Arrays work exactly like that row. That’s why some operations are O(1) and others are O(n), even though each is a single line of code.
Every language here uses a contiguous, growable array (Swift Array, Kotlin/Java ArrayList, JS arrays in their fast mode). Indexing is O(1) and cache-friendly; appending is amortized O(1) because the buffer doubles (or grows by 1.5×) when full; anything that shifts elements is O(n). The interview traps are calls that hide that shift (removeFirst, insert(at: 0), remove(0), shift, splice), copies hidden in slicing, and value semantics in Swift (an array copied before mutation).
| Operation | Cost | Why |
|---|---|---|
Read or write nums[i] | O(1) | Jump straight to the position |
| Add at the end | O(1) on average | Occasionally the array grows into a bigger block |
| Insert or remove at the front or middle | O(n) | Every later element shifts by one |
contains(x) / indexOf(x) | O(n) | Checks elements one by one |
| Copy, slice into a new array, sort | O(n), O(k), O(n log n) | Touches every element (sorting more than once) |
var nums = [3, 5, 8]
nums.append(13) // O(1): nothing moves
nums.insert(1, at: 0) // O(n): 3, 5, 8, 13 all shift right
nums.remove(at: 0) // O(n): they all shift backval nums = mutableListOf(3, 5, 8)
nums.add(13) // O(1): nothing moves
nums.add(0, 1) // O(n): 3, 5, 8, 13 all shift right
nums.removeAt(0) // O(n): they all shift backList<Integer> nums = new ArrayList<>(List.of(3, 5, 8));
nums.add(13); // O(1): nothing moves
nums.add(0, 1); // O(n): 3, 5, 8, 13 all shift right
nums.remove(0); // O(n): they all shift backconst nums = [3, 5, 8];
nums.push(13); // O(1): nothing moves
nums.unshift(1); // O(n): 3, 5, 8, 13 all shift right
nums.shift(); // O(n): they all shift backChanging an array while you walk through it
Removing an element shifts everything after it one position to the left. That’s easy to forget inside a loop:
Tap the line with the bug.
func removeNegatives(_ nums: inout [Int]) {
var i = 0
while i < nums.count {
if nums[i] < 0 { nums.remove(at: i) }
i += 1
}
}fun removeNegatives(nums: MutableList<Int>) {
var i = 0
while (i < nums.size) {
if (nums[i] < 0) nums.removeAt(i)
i++
}
}void removeNegatives(List<Integer> nums) {
int i = 0;
while (i < nums.size()) {
if (nums.get(i) < 0) nums.remove(i);
i++;
}
}function removeNegatives(nums: number[]): void {
let i = 0;
while (i < nums.length) {
if (nums[i] < 0) nums.splice(i, 1);
i++;
}
}Hint: Try [-1, -2, 3]. After -1 is removed at index 0, which number is now at index 0, and what is i?
After removing the element at i, the next element slides into position i. Then i += 1 steps past it without checking it. With [-1, -2, 3], -1 is removed, -2 moves to index 0, i becomes 1, and -2 survives.
The quick fix is to advance i only when nothing was removed. The better fix avoids shifting altogether: keep the elements you want and build the result once, in O(n) instead of O(n²):
nums.removeAll { $0 < 0 } // one pass, no repeated shiftingnums.removeAll { it < 0 } // one pass, no repeated shiftingnums.removeIf(x -> x < 0); // one pass, no repeated shiftingconst kept = nums.filter((x) => x >= 0); // builds a new array in one passPredict the output
What does this print, and how much work does it do for a long array?
var result: [Int] = []
for x in [1, 2, 3] {
result.insert(x, at: 0)
}
print(result)val result = mutableListOf<Int>()
for (x in listOf(1, 2, 3)) {
result.add(0, x)
}
println(result)List<Integer> result = new ArrayList<>();
for (int x : List.of(1, 2, 3)) {
result.add(0, x);
}
System.out.println(result);const result: number[] = [];
for (const x of [1, 2, 3]) {
result.unshift(x);
}
console.log(result);Each number is inserted at the front, so the last one ends up first: [3, 2, 1]. Every insertion at index 0 shifts all the numbers already there, so n insertions cost 0 + 1 + 2 + … + (n − 1) moves, which is O(n²). To build a reversed array, append in order and reverse once at the end (O(n)), or loop backwards.
Rotate Array
Rotate an array to the right by k steps, in place (no second array), so each element moves k positions to the right and the ones that fall off the end wrap around to the front.
nums = [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]
nums = [-1, -100, 3, 99], k = 2 → [3, 99, -1, -100]›
Rotating by k is the same as rotating by k % n: rotating a 7-element array by 7 changes nothing. Do that first, so k is smaller than n.
›
Reverse the whole array: [7, 6, 5, 4, 3, 2, 1]. The last k elements are now at the front, but backwards. What happens if you reverse the first k elements, and then the rest, separately?
SolutionTry it yourself firstTime O(n)Space O(1)
Three reversals: the whole array, then the first k elements, then the remaining n − k. Each element is moved at most twice.
func rotate(_ nums: inout [Int], _ k: Int) {
let n = nums.count
guard n > 0 else { return }
let k = k % n
nums.reverse() // [7, 6, 5, 4, 3, 2, 1]
nums[0..<k].reverse() // [5, 6, 7, 4, 3, 2, 1]
nums[k..<n].reverse() // [5, 6, 7, 1, 2, 3, 4]
}fun rotate(nums: IntArray, k: Int) {
val n = nums.size
if (n == 0) return
val shift = k % n
nums.reverse() // [7, 6, 5, 4, 3, 2, 1]
nums.reverse(0, shift) // [5, 6, 7, 4, 3, 2, 1]
nums.reverse(shift, n) // [5, 6, 7, 1, 2, 3, 4]
}void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0) return;
k %= n;
reverse(nums, 0, n - 1); // [7, 6, 5, 4, 3, 2, 1]
reverse(nums, 0, k - 1); // [5, 6, 7, 4, 3, 2, 1]
reverse(nums, k, n - 1); // [5, 6, 7, 1, 2, 3, 4]
}
void reverse(int[] nums, int left, int right) {
while (left < right) {
int tmp = nums[left];
nums[left++] = nums[right];
nums[right--] = tmp;
}
}function rotate(nums: number[], k: number): void {
const n = nums.length;
if (n === 0) return;
k %= n;
reverse(nums, 0, n - 1); // [7, 6, 5, 4, 3, 2, 1]
reverse(nums, 0, k - 1); // [5, 6, 7, 4, 3, 2, 1]
reverse(nums, k, n - 1); // [5, 6, 7, 1, 2, 3, 4]
}
function reverse(nums: number[], left: number, right: number): void {
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
}A version with k calls to “remove the last element and insert it at the front” also works, but each insert at index 0 is O(n), so it’s O(n · k). The reversal trick is the kind of idea worth remembering: it shows up again in “reverse the words in a sentence”.
Hidden shifts and copies
Predict the output
A worker processes a queue of 100,000 jobs by repeatedly taking the first element and removing it from an array-backed list. Roughly how many element moves does that cost in total?
Array.removeFirst() is O(n): every remaining element shifts. Summed over the queue, that's about n²/2 = 5 × 10⁹ moves. Use a read index into the array, ArraySlice (popFirst() on a slice just moves its start), or Deque from swift-collections.
ArrayList.removeAt(0) shifts every remaining element: about n²/2 = 5 × 10⁹ moves in total. Use ArrayDeque (Kotlin's or Java's), whose removeFirst() is O(1), or keep a read index.
ArrayList.remove(0) shifts the rest of the backing array with System.arraycopy: about n²/2 = 5 × 10⁹ moves in total. Use ArrayDeque.poll(), which is O(1), or keep a read index.
By the language spec, shift() moves every remaining element, so the total is about n²/2 = 5 × 10⁹. Engines sometimes optimize small arrays, but you can't rely on that for large ones. Keep a read index (let head = 0; const job = jobs[head++]) or use a real queue structure.
Value semantics and slices
Swift
Swift arrays are value types with copy-on-write: passing one around is O(1), but the first mutation of a shared buffer copies it, O(n). A helper that takes [Int] and mutates a local var copy inside a loop can turn O(n) into O(n²). Use inout, or make sure the buffer is uniquely referenced. nums[a..<b] is an ArraySlice sharing storage (O(1)); Array(slice) copies.
Kotlin
subList(a, b) is a view (O(1)) that breaks if the original list is structurally modified; slice(a until b) and copyOfRange copy (O(k)). toList() and sorted() always allocate.
Java
subList is a view, O(1), and throws ConcurrentModificationException after a structural change to the parent. Arrays.copyOfRange and new ArrayList<>(list) copy. List.of and toList() from streams are unmodifiable.
TypeScript
slice and spread ([...a]) copy in O(k). splice mutates and shifts in O(n). Arrays with holes or mixed element types can fall out of the engine’s fast mode; keep them dense and of one type in hot code.
- Contiguous growable arrays: O(1) index, amortized O(1) append, O(n) for anything that shifts.
contains/indexOfare O(n). - Removing while iterating forward skips the next element; prefer
removeAll/removeIf/filter, or a read/write pointer pass. - Front removal in a loop is O(n²): use a deque or a read index.
| Swift | Kotlin | Java | TypeScript | |
|---|---|---|---|---|
| O(n) front removal | removeFirst() | removeAt(0) | remove(0) | shift() |
| O(1) queue | Deque (swift-collections), slice + popFirst | ArrayDeque | ArrayDeque | read index |
| View, not copy | ArraySlice | subList | subList | none (slice copies) |
Swift
- Copy-on-write: mutating a shared array copies it once, O(n). Use
inoutin helpers.
Check this part
Which operation on an array of a million numbers is slowest?
A loop removes the element at index i and then always does i += 1. What goes wrong?
You process a 100k-element queue with
Array.removeFirst(). Total cost?You process a 100k-element queue withArrayList.removeAt(0). Total cost?You process a 100k-element queue withArrayList.remove(0). Total cost?You process a 100k-element queue withshift(). Total cost?Why is appending to a dynamic array O(1) only on average?