Index arithmetic

An index is an offset

The first module showed that an array is one block of memory, and that element i lives at base + i × size. That formula is the whole reason arrays are fast: reaching any element is one multiply-add and one load, the same cost for the first element as for the billionth.

It also explains why most languages count from 0. The index is the distance from the start of the block, measured in elements. Element 0 is at distance 0, the base address itself. If indexes started at 1, every access would need a subtraction, base + (i − 1) × size. Edsger Dijkstra wrote a short note in 1982 arguing for 0-based ranges for a related reason: a half-open range such as 0 ≤ i < n contains exactly n elements, and two adjacent ranges such as 0 ≤ i < k and k ≤ i < n share no element and leave no gap. That convention, start included and end excluded, runs through every algorithm in this track.

Bounds

The formula will happily compute an address past the end of the array. What happens next depends on the language.

C and C++ don't check. Reading a[10] from a 10-element array loads whatever bytes lie just past it, and writing there overwrites them. These out-of-bounds accesses are among the most serious bugs in software: the Heartbleed vulnerability in 2014 let attackers read up to 64 KB of a server's memory, including private keys, because a length field was trusted without checking it against the real buffer.

Java, C#, Python, Go and Rust check every index and raise an error instead. The check is one comparison, and compilers remove it when they can prove the index is in range, for example in a loop from 0 to the array's length. Python also accepts negative indexes, counting from the end: a[-1] is a[len(a) - 1].

Two dimensions in one block

Memory is one-dimensional, so a grid has to be laid out as a line. The usual choice, used by C, NumPy and most languages, is row-major order: row 0 from left to right, then row 1, and so on. In the trace above, a 2 × 4 grid becomes 8 consecutive cells, and cell (r, c) is at index:

index = r × cols + c

To skip to row r you pass r complete rows of cols cells, then move c cells along. Going back is a single division: the quotient is the row and the remainder is the column, which is what divmod(6, 4) returns in the trace.

Fortran, MATLAB, Julia and R use column-major order instead, storing each column contiguously, so index = c × rows + r. Neither is better, but loops should walk along the dimension that is contiguous, as the caches lesson showed.

Some languages build grids differently. A Java int[][] and a Python list of lists are arrays of separate row arrays: the outer array holds a reference to each row, and the rows can sit anywhere in memory and even have different lengths. A C array int a[2][4] and a NumPy array are one flat block with the row-major formula built in. The flat layout costs one fewer pointer to follow per access and keeps the whole grid contiguous.

Arithmetic instead of loops

Once a position is a number, many questions about it become arithmetic:

• Neighbors. In a grid stored row by row, the cell to the right of index i is i + 1, the cell to the left is i − 1, and the cells above and below are i − cols and i + cols. You still need to check the edges: i + 1 from the last column wraps onto the next row.
• Wrapping around. (i + 1) % n steps forward and returns to 0 after n − 1. Rotating an array by k places moves the element at i to (i + k) % n. Ring buffers, in the stacks and queues module, are built on this.
• Grouping. Integer division groups consecutive indexes: i // 3 is the same for 0, 1 and 2. In a 9 × 9 Sudoku, r // 3 picks one of three bands of rows and c // 3 one of three stacks of columns, so the box number is (r // 3) × 3 + c // 3. That is the answer to this lesson's opening question: row 4, column 7 is at index 4 × 9 + 7 = 43, in box 1 × 3 + 2 = 5.
• Even and odd, and powers of two. i % 2 alternates, and when n is a power of two, i % n is the same as i & (n − 1), a single AND instruction. Hash tables use exactly that to turn a hash into a slot.

Views without copies

Index arithmetic can also reinterpret data without moving it. NumPy describes each array with strides: how many bytes to step for each dimension. Transposing a matrix just swaps its strides, so the transpose of a million-element array is created instantly and shares the original memory. Slicing every second element doubles the stride. The data stays where it is; only the formula that maps indexes to addresses changes.

The same idea appears in Python's memoryview, in Go slices, which are a pointer, a length and a capacity over a shared array, and in Rust's slices. A view is cheap to create, but it shares memory with the original, so writing through it changes both. The next lesson turns to the one thing index arithmetic can't do: make a block of memory bigger.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Index arithmetic from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

rows, cols = 2, 4
grid = [0] * (rows * cols)
def index(r, c):
    return r * cols + c
grid[index(1, 2)] = 7
r, c = divmod(6, cols)

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.