1.1Arrays and address calculation
The idea
An array stores elements in consecutive memory, so the address of any element is computed directly from its index.
Think of it like this: A row of lockers numbered from 0: locker i is exactly i doors from the first.
Why it exists
Address-calculation questions are formula questions: no thinking, just care with the lower bound and row/column order.
How it works
- 1-D: addr = base + (i − lower) × size.
- Row-major 2-D: skip i full rows, then j more elements.
- Column-major: skip j full columns, then i more.
- Triangular matrices store only n(n + 1)/2 cells.
Worked example: A[10][20], 4 bytes each, base 1000, address of A[3][5]
Row-major: 1000 + (3 × 20 + 5) × 4 = 1260. Column-major: 1000 + (5 × 10 + 3) × 4 = 1212.
Now play with it
- →Change the lower bound to 1 and watch both addresses shift.
- →Swap rows and columns to see the two orders disagree.
Row-major: finish a whole row before the next. Change the lower bound to 1 to see why you subtract it.
Check yourself
For int A[5][8] stored row-major from address 100 (4 bytes), A[2][3] is at
Exam notes (the dense version)
In a 1-D array the address of A[i] is base + (i − lower) × size. For a 2-D array stored in row-major order, A[i][j] is at base + ((i − r₀) × columns + (j − c₀)) × size; column-major swaps the roles. Access is O(1); insertion or deletion in the middle is O(n). A triangular matrix needs only n(n + 1)/2 cells.
Previous year questions: Arrays, Stacks, Queues & Linked Lists (14)
PYQs are grouped by topic, so this is the full set for Arrays, Stacks, Queues & Linked Lists; try the ones that match this subtopic. Open all 14 on the topic page.