Arrays

Overview

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together, making it easy to calculate the position of each element by simply adding an offset to a base value (the memory address of the first element).

Arrays are used extensively in algorithm problems and system design. Understanding their performance characteristics is essential for writing efficient code.

Time Complexity

Space complexity: O(n) — proportional to the number of elements stored.

Core Patterns

Two Pointer

Use two pointers moving toward each other (or in the same direction) to reduce O(n²) solutions to O(n).

# Check if array has a pair summing to target
def two_sum_sorted(arr: list, target: int) -> bool:
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return True
        elif current < target:
            left += 1   # need bigger sum
        else:
            right -= 1  # need smaller sum

    return False

# Time: O(n)  |  Space: O(1)

Sliding Window

Maintain a window of elements and slide it across the array to avoid recomputing from scratch on each step.

# Maximum sum subarray of size k
def max_subarray_sum(arr: list, k: int) -> int:
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # slide
        max_sum = max(max_sum, window_sum)

    return max_sum

# Time: O(n)  |  Space: O(1)

Prefix Sum

Precompute cumulative sums to answer range-sum queries in O(1) after O(n) preprocessing.

# Build prefix sums, then query any range in O(1)
def build_prefix(arr: list) -> list:
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i + 1] = prefix[i] + v
    return prefix

def range_sum(prefix: list, l: int, r: int) -> int:
    return prefix[r + 1] - prefix[l]  # O(1)

Common Interview Problems

• Two Sum — find pair summing to target (use HashMap for O(n))
• Best Time to Buy/Sell Stock — single pass, track min price seen so far
• Maximum Subarray — Kadane's algorithm, O(n) dynamic programming
• Rotate Array — reverse trick: O(n) time, O(1) space
• Product of Array Except Self — left/right prefix products, no division
• Container With Most Water — two-pointer, greedy shrink of wider side
• Trapping Rain Water — two-pointer or prefix max arrays

Memory Layout

Arrays store elements in contiguous memory blocks. This enables cache-friendly access patterns — the CPU prefetcher can anticipate sequential reads, making array iteration significantly faster than linked lists in practice, even though both are theoretically O(n).

/* int arr[4] — stored at base address 0x1000 */
arr[0]  →  address 0x1000  (4 bytes)
arr[1]  →  address 0x1004  (4 bytes)
arr[2]  →  address 0x1008  (4 bytes)
arr[3]  →  address 0x100C  (4 bytes)

/* element address = base + (index × element_size) */
addr(arr[i]) = 0x1000 + i * sizeof(int)

Dynamic Arrays

Languages like Python (list) and Java (ArrayList) implement dynamic arrays that resize automatically. When capacity is exceeded, a new array of typically 2× the size is allocated and all elements are copied — this resize operation is O(n), but it happens infrequently enough that the amortized cost of append is O(1).

• Python: list — dynamic, mixed types allowed via boxing
• Java: ArrayList<T> — typed, backed by Object array
• JavaScript: Array — sparse, dynamic, can hold any type
• Go: slice — header (ptr, len, cap) over backing array