Arrays

The array is the most fundamental data structure in computer science, and the one you will reach for first in the majority of interview problems. Its power comes from a single property: contiguous memory allocation. Every element sits next to its neighbor in RAM, and that physical adjacency unlocks constant-time access, predictable cache behavior, and the simplest possible addressing scheme.

Interviewers love array problems because the structure itself is trivial — every candidate knows what an array is — but the patterns built on top of arrays separate strong candidates from average ones. This chapter gives you both the internals and the patterns.

Memory Model: How Arrays Live in RAM

When the JVM allocates an int[] of size 10, it reserves a contiguous block of 40 bytes (plus object header overhead). Element arr[i] lives at memory address base + i * 4. This arithmetic is so simple that the CPU executes it in a single instruction.

The real performance advantage, however, comes from cache locality. Modern CPUs do not fetch individual bytes from main memory. They fetch entire cache lines — typically 64 bytes. When you access arr[0], the CPU loads arr[0] through arr[15] (for an int[]) into L1 cache. By the time your loop reaches arr[1], the data is already waiting in the fastest memory tier.

This means sequential array traversal operates at near-peak memory bandwidth. A loop that sums all elements of a million-element int[] runs 10–50× faster than the equivalent traversal of a linked list with the same elements, because the linked list’s scattered nodes trigger cache misses at nearly every step.

When an interviewer asks you to compare arrays and linked lists, this is the answer they want: not the textbook O(1) vs O(n) access time, but the hardware reality that makes arrays the default choice for sequential processing.

Static vs. Dynamic Arrays

A static array has fixed size, determined at allocation time. Java’s raw arrays (int[], String[]) are static. Once you allocate new int[100], you cannot grow it to 101 elements without creating a new array and copying.

A dynamic array wraps a static array and manages resizing transparently. Java’s ArrayList<T> is the canonical dynamic array. When the internal array fills up, ArrayList allocates a new array (1.5× the old capacity in OpenJDK), copies all elements, and discards the old array.

Growth Factor: 1.5× vs. 2×

The growth factor creates a trade-off:

• 2× growth (used by many C++ std::vector implementations): Wastes up to 50% of allocated memory at any given time, but resizes less frequently.
• 1.5× growth (used by Java’s ArrayList): Wastes at most 33% of memory, but resizes ~1.7× more often for the same final size.

Java’s choice of 1.5× reflects a preference for memory efficiency over raw throughput. In an interview, mentioning this trade-off demonstrates that you think about real-world engineering constraints, not abstract complexity alone.

Implementing a Minimal Dynamic Array

Here is a clean implementation using Java 25 generics and modern idioms:

public class DynamicArray<T> {
    private Object[] data;
    private int size;

    public DynamicArray() {
        this.data = new Object[4];
        this.size = 0;
    }

    public void append(T element) {
        if (size == data.length) {
            resize(data.length + (data.length >> 1)); // 1.5× growth
        }
        data[size++] = element;
    }

    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index %d, Size %d".formatted(index, size));
        }
        return (T) data[index];
    }

    public void set(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index %d, Size %d".formatted(index, size));
        }
        data[index] = element;
    }

    public int size() {
        return size;
    }

    private void resize(int newCapacity) {
        var newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
}

Key design decisions:

• Object[] backing store — Java’s type erasure prevents creating T[] directly. This matches how ArrayList works internally.
• Bit-shift for 1.5× growth — length + (length >> 1) computes length * 1.5 using integer arithmetic, avoiding floating-point.
• Formatted exception messages — Using String.formatted() produces clear error messages during debugging.

Amortized Analysis of Append

The append operation costs O(1) most of the time, but occasionally triggers an O(n) resize. Amortized analysis proves that the average cost across a sequence of operations remains O(1).

The Banker’s Method

Imagine each append call deposits 3 coins into a bank account:

1. 1 coin pays for placing the element into the array.
2. 2 coins are saved for the future resize.

When a resize triggers at capacity n, you need to copy n elements — costing n coins. But over the n/2 appends since the last resize (the array grew from n/2 to n), you saved 2 × n/2 = n coins. The bank balance never goes negative.

Therefore, each append costs 3 coins amortized — a constant. The total cost of n appends is O(n), making the amortized cost per operation O(1).

When an interviewer asks about ArrayList.add() performance, walk through the banker’s method in two or three sentences. It demonstrates understanding that goes beyond memorizing “amortized O(1).”

Interview Pattern: Two Pointers

The two-pointer technique uses two indices that move through the array according to specific rules. It transforms O(n²) brute-force solutions into O(n) single-pass algorithms.

Problem: Remove Duplicates from Sorted Array

Given a sorted integer array, remove duplicates in place and return the new length. The relative order of elements must remain the same.

Example: [1, 1, 2, 3, 3, 4] → [1, 2, 3, 4, _, _], return 4

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;

    int writePointer = 1;

    for (int readPointer = 1; readPointer < nums.length; readPointer++) {
        if (nums[readPointer] != nums[readPointer - 1]) {
            nums[writePointer] = nums[readPointer];
            writePointer++;
        }
    }

    return writePointer;
}

How it works: The readPointer scans every element. The writePointer marks the position where the next unique element should be placed. When readPointer finds a value different from the previous one, it writes that value at writePointer and advances. Elements after writePointer are irrelevant — the caller uses only the first writePointer elements.

Complexity: O(n) time, O(1) space. One pass through the array with no auxiliary storage.

When to Reach for Two Pointers

Use two pointers when the problem involves:

• A sorted array and you need pairs that satisfy a condition (e.g., two-sum in sorted array)
• In-place modification where you need to partition or compact elements
• Converging from both ends toward the center (e.g., container with most water)

Interview Pattern: Prefix Sums

A prefix sum array stores the cumulative sum of elements up to each index. It converts range-sum queries from O(n) to O(1) after an O(n) preprocessing step.

Problem: Subarray Sum Equals K

Given an integer array and a target sum k, find the total number of contiguous subarrays whose elements sum to k.

Example: nums = [1, 2, 3, -1, 1], k = 3 → Output: 3 (subarrays: [1,2], [3], [3,-1,1])

public int subarraySum(int[] nums, int k) {
    // Map from prefix sum to how many times that sum has occurred
    var prefixCounts = new java.util.HashMap<Integer, Integer>();
    prefixCounts.put(0, 1); // Empty prefix has sum 0

    int currentSum = 0;
    int count = 0;

    for (int num : nums) {
        currentSum += num;

        // If (currentSum - k) was seen before, those occurrences mark
        // starting points of subarrays that sum to k
        count += prefixCounts.getOrDefault(currentSum - k, 0);

        prefixCounts.merge(currentSum, 1, Integer::sum);
    }

    return count;
}

The insight: If the prefix sum at index j is S[j] and the prefix sum at index i is S[i], then the subarray sum from i+1 to j is S[j] - S[i]. You need S[j] - S[i] = k, which means you need S[i] = S[j] - k. The hash map tracks how many times each prefix sum has appeared.

Complexity: O(n) time, O(n) space. A single pass with a hash map storing at most n prefix sums.

When to Reach for Prefix Sums

Use prefix sums when the problem involves:

• Sum of elements in a range or subarray
• Counting subarrays with a specific property (sum, XOR, modular condition)
• Converting repeated range queries from O(n) each to O(1) each

Interview Pattern: Kadane’s Algorithm — Maximum Subarray

Given an integer array, find the contiguous subarray with the largest sum.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → Output: 6 (subarray [4, -1, 2, 1])

This is one of the most frequently asked array problems. Kadane’s algorithm solves it in a single pass:

public record SubarrayResult(int maxSum, int start, int end) {}

public SubarrayResult maxSubarray(int[] nums) {
    int currentMax = nums[0];
    int globalMax = nums[0];
    int start = 0;
    int tempStart = 0;
    int end = 0;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > currentMax + nums[i]) {
            // Starting fresh at i beats extending the previous subarray
            currentMax = nums[i];
            tempStart = i;
        } else {
            currentMax = currentMax + nums[i];
        }

        if (currentMax > globalMax) {
            globalMax = currentMax;
            start = tempStart;
            end = i;
        }
    }

    return new SubarrayResult(globalMax, start, end);
}

The decision at each element: Either extend the current subarray to include nums[i], or discard the running subarray and start fresh at nums[i]. You start fresh whenever the running sum has become so negative that adding nums[i] to it produces a value smaller than nums[i] alone.

The Java 25 record elegantly packages the result — sum, start index, and end index — without boilerplate. The caller destructures with pattern matching:

var result = maxSubarray(nums);
switch (result) {
    case SubarrayResult(var sum, var s, var e) ->
        System.out.println("Max sum %d from index %d to %d".formatted(sum, s, e));
}

Complexity: O(n) time, O(1) space. One pass, no auxiliary data structures.

Multi-Dimensional Arrays

Interview problems frequently involve 2D arrays (matrices). Understanding memory layout matters for performance-sensitive code.

Row-Major vs. Column-Major Order

Java stores 2D arrays in row-major order: all elements of row 0, then all elements of row 1, and so on. This means iterating row by row (for row ... for col) yields sequential memory access and good cache performance. Iterating column by column (for col ... for row) jumps across memory and triggers cache misses.

// Cache-friendly: row-major traversal
int sum = 0;
for (int row = 0; row < matrix.length; row++) {
    for (int col = 0; col < matrix[0].length; col++) {
        sum += matrix[row][col];
    }
}

// Cache-unfriendly: column-major traversal
// Same result, but 2-5× slower on large matrices
int sum = 0;
for (int col = 0; col < matrix[0].length; col++) {
    for (int row = 0; row < matrix.length; row++) {
        sum += matrix[row][col];
    }
}

Common Matrix Traversal Patterns

• Spiral order — Traverse from outer boundary inward. Use four boundaries (top, bottom, left, right) and shrink them after each pass.
• Diagonal traversal — Elements on the same diagonal share the property row + col = constant (for one direction) or row - col = constant (for the other).
• Rotate 90° — Transpose the matrix, then reverse each row. In-place, O(n²) time, O(1) space.

Edge Cases That Trip Candidates

Every array problem carries a set of edge cases that interviewers expect you to handle. Train yourself to check these before writing code:

Edge Case	Why It Matters
Empty array (length == 0)	Prevents ArrayIndexOutOfBoundsException on the first access
Single element	Many algorithms have off-by-one errors when n = 1
All identical elements	Tests whether your duplicate-handling logic works
All negative values	Kadane’s algorithm must handle this — the max subarray is the least negative element
Integer overflow	nums[i] + nums[j] can overflow int range; use long arithmetic when sums are involved
Very large arrays (n = 10⁷+)	Signals that O(n log n) or O(n) is required; O(n²) will time out

Walk through at least two edge cases on every problem. Interviewers notice when you test proactively — it signals production-grade engineering discipline.

When to Reach for Arrays in Interviews

Reach for an array-based solution when:

• Random access is needed — Any problem where you need element-by-index lookup.
• The input is already an array — Sorting, searching, partitioning problems.
• Space efficiency matters — Arrays have zero per-element overhead (unlike linked lists with pointer storage).
• Sequential processing dominates — Prefix sums, sliding windows, and scan-based algorithms exploit cache locality.

Think twice about arrays when:

• Frequent insertions/deletions in the middle — Each operation shifts O(n) elements. Linked lists or balanced trees handle this better.
• The size is completely unknown and changes wildly — While dynamic arrays handle growth well, extremely unpredictable sizes can waste memory during over-allocation.

Arrays are the workhorse of algorithm interviews. The patterns in this chapter — two pointers, prefix sums, and Kadane’s algorithm — appear in dozens of variations across LeetCode, HackerRank, and real interview panels. Internalize them until reaching for the right pattern feels automatic. In the next chapter, you move to the other side of the memory layout spectrum: linked lists.