Loading TechCookies contentβ¦
Arrays are a contiguous block of memory. That one property gives you O(1) random access by index β the most powerful primitive in algorithm design.
Almost every interview problem reduces to: traverse an array cleverly.
Key properties to memorise:
| Operation | Time | Why |
|---|---|---|
| Access arr[i] | O(1) | Direct memory offset |
| Search (unsorted) | O(n) | May need to check every element |
| Insert at end | O(1) amortised | Append doesn't shift anything |
| Insert at middle | O(n) | Must shift elements right |
| Delete at middle | O(n) | Must shift elements left |
Indices start at 0: the first element is arr[0], the last is arr[arr.length - 1]. The most common beginner bug in all of programming is the off-by-one:
for (let i = 0; i <= arr.length; i++) // β last pass reads arr[arr.length] β undefined!
for (let i = 0; i < arr.length; i++) // β visits exactly indices 0 β¦ length-1
When in doubt, ask: how many times does this loop body run? For an array of length 3 the answer must be exactly 3 β i takes the values 0, 1, 2.
When an array is sorted, you unlock O(log n) search (binary search) and the two-pointer pattern β both are upcoming concepts.