# 1.3 Arrays & 2-D Arrays (Review)

> Arrays store items side by side in memory, which is why reading any index is instant. 2-D arrays are stored row by row.

Chapter: Introduction to Data Structures · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/arrays

## Mental 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.

## C++ code: 1-D and 2-D arrays

```cpp
#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:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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) |

Space: O(n) for n items

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

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): Uses the array as its first example and explains contiguous memory.
- [Data Structures: Full Course Using C and C++](https://youtu.be/B31LgI4Y4DQ) (freeCodeCamp.org): Full course backup. Skim the array and memory parts if you need more practice with C/C++ arrays.

## Exam 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).

## Quick check

1. `int a[10]` starts at address 500 and `sizeof(int)` = 4. Where is `a[6]`?
   A. 506
   B. 520
   C. 524
   D. 530
   Answer: C. 500 + 6 × 4 = 524.

2. In `int m[3][4]`, how many elements come before `m[2][1]` in memory (row-major)?
   A. 3
   B. 7
   C. 9
   D. 6
   Answer: C. 2 × 4 + 1 = 9 elements come before it.

3. Why is reading `a[i]` constant time?
   A. The array is sorted
   B. The address is computed with one multiply and one add
   C. C++ caches arrays
   D. Arrays are dynamic
   Answer: B. Items are contiguous, so the address is base + i × size. No searching is needed.

4. What does this print?

```cpp
int a[4] = {5, 2, 8};
cout << a[3];
```
   A. 8
   B. Garbage
   C. 0
   D. Compile error
   Answer: C. With an initializer list, any missing elements are set to 0.

## Practice

**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]`.

Solution:

- `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.

```cpp
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]);
}
```


**Problems:**

- [Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/) (easy). Hint: Each output is the previous output plus the current item. One loop, O(n).
- [Richest Customer Wealth](https://leetcode.com/problems/richest-customer-wealth/) (easy). Hint: Sum each row of the 2-D array, keep the maximum.
- [Matrix Diagonal Sum](https://leetcode.com/problems/matrix-diagonal-sum/) (easy). 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.

## Mastery checklist

- [ ] 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++.