Arrays Basics

The array is the data structure every other one is compared against, because it's the closest thing to "raw memory" that Java exposes to you. Understanding exactly why array operations cost what they cost — rather than just memorizing "indexing is fast" — is what lets you reason correctly about trickier structures later.

Fixed-Size Arrays in Java

A Java array is a contiguous block of memory of a fixed size, decided at creation time and never resized afterward. Declaring int[] arr gives you a block that holds primitive int values directly (not boxed objects), which is part of why arrays are memory-efficient.

int[] fixed = new int[5];       // 5 ints, all initialized to 0
int[] literal = { 10, 20, 30 }; // size fixed at 3, cannot grow
fixed[2] = 42;                    // direct write
int value = fixed[2];             // direct read

Time complexity: O(1) per read or write — the JVM computes the target address as base + index * elementSize directly, no scanning. Space complexity: O(n) for an array of n elements — it's the size of the data itself, not extra overhead.

Why Indexing Is O(1) but Insertion/Deletion Is O(n)

Because array elements sit in contiguous memory, random access by index is O(1) — the address is a direct calculation. But inserting or deleting in the middle means every element after that position has to physically shift to keep the array contiguous, which is an O(n) operation in the worst case (inserting/deleting near the front).

// Insert `value` at `index`, shifting everything after it one slot right.
// Caller must ensure arr has a free trailing slot (arr.length > count).
public void insertAt(int[] arr, int count, int index, int value) {
    for (int i = count; i > index; i--) {
        arr[i] = arr[i - 1]; // shift right to make a gap
    }
    arr[index] = value;
}

Time complexity: O(n) — inserting at index 0 shifts up to n elements; inserting at the end is O(1), but the general case (and the worst case interviewers grade) is O(n). Space complexity: O(1) — the shifting happens in place.

2D Arrays

Java represents a 2D array as an array of arrays (rows), which is common for grid problems (matrix traversal, islands, dynamic programming tables).

int[][] grid = new int[3][4]; // 3 rows, 4 columns, all zeros
grid[1][2] = 9;         // row 1, column 2

for (int row = 0; row < grid.length; row++) {
    for (int col = 0; col < grid[row].length; col++) {
        System.out.print(grid[row][col] + " ");
    }
}

Time complexity: O(rows × cols) to visit every cell once — commonly written O(n × m), or O(n²) when the grid is square. Space complexity: O(rows × cols) for the grid storage itself.

Worked Example: Reversing an Array In Place (Two Pointers)

A classic warm-up that shows the two-pointer pattern in its simplest form: one pointer starts at each end, they swap and walk toward each other until they meet.

public void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

Time complexity: O(n) — each pointer traverses about half the array, so total swaps are n/2, which is still O(n). Space complexity: O(1) — the reversal happens in place using one temporary variable, no auxiliary array.

Why ArrayList Exists (Dynamic Resizing Tradeoff)

A raw array's fixed size is often exactly the problem: you frequently don't know the final count ahead of time. ArrayList<T> wraps an internal array and automatically allocates a larger one (typically 1.5× the old capacity) and copies everything over when it runs out of room.

List<Integer> list = new ArrayList<>();
list.add(10); // amortized O(1)
list.add(20); // amortized O(1)
int first = list.get(0); // O(1), same random-access guarantee as an array

Time complexity: add() is O(1) amortized — most calls are O(1), but occasionally a call triggers a full O(n) resize-and-copy; averaged over many calls this comes out to O(1) each. get(index) stays O(1), same as a raw array. Space complexity: O(n), plus some unused trailing capacity the list keeps for future growth — the tradeoff for not having to know the size up front. Also worth remembering: ArrayList<Integer> stores boxed Integer objects, not primitive ints, which costs extra memory and autoboxing overhead compared to a raw int[].