Array Basics

An array is a sequence of elements laid out by index: position 0, position 1, position 2, and so on. In the ideal machine model used for interviews, those elements occupy consecutive memory slots, so moving from one index to the next means moving by exactly one element size.

This is why arrays are the default structure for ordered data. They do not store links between elements. The index itself is the navigation system, and that makes array operations feel simple until insertion, deletion, or resizing forces many elements to move.

The key formula is address = base + index * elementSize. If the machine knows where the array begins, how large each element is, and which index you want, it can compute the target location directly. It does not need to scan earlier elements.

That direct-address calculation is the reason arr[i] is O(1). It is also why arrays require a fixed element type or fixed-size references: without a predictable element size, the formula would not work cleanly.

Modern CPUs read memory in chunks called cache lines. Because adjacent array elements are near each other, a left-to-right scan often benefits from data that has already been pulled into cache. This is one reason simple array loops can beat pointer-heavy structures even when both have the same big-O complexity.

Interviewers usually do not expect hardware details, but they do expect engineering judgment. When you can solve a problem with a linear scan over an array, it is often both asymptotically good and practically fast.

A matrix is usually discussed as rows and columns. In row-major order, cells from row 0 come first, then row 1, then row 2. The conceptual address for cell row, col is base + (row * columns + col) * elementSize.

This matters for matrix problems because scanning row by row follows the stored order in many languages and in the interview memory model. Java represents int[][] as an array of row arrays, so each row is its own array, but the row-major mental model still explains why nested loops over rows then columns are natural and efficient.