Arrays

An array is a row of values stored side by side, each at a numbered position called its index. Python calls it a list and JavaScript calls it an array, but the idea is the same. Indexes start at 0, so the first value is at index 0.

Because every slot sits right after the one before, the computer can jump straight to any index. It doesn't need to look at the slots in front of it first.

Measuring speed with Big-O

Interviewers care about how your code slows down as the input grows. Big-O describes that growth, where n is the size of the input:

• O(1) means the work stays the same, however big the input is.
• O(n) means the work grows in step with the input: twice the values, twice the work.
• O(n²) means the work grows with the square: twice the values, four times the work.

Reading by index is O(1). Finding a value without knowing where it is means checking each slot in turn, which is O(n):

The second line searched from the start until it found 23 at index 4. On a list of a million values, that search could take a million steps.

Adding and removing

Adding to the end is quick, because nothing else has to move. Inserting in the middle is slow, because every value after that spot shifts along by one:

Inserting 30 at index 2 moved 40 and 50 one place to the right. On a long array, that shifting is O(n) work. Removing from the middle costs the same, for the same reason.

Access by index

O(1)

Search (unsorted)

O(n)

Insert / delete (middle)

O(n)

Append at end

O(1)

Space

O(n)

Pattern: remember what you've seen

Many array problems ask whether some value appeared earlier. Searching the array each time is O(n) per search. A hash map (a dictionary in Python, a Map or object in JavaScript) answers "have I seen this?" in O(1). When you only need the values themselves, a set does the same job. A set holds each value once, and checking for one is O(1) too:

One pass over the array, with a quick lookup at each step, makes the whole thing O(n). Trading a little extra memory for speed like this is the most common trick in interviews.

Pattern: two pointers

When an array is sorted, you can often work from both ends at once. Keep one index at the start and one at the end, and move them toward each other:

If the total is too small, only moving left up can make it bigger. If it's too big, only moving right down can shrink it. Each step rules out a value for good, so the search takes O(n) steps instead of checking all pairs.

Pattern: sliding window

Some problems ask about a run of neighboring values, like the best sum of 3 in a row. Instead of adding up each run from scratch, keep a window: add the value coming in and take away the one leaving.

Each step does a fixed amount of work, so the whole scan is O(n). The best run is 8, 3 and 4.