Array Fundamentals and Traversal

Almost every coding-interview problem starts life as an array problem, and the first thing interviewers judge is whether you understand why arrays are fast. An array stores elements in one contiguous block of memory, so the address of index i is base + i × elementSize — a single arithmetic step. That is what gives you O(1) random access, and it is the property every array trick ultimately exploits.

The core idea

Contiguity buys constant-time indexing but costs you at the edges: inserting or deleting in the middle forces every later element to shift. A dynamic array (Java ArrayList, C++ vector, Python list) hides resizing behind amortized O(1) append — it doubles capacity, so the occasional O(n) copy averages out.

Operation	Time	Note
Access by index	O(1)	base + i × size
Search (unsorted)	O(n)	linear scan
Search (sorted)	O(log n)	binary search
Insert/delete at end	O(1) amortized	dynamic array
Insert/delete at middle	O(n)	shift elements
Space	O(n)	contiguous block

Exam Tricks & Tips

• 🎯 State "O(1) random access, O(n) middle insert/delete" out loud — interviewers listen for it.
• 🎯 Append is amortized O(1), not worst-case O(1); say "amortized" to sound precise.
• 🎯 For "find something" in an unsorted array, a single pass with a running variable beats sorting first.
• 🎯 Iterate by index when you need neighbours (i-1, i+1) or must modify in place; use for-each only for read-only scans.
• 🎯 0-based indexing: the last valid index is n-1 — the number-one source of off-by-one bugs.
• ❌ Common mistake: assuming insertion anywhere is O(1) — only the end of a dynamic array is.

Expected pattern

Warm-up array questions test clean single-pass traversal, correct boundary handling, and in-place updates without an extra array. Expect "traverse and transform", "find max/second-max", or "count elements meeting a condition" as the opener before a harder follow-up.

Quick recap

Arrays = contiguous memory → O(1) access, O(n) middle insert/delete, amortized O(1) append. Master clean index-based traversal and boundary handling; they underpin the two-pointer, sliding-window, and prefix-sum patterns that follow.

Cover the answer, recall, then check. 11 cards on array fundamentals and traversal.

Q1. Why is array access O(1)?
A1. Contiguous memory: address of index i = base + i × elementSize, one arithmetic step regardless of i.

Q2. Time to insert/delete in the middle of an array?
A2. O(n) — every element after the position must shift by one.

Q3. What does "amortized O(1)" append mean?
A3. A dynamic array doubles capacity on overflow; the rare O(n) copy is spread over many O(1) appends, averaging O(1).

Q4. Search cost in an unsorted vs sorted array?
A4. Unsorted: O(n) linear scan. Sorted: O(log n) binary search.

Q5. Last valid index of an array of size n?
A5. n-1 (0-based indexing).

Q6. Space complexity of an array of n elements?
A6. O(n) — one contiguous block.

Q7. When iterate by index vs for-each?
A7. By index when you need neighbours or must modify in place; for-each for read-only scans.

Q8. Find the second-largest element — cost?
A8. O(n) with two running variables (largest, secondLargest); no sort needed.

Q9. Why do arrays beat linked lists for cache performance?
A9. Contiguity → sequential access hits the CPU cache (spatial locality); linked-list nodes are scattered.

Q10. Cost to reverse an array in place?
A10. O(n) time, O(1) space — swap i with n-1-i for i < n/2.

Q11. Biggest off-by-one trap in traversal?
A11. Looping to <= n instead of < n, or reading arr[i+1] on the last index without a bound check.

The array is the first data structure every interviewer assumes you know cold, and it silently underpins strings, matrices, heaps and hash buckets. Understanding why an array is fast is the difference between guessing complexities and stating them with confidence.

Core idea: an array stores elements in a single contiguous block of memory. Because every element is the same size, the address of index i is just base + i × size. That one multiplication is why random access is O(1) — the machine never "walks" to the element, it computes where it lives.

How it works

Beginner — layout and access

A zero-indexed array a of length n occupies slots a[0] … a[n-1]. Reading or writing a[i] is O(1). A full traversal touches each element once, so it is O(n) time, O(1) extra space.

for i in 0..n-1:
    process(a[i])

Intermediate — the cost of insertion and deletion

The contiguity that makes access cheap makes structural edits expensive. Inserting at the front forces every later element to shift right — O(n). Deleting from the middle shifts everything after it left — O(n). Only appending at the end of a dynamic array is cheap.

Dynamic arrays (Java ArrayList, C++ vector, Python list) grow by doubling capacity when full. Copying on a resize is O(n), but because it happens rarely, appends are amortised O(1). Doubling gives a geometric series: n appends cost about 2n copies total.

Advanced — cache locality

Contiguous storage means a traversal reads memory the CPU has already prefetched into cache. This is why array traversal often beats a linked list of the same length in practice even when both are O(n): the constant factor is smaller.

Worked example

What is the amortised cost of appending N elements to an empty dynamic array that doubles?
Resizes happen at sizes 1, 2, 4, …, N, copying 1 + 2 + 4 + … + N ≈ 2N elements total. Add N cheap writes: total ≈ 3N operations over N appends → O(1) amortised per append. The trap answer "O(n) because resizing copies" ignores how rarely it happens.

When to use it

Reach for an array when you need indexed access, a fixed or append-only collection, or the input is already a list. Nearly every two-pointer, sliding-window, prefix-sum and sorting technique operates on arrays. Avoid arrays when you need frequent front/middle insertions — a linked list or deque fits better.

Tricks & gotchas

• Precompute the length once; re-reading len(a) in a hot loop is a common micro-slip.
• Off-by-one errors cluster at a[n] (out of bounds) and empty arrays (n == 0).
• Mnemonic: "Access cheap, shift dear."

Key complexities

• Access/update by index: O(1); search unsorted O(n); sorted (binary search) O(log n).
• Insert/delete at end (dynamic array, amortised): O(1); at arbitrary index: O(n) shifting.
• Full traversal: O(n) time, O(1) extra space.
• Address of A[i]: base + i·(element size) (0-based).
• Dynamic array doubling ⇒ amortised O(1) append (≤ 2n copies over n inserts).

Usage: reach for arrays when random access dominates; avoid mid-array inserts.

Worked Example

Problem: Trace the output of this code that sums the elements at even indices.

arr = [3, 1, 4, 1, 5]
total = 0
for i from 0 to length(arr)-1:
    if i % 2 == 0:
        total = total + arr[i]
print(total)

Solution: Arrays are 0-indexed, so index 0 is the first element. Walk through each index:

i	arr[i]	i even?	total
0	3	yes	3
1	1	no	3
2	4	yes	7
3	1	no	7
4	5	yes	12

Only indices 0, 2, 4 contribute: 3 + 4 + 5 = 12.

The loop visits every element once, so the traversal is O(n) time and O(1) extra space.

Answer: It prints 12.