Arrays

A numbered row of boxes in memory

When you write new int[6] in Java, the runtime reserves one contiguous block of memory. Six int-sized slots, physically next to each other. Contiguous is the magic word. Because slot sizes are identical and the slots are adjacent, the computer can compute the exact address of any element with one multiplication: start address plus index times slot size. No searching, no walking, just arithmetic.

That is why reading or writing nums[i] is O(1), constant time, whether the array holds ten elements or ten million. The index tells the computer exactly where to look. Indexes start at 0, so an array of length n has valid indexes 0 through n - 1; step outside that range and Java throws an ArrayIndexOutOfBoundsException rather than letting you read a stranger's mailbox.

int[] scores = new int[6];
scores[0] = 91;
scores[5] = 78;

int last = scores[scores.length - 1];

int[] primes = {2, 3, 5, 7, 11, 13};
System.out.println(primes[3]);

What arrays do cheaply, and what costs O(n)

Access by index is O(1). Updating an element in place is O(1). Scanning the whole array (to sum it, find the max, or search for a value) is O(n), because you touch each element once. So far, so intuitive.

The expensive operations are the ones that fight the contiguous layout. Inserting a value into the middle of a full row means shifting every element after it one slot to the right to make room: O(n) in the worst case. Deleting from the middle means shifting everything after it left: also O(n). And a plain Java array cannot grow at all. Its length is fixed at creation. To "grow" one, you allocate a bigger array and copy everything over, which is O(n). The rule of thumb: arrays are brilliant when you know the size up front and mostly read by index, and clumsy when data constantly enters and leaves the middle.

int[] insertAt(int[] arr, int index, int value) {
    int[] bigger = new int[arr.length + 1];
    for (int i = 0; i < index; i++) {
        bigger[i] = arr[i];
    }
    bigger[index] = value;
    for (int i = index; i < arr.length; i++) {
        bigger[i + 1] = arr[i];
    }
    return bigger;
}

ArrayList: the array that grows itself

Java's ArrayList is not a different data structure. It is a plain array wearing a convenience jacket. Internally it keeps an array with some spare capacity. When you call add and there is room, the element drops into the next free slot in O(1). When the internal array fills up, ArrayList allocates a new array roughly 1.5 times larger and copies everything across.

That occasional copy is O(n), but it happens so rarely that the average cost of add stays O(1). This averaged accounting is called amortized O(1), and it is worth knowing the term because interviewers use it. Everything else carries over from raw arrays: get(i) is O(1), and add or remove in the middle is O(n) because of shifting. Use int[] when the size is fixed; use ArrayList when it is not.

The loop patterns interviews are built on

Nearly every beginner array problem is a variation of one pass with a little state. Finding the maximum: keep a best-so-far variable and update it as you scan. Reversing in place: one pointer at each end, swap, and walk them toward the middle. Counting or summing: an accumulator updated per element. Each of these is O(n) time and O(1) extra space, and saying so out loud is part of the answer.

Get comfortable with these single-pass patterns, because the classic interview techniques (two pointers, sliding window, prefix sums) are just disciplined ways of scanning an array without redundant work. Before those, though, meet the array's most famous special case: the string, an array of characters with some Java-specific rules of its own.

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

Frequently asked