Arrays

An array is a block of memory slots of the same size, laid out back to back, addressed by a starting position plus an offset. That contiguity is the entire reason arrays behave the way they do — every property that seems arbitrary (O(1) access, O(n) insertion, resizing surprises) falls directly out of "the elements are physically next to each other in memory." Interviewers care about arrays first because almost every other structure is compared against them: a hash table trades array-style access for a hash function, a linked list trades array-style contiguity for cheap insertion, and a heap is literally implemented as an array with implicit tree structure. Understanding exactly why an array does what it does — a database's row storage, a video buffer, Python's list, Java's ArrayList — is the baseline every other structure gets measured against.

Deep Dive: Contiguous Memory and Address Arithmetic

def address_of(base, index, elem_size):
    return base + index * elem_size

Every element in an array has the same fixed size (say 8 bytes for a 64-bit integer), and the array is one unbroken run of memory. That means the address of any element is computable directly: address = base_address + index * element_size. No searching, no following pointers — just one multiplication and one addition, both constant-time operations regardless of how big the array is or which index you ask for. That's the entire mechanism behind "array access is O(1)": it's not that the computer is fast, it's that finding the address doesn't require looking at any other element first.

Compare this to a structure where elements are scattered across memory and linked by pointers (a linked list): there's no formula that gets you from "I want index 5" to an address, because the fifth node could be anywhere. You have to start at the head and follow four next pointers to get there, which is O(n) in the worst case. Contiguity is the one property that makes the address formula possible, and it's also the one property a linked list deliberately gives up.

Deep Dive: 2D Arrays and Row-Major Layout

flat_index = row * num_cols + col
address    = base + flat_index * elem_size

A "2D array" is a convenient fiction — underneath, memory is one-dimensional, so a 2D array is stored as a single flat run with a formula that maps (row, col) to a flat position. Row-major order (used by C, C++, Python's NumPy by default, and most languages) lays a matrix out row by row: all of row 0's elements, then all of row 1's, and so on. That's why matrix[1][0] above lands at flat index 4 — it's the start of row 1, which is right after row 0's 4 elements.

This has a real performance consequence, not just a bookkeeping one: iterating a row-major matrix row-by-row visits consecutive memory addresses, which is cache-friendly (the CPU pulls in a chunk of nearby memory on every cache miss, and row-by-row access keeps reusing that chunk). Iterating column-by-column jumps num_cols * elem_size bytes on every step, which can miss the cache almost every time on a large matrix. Same algorithm, same Big-O, genuinely different real-world speed — this is the concrete case where "two O(n) algorithms can have very different real-world speed" actually shows up.

Deep Dive: Why Insertion and Deletion Are O(n) — the Shift

def insert_at(arr, pos, value):
    arr.append(None)
    shifts = 0
    for i in range(len(arr) - 1, pos, -1):
        arr[i] = arr[i - 1]
        shifts += 1
    arr[pos] = value
    return shifts

Contiguity, the same property that makes access O(1), is exactly why insertion in the middle is expensive: there is no gap to drop a new element into. To insert 99 at index 1, every element from index 1 onward has to slide one slot to the right first (9→1, then 8, 2, 5 keep shifting up) to open a hole — that's 4 element moves for a 5-element array, i.e. up to n-1 moves in the worst case (inserting at index 0). Deletion is the mirror image: removing an element leaves a hole, and everything after it has to slide left by one to close the gap, again up to n-1 moves.

The worst case for both is inserting or deleting at index 0 (shift everything — O(n)); the best case is inserting or deleting at the very end, where there's nothing after it to shift, so it's O(1) — you're just writing to (or vacating) the last slot directly. This is why "insert at the end" and "insert somewhere in the middle" have completely different complexity even though they're "the same operation" conceptually: the cost is entirely about how many elements sit after the target position, not about the operation itself.

Deep Dive: Dynamic Arrays and Amortized O(1) Append

def append(self, value):
    if self.size == self.capacity:
        self.capacity *= 2
        new_data = [None] * self.capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
    self.data[self.size] = value
    self.size += 1

A static array has a fixed size decided at creation — appending past that size is simply impossible without a new array. A dynamic array (Python's list, Java's ArrayList, C++'s vector) fakes "growable" by allocating a fixed-size backing array under the hood and, when it fills up, allocating a new array (typically double the size), copying every existing element over, and freeing the old one. That resize is a real O(n) operation — the copy touches every element — so any single append can be expensive.

The reason it's still called "O(1) amortized" (not O(1) worst case) is that expensive resizes get rarer exactly as fast as they get bigger. Doubling means you do a size-1 copy, then a size-2 copy, then size-4, size-8... — a geometric series that sums to roughly 2n for n total appends, so the *average* cost per append stays bounded by a constant even though occasional individual appends cost O(n). The demo confirms this concretely: 17 appends triggered 5 resizes (doubling 1→2→4→8→16→32) totaling 31 element-copies, averaging 1.82 copies per append — bounded, not growing with n. If the array grew by a fixed amount instead of doubling (say +1 each time), you'd get a resize on every single append, making it O(n) per append and O(n²) for n appends total — doubling specifically is what makes the amortized analysis work.

Deep Dive: Cache-Friendliness — Arrays vs Pointer-Chasing

Big-O treats "visit every element" as O(n) whether it's an array or a linked list, but real hardware doesn't treat them the same. A CPU doesn't fetch one byte at a time from RAM — it pulls in a cache line (a chunk of nearby bytes, often 64 bytes) and keeps it close to the core. Scanning an array sequentially means each cache-line fetch serves many subsequent accesses for free, because the next several elements are already sitting in that fetched line. A linked list's nodes are typically scattered wherever the allocator put them, so each next pointer jump is likely to land outside the current cache line, forcing a fresh (slow) memory fetch almost every step.

This doesn't change either structure's Big-O — both are O(n) to traverse — but it's the honest answer to "why do arrays feel faster in practice for sequential access": fewer cache misses, not a different complexity class. This is worth being precise about in an interview: don't claim a specific multiplier ("arrays are 10x faster") without having measured it on the actual hardware and data size in question — the real effect is real but its magnitude depends on element size, list length, and the memory allocator, not a fixed constant.

Key Pointers

• Array access is O(1) because contiguous memory gives a direct address formula: base + index × element_size — no searching required.
• Insertion and deletion in the middle are O(n) because contiguity forces a shift: everything after the target index has to slide to open or close a gap.
• Insertion and deletion at the very end are O(1) — nothing needs to shift because there's nothing after the target position.
• A 2D array is really one flat 1D array underneath; row-major layout maps (row, col) to a flat index via row × num_cols + col.
• Dynamic arrays (Python list, Java ArrayList) resize by allocating a bigger block (typically double) and copying every element over — that single resize is O(n).
• Append on a dynamic array is O(1) amortized, not O(1) worst case — the doubling strategy makes expensive resizes exponentially rarer, so the average cost per append stays constant.
• Arrays tend to be cache-friendlier than pointer-chasing structures because sequential memory access reuses fetched cache lines; this affects real speed, not Big-O class.
• A static array has fixed capacity at creation; a dynamic array simulates growth by resizing its backing static array under the hood.

How It Works

1. To access arr[i]: compute base_address + i * element_size and read directly — no traversal.
2. To insert at position k: make room (grow the backing store if needed), shift every element from the end down to position k one slot to the right, then write the new value at k.
3. To delete at position k: shift every element after k one slot to the left, overwriting the deleted slot, then shrink the logical size by one.
4. To append to a dynamic array: if there's spare capacity, write directly at the next free slot (O(1)); if full, allocate a new backing array (commonly double the capacity), copy every existing element across, free the old array, then write the new element.
5. To access matrix[r][c] in a row-major 2D array: compute the flat index r * num_cols + c, then apply the normal 1D address formula.
6. To reverse an array in place: swap the first and last elements, then the second and second-to-last, moving two pointers toward the middle until they meet or cross.
7. To find the second-largest element in one pass: track the two largest values seen so far, updating both as you scan — no need to sort or make a second pass.

Try It Yourself

Four small demos: address arithmetic, the insert/delete shift cost, a hand-rolled dynamic array tracking real resize and copy counts, and one-pass second-largest plus in-place reversal.

def address_of(base, index, elem_size):
    return base + index * elem_size

base, elem_size = 1000, 8
for i in [0, 1, 2, 5]:
    print(f"address of arr[{i}] = {base} + {i}*{elem_size} = {address_of(base, i, elem_size)}")

# Output:
# address of arr[0] = 1000 + 0*8 = 1000
# address of arr[1] = 1000 + 1*8 = 1008
# address of arr[2] = 1000 + 2*8 = 1016
# address of arr[5] = 1000 + 5*8 = 1040

def insert_at(arr, pos, value):
    arr.append(None)
    shifts = 0
    for i in range(len(arr) - 1, pos, -1):
        arr[i] = arr[i - 1]
        shifts += 1
    arr[pos] = value
    return shifts

arr = [5, 2, 8, 1, 9]
shifts = insert_at(arr, 1, 99)
print("after insert 99 at index 1:", arr, "shifts performed:", shifts)
# after insert 99 at index 1: [5, 99, 2, 8, 1, 9] shifts performed: 4

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity
        self.resizes = 0
        self.total_copies = 0

    def append(self, value):
        if self.size == self.capacity:
            self.capacity *= 2
            new_data = [None] * self.capacity
            for i in range(self.size):
                new_data[i] = self.data[i]
                self.total_copies += 1
            self.data = new_data
            self.resizes += 1
        self.data[self.size] = value
        self.size += 1

d = DynamicArray()
for i in range(17):
    d.append(i)
print(f"after 17 appends: size={d.size}, capacity={d.capacity}, "
      f"resizes={d.resizes}, total element-copies={d.total_copies}")
print(f"average copies per append = {d.total_copies/17:.2f}")

# Output:
# after 17 appends: size=17, capacity=32, resizes=5, total element-copies=31
# average copies per append = 1.82

def second_largest(arr):
    first = second = float("-inf")
    for x in arr:
        if x > first:
            second = first
            first = x
        elif first > x > second:
            second = x
    return second

arr2 = [5, 2, 8, 1, 9, 3]
print(f"arr={arr2} -> second largest = {second_largest(arr2)}")
# arr=[5, 2, 8, 1, 9, 3] -> second largest = 8

Common Mistakes & Interview Traps

• Assuming array insertion is O(1) because access is — access and insertion have completely different cost drivers (address arithmetic vs shifting), and conflating them is one of the most common interview slip-ups.
• Calling dynamic array append "O(1)" without the word "amortized" — a single append that triggers a resize is a genuine O(n) operation; the O(1) claim only holds averaged over many appends.
• Forgetting that insertion/deletion at the *end* is the O(1) special case, not the general case — "arrays are O(n) to insert into" is only true when the position isn't the last one.
• Treating a 2D array's matrix[i][j] access as somehow different in complexity from 1D access — it's still O(1), just with one extra multiplication in the address formula.
• Claiming a specific speed multiplier for cache-friendliness ("arrays are 10x faster than linked lists") without a measurement — the effect is real but its size depends on hardware, element size, and access pattern.
• Off-by-one errors when shifting during insert/delete — shifting in the wrong direction, or starting the shift loop at the wrong end, silently corrupts adjacent elements instead of erroring.

Interview Q&A

Q: Why is array access O(1) but insertion O(n)?

A: Access only needs one computation — base + index * element_size — because contiguous memory makes every element's address directly derivable. Insertion at an arbitrary position has to physically slide every element after that position over by one slot to open a gap, which touches up to n-1 elements in the worst case. Same underlying property (contiguity), opposite consequence for these two operations.

Q: What happens when a dynamic array (like Python's list or Java's ArrayList) runs out of space?

A: It allocates a new, larger backing array — typically double the old capacity — copies every existing element into it, and then proceeds with the append. The old backing array is discarded. This single resizing append is a real O(n) operation because the copy touches every element currently in the array.

Q: Why is that append still called O(1) amortized?

A: Because resizes get exponentially rarer as the array grows — doubling means the total copying work across n appends sums to roughly 2n (a geometric series: 1+2+4+...+n/2 ≈ n), so the *average* cost per append is a small constant even though a handful of individual appends cost O(n). The 17-append demo shows this directly: 5 resizes, 31 total copies, 1.82 copies per append on average — bounded, not growing with n.

Q: How would you find the second-largest element in an array in one pass?

A: Track two running values, the largest seen so far and the second-largest seen so far, updating both in a single scan: if the current element beats the largest, the old largest becomes the new second-largest before updating; if it beats only the second-largest (and isn't equal to the largest), update just that. This is O(n) time and O(1) auxiliary space, versus O(n log n) for sorting first.

Q: Why are arrays generally faster in practice than linked lists for sequential access, even though both can be O(n) to traverse?

A: Big-O counts operations, not cache misses. An array's elements sit in consecutive memory, so scanning it reuses CPU cache lines fetched for earlier elements; a linked list's nodes are usually scattered across memory, so each next jump is likely to miss the cache and trigger a fresh, slower memory fetch. The asymptotic complexity is identical; the constant factor hidden inside that O(n) is not.

Q: What's the time complexity of reversing an array in place?

A: O(n) time and O(1) auxiliary space, using two pointers starting at each end, swapping and moving toward the middle until they meet or cross — that's n/2 swaps for n elements, which is still O(n) after dropping the constant factor. A recursive version would do the same number of swaps but cost O(n) auxiliary space for the call stack instead.

Follow-up: If doubling capacity gives amortized O(1) append, why not just grow by a large fixed amount like +1000 each time instead?

A: A fixed increment still causes a resize every ~1000 appends regardless of current size, so for large n the *number* of resizes stays proportional to n (n/1000 resizes), and each later resize copies a huge, ever-growing array — the total copying work becomes O(n²) for n appends, not O(n). Doubling ties the resize frequency to the current size, which is what keeps the geometric series — and the amortized bound — bounded by O(n) total.

Follow-up: Does shrinking a dynamic array (e.g. after many deletions) need the same doubling trick in reverse?

A: Yes — naively shrinking the backing array back to fit every time you delete causes the same problem in reverse (repeated allocation/copy near a size boundary), and naively never shrinking wastes memory forever. Real implementations typically only shrink when usage drops to roughly a quarter of capacity, halving capacity at that point, which avoids the "thrashing" case of repeatedly growing and shrinking across the same boundary (append, delete, append, delete right at the threshold).

Follow-up: You said row-major access is more cache-friendly — does that mean you should always iterate matrices row by row?

A: For row-major-stored matrices (the default in most languages), yes — row-by-row iteration matches memory order and stays cache-friendly, while column-by-column jumps across rows on every step. Some languages (Fortran, and MATLAB by default) use column-major order instead, in which case the cache-friendly direction flips — the rule isn't "rows are always faster," it's "iterate in the same order the memory is actually laid out."

Trade-offs

Arrays are the wrong choice when a workload does frequent insertions or deletions away from the end — every such operation pays an O(n) shift, and a structure built for cheap mid-sequence mutation (a linked list, or a balanced tree for sorted mutable data) avoids that cost entirely, at the price of losing O(1) indexed access and cache-friendly scanning. Arrays are also a poor fit when the final size is wildly unpredictable and memory is tight, since a dynamic array can hold up to roughly double the elements it needs in unused capacity right after a resize. Use an array (or dynamic array) when access pattern is dominated by index lookups or end-appends and mutation in the middle is rare; reach for a linked structure, deque, or tree when mid-sequence insertion/deletion dominates, and reach for a hash table entirely when lookup needs to be by key rather than by position.

PracticeSolve related problems in the 150 →