Arrays & 2-D Arrays (Review)

02Mental model

Picture a row of numbered lockers in a corridor. Every locker is the same size and they sit right next to each other. If locker 0 is at the start of the corridor and each is 4 steps wide, you can walk straight to locker 7: it’s 28 steps away. You never open lockers 0 to 6 on the way.

That is an array: same-type items stored contiguously (side by side) in memory.

Why access is instant

The compiler knows three things: the base address (where a[0] lives), the size of one item, and the index. So

address of a[i] = base + i × sizeof(type)

One multiplication and one addition, for any i: O(1) random access.

The price you pay

Fixed size: int a[100] is static. Need 101? Make a new array and copy.
Insert / delete in the middle is O(n): every item after the gap must shift.
No bounds checking: a[100] on a 100-item array compiles and runs, but reads or overwrites whatever is next in memory.

2-D arrays

A matrix int m[R][C] looks like a grid, but memory is one long line. C++ stores it row by row (row-major):

address of m[i][j] = base + (i × C + j) × sizeof(type)

So looping i (rows) outside and j (columns) inside walks memory in order. That is the natural and fastest way.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Read different indexes, including one that is out of range.

Loading visualizer…

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

1-D and 2-D arrays29 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

int main() {
    // 1-D array: contiguous memory, index i is at base + i * sizeof(int)
    int a[5] = {12, 7, 31, 4, 19};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "a[3] = " << a[3] << "\n";
    cout << "elements are " << sizeof(int) << " bytes apart: "
         << (&a[1] - &a[0]) * sizeof(int) << "\n";

    int sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    cout << "sum = " << sum << "\n";

    // 2-D array: stored row by row (row-major)
    const int R = 3, C = 4;
    int m[R][C];
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            m[i][j] = i * C + j + 1;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << m[i][j] << "\t";
        cout << "\n";
    }
    // m[1][2] is element number 1*C + 2 = 6 in memory
    cout << "m[1][2] = " << m[1][2] << ", offset = " << (&m[1][2] - &m[0][0]) << "\n";
}

Expected output

a[3] = 4
elements are 4 bytes apart: 4
sum = 73
1	2	3	4	
5	6	7	8	
9	10	11	12	
m[1][2] = 7, offset = 6

05Complexity

Access a[i]	O(1)
Search (unsorted)	O(n)
Insert / delete at position i	O(n): shift items
Insert / delete at the end	O(1) if there is space
Traverse an R × C matrix	O(R·C)
Extra space	O(n) for n items

Address formula (row-major): &m[i][j] = base + (i × COLS + j) × sizeof(type).

06Watch

Introduction to data structures

mycodeschool · 6:33

Why this one: Uses the array as its first example and explains contiguous memory.

Watched

Data Structures: Full Course Using C and C++

freeCodeCamp.org · 9h 46m

Why this one: Full course backup. Skim the array and memory parts if you need more practice with C/C++ arrays.

Watched

Original class slides (Python, by the course's lecture authors):Basic Data Structures

07Exam lens

Likely questions

An int array starts at address 1000 and sizeof(int) = 4. What is the address of a[7]?
A float m[5][8] starts at 2000 (sizeof(float) = 4). Find the address of m[3][6] in row-major order.
Why is accessing a[i] O(1) but inserting at the front O(n)?
Write a function to find the sum of each row of a 2-D array.

Common mistakes

Using 1-based indexes. C++ arrays start at 0, so the last valid index is n − 1.
Writing a[n] (out of bounds). C++ does not check, so it silently corrupts memory.
Using sizeof(a)/sizeof(a[0]) inside a function. There, a is a pointer, so the trick gives the wrong size. Pass n instead.
Mixing up rows and columns in the address formula (multiply the row index by the number of COLUMNS).

08Quick check

1.int a[10] starts at address 500 and sizeof(int) = 4. Where is a[6]?
2.In int m[3][4], how many elements come before m[2][1] in memory (row-major)?
3.Why is reading a[i] constant time?
4.What does this print?
```
int a[4] = {5, 2, 8};
cout << a[3];
```

09Practice

🟢 Trace by hand

int m[4][5] starts at address 3000 with 4-byte ints. Compute the address of m[2][3] and of m[3][4].

Show answer

m[2][3]: offset = 2 × 5 + 3 = 13, address = 3000 + 13 × 4 = 3052
m[3][4]: offset = 3 × 5 + 4 = 19, address = 3000 + 19 × 4 = 3076 (the last element)

🟡 Implement it

Write void transpose(int a[3][3]) that swaps rows and columns in place, and a main() that prints the matrix before and after.

Hint

Only swap the upper triangle, a[i][j] with a[j][i] for j > i. Otherwise you swap everything twice and end up back where you started.

Solution

void transpose(int a[3][3]) {
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 3; j++)
            swap(a[i][j], a[j][i]);
}

🔴 Solve problems

Running Sum of 1d Array easyleetcode.com
Hint
Each output is the previous output plus the current item. One loop, O(n).
Richest Customer Wealth easyleetcode.com
Hint
Sum each row of the 2-D array, keep the maximum.
Matrix Diagonal Sum easyleetcode.com
Hint
Primary diagonal is m[i][i], the other is m[i][n-1-i]. Don't count the centre twice when n is odd.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can compute the address of a[i] and m[i][j] by hand.
I can explain why array access is O(1) and insertion is O(n).
I can loop over a 2-D array row by row.
I know why out-of-bounds access is dangerous in C++.

0/4 ticked

My notes