These are the notes for C++ Coding Questions, episode 19, placement practice for people who finished the SyntaxPilot C++ course. The matrix, numbers in rows and columns, on three of the most asked interview questions: rotating a matrix 90° clockwise in place (why writing straight into the matrix scrambles it, and why a transpose over every cell changes nothing), printing a matrix in spiral order (four walls, and the single-row trap), and searching a matrix whose rows and columns are sorted (why binary search on the cells fails, and the staircase from the top-right corner).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. Not one of today's three bugs gives an error message: they all compile cleanly and print a wrong answer.
Real-life pictures
| In real life | In C++ |
|---|---|
| A cinema hall: seat (row 2, seat 5) | a matrix: a[i][j] is row i, column j |
| You took a photo sideways and tap rotate | rotate the matrix 90° clockwise |
| The photo's top row becomes its right column | row i becomes column n − 1 − i |
| Repainting pixels where they sit paints over pixels you haven't moved yet | writing into the same matrix overwrites unread cells |
| Flip the photo on its diagonal, then mirror it | transpose, then reverse each row |
| A jalebi maker pipes the outside ring first, then the next ring inward | spiral order, clockwise from the outside in |
| The four edges of the tray, moved in after each side | four walls: top, bottom, left, right |
| On a long, thin tray the last ring is a single line | a single row: don't come back the same way |
| A supermarket shelf: prices go up to the right and down the shelves | a matrix with sorted rows and sorted columns |
| Stand at the top-right item: too costly, step left; too cheap, step down | the staircase search, O(n + m) |
A matrix in one minute
A matrix is numbers arranged in rows (across) and columns (down), like the seats of a cinema hall. In C++ the usual way to store one is a vector of vectors:
vector<vector<int>> a(n, vector<int>(m)); // n rows, each a vector of m numbers (all 0)
a[i][j] // row i, column j (both start at 0)
a.size() // n, the number of rows
a[0].size() // m, the number of columns (only if there is a row 0!)
Reading one from input, row by row:
for (auto& row : a) // each row, by reference
for (int& x : row) cin >> x;
- When the number of rows equals the number of columns (n × n) it is a square matrix.
- The diagonal (main diagonal) is the cells where
i == j, from the top-left to the bottom-right. The anti-diagonal is the cells wherei + j == n - 1, from the top-right to the bottom-left. - In place means you change the matrix itself, without making a second matrix: O(1) extra space.
- The cells stored row after row (
a[0][0], a[0][1], …, a[1][0], …) is called row-major order, the "reading order" of a matrix.
col 0 col 1 col 2
row 0 1 2 3 a[0][2] = 3
row 1 4 5 6 diagonal: 1 5 9
row 2 7 8 9 anti-diagonal: 3 5 7
Q1: Rotate an n × n matrix 90° clockwise, in place
Problem. Given n and an n × n matrix, turn it 90° clockwise without using a second matrix.
| Input | Output |
|---|---|
1 2 3 / 4 5 6 / 7 8 9 |
7 4 1 / 8 5 2 / 9 6 3 |
1 … 16 (4 × 4) |
13 9 5 1 / 14 10 6 2 / 15 11 7 3 / 16 12 8 4 |
Think out loud. Like turning a phone photo: the top row becomes the right column. In general, row i becomes column n − 1 − i, so the value at [i][j] moves to [j][n-1-i]. Edge cases: n = 1, an even size (4 × 4, no middle cell), and no second matrix allowed.
The obvious attempt: use the rule directly
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void rotate90(vector<vector<int>>& a) {
int n = a.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[j][n - 1 - i] = a[i][j]; // row i -> column n-1-i
}
int main() {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (auto& row : a)
for (int& x : row) cin >> x;
rotate90(a);
for (auto& row : a) {
for (int x : row) cout << x << " ";
cout << "\n";
}
return 0;
}
Input 3 / 1 2 3 / 4 5 6 / 7 8 9:
7 4 1
2 5 2
1 2 1
The first row is right, but then 2 5 2 and 1 2 1: numbers are copied twice, and 8, 9 and 6 have vanished.
Why it fails: we wrote over cells we hadn't read yet
i = 0, j = 0: a[0][2] = a[0][0] → the 3 in a[0][2] is overwritten by 1
...later, i = 0, j = 2 reads a[0][2]: it is already 1, the 3 is lost
A "move each value to its new place" rule only works if you write into a second matrix, which costs O(n²) extra space. The question says in place.
The trick: two moves that only ever swap.
- Transpose: swap
a[i][j]witha[j][i]. That flips the matrix on its diagonal, so rows become columns. - Reverse every row: mirror it left to right.
Together they are a 90° clockwise turn, and because every step is a swap, nothing is ever lost.
1 2 3 transpose 1 4 7 reverse rows 7 4 1
4 5 6 -----------> 2 5 8 -------------> 8 5 2
7 8 9 3 6 9 9 6 3
Attempt: transpose over every cell, then reverse
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void rotate90(vector<vector<int>>& a) {
int n = a.size();
for (int i = 0; i < n; i++) // 1. transpose
for (int j = 0; j < n; j++)
swap(a[i][j], a[j][i]);
for (auto& row : a) // 2. reverse each row
reverse(row.begin(), row.end());
}
int main() {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (auto& row : a)
for (int& x : row) cin >> x;
rotate90(a);
for (auto& row : a) {
for (int x : row) cout << x << " ";
cout << "\n";
}
return 0;
}
3 2 1
6 5 4
9 8 7
That is not a turn, only a mirror image, as if the transpose never happened.
Why: every pair was swapped twice.
i = 0, j = 1: swap(a[0][1], a[1][0]) → swapped
i = 1, j = 0: swap(a[1][0], a[0][1]) → swapped BACK
The loop visits every pair from both sides, and two swaps are no swap at all. The transpose undid itself, and only the "reverse each row" part did anything.
Fix: only the cells above the diagonal, j = i + 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void rotate90(vector<vector<int>>& a) {
int n = a.size();
for (int i = 0; i < n; i++) // 1. transpose
for (int j = i + 1; j < n; j++)
swap(a[i][j], a[j][i]);
for (auto& row : a) // 2. reverse each row
reverse(row.begin(), row.end());
}
int main() {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (auto& row : a)
for (int& x : row) cin >> x;
rotate90(a);
for (auto& row : a) {
for (int x : row) cout << x << " ";
cout << "\n";
}
return 0;
}
Input 3 × 3:
7 4 1
8 5 2
9 6 3
Input 4 / 1 2 3 4 / 5 6 7 8 / 9 10 11 12 / 13 14 15 16:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
And n = 1 (input 1 / 5):
5
Each pair above the diagonal is swapped exactly once; the diagonal cells (i == j) stay where they are, which is correct, because a transpose doesn't move them.
O(n²) time (every cell is touched a couple of times), O(1) extra space: truly in place.
Q2: Print a matrix in spiral order
Problem. Given n, m and an n × m matrix, print every number in spiral order: clockwise, from the outside in.
| Input | Output |
|---|---|
3 × 3: 1 2 3 / 4 5 6 / 7 8 9 |
1 2 3 6 9 8 7 4 5 |
3 × 4: 1 2 3 4 / 5 6 7 8 / 9 10 11 12 |
1 2 3 4 8 12 11 10 9 5 6 7 |
1 × 3: 1 2 3 |
1 2 3 |
Think out loud. Like the jalebi maker: each ring is four sides, right along the top, down the right side, left along the bottom, up the left side. Keep four walls as variables: after the top row, top moves down; after the right column, right moves left; then bottom moves up and left moves right. Edge cases: not square (3 × 4), a single row, a single column.
left right
↓ ↓
top → 1 → 2 → 3 → 4
↓
5 → 6 → 7 8
↑ ↓
bottom → 9 ← 10← 11← 12
The obvious attempt: four sides while the walls haven't crossed
#include <iostream>
#include <vector>
using namespace std;
vector<int> spiral(const vector<vector<int>>& a) {
int top = 0, bottom = a.size() - 1;
int left = 0, right = a[0].size() - 1;
vector<int> out;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) out.push_back(a[top][j]);
top++;
for (int i = top; i <= bottom; i++) out.push_back(a[i][right]);
right--;
for (int j = right; j >= left; j--) out.push_back(a[bottom][j]);
bottom--;
for (int i = bottom; i >= top; i--) out.push_back(a[i][left]);
left++;
}
return out;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
for (int x : spiral(a)) cout << x << " ";
cout << "\n";
return 0;
}
3 × 3:
1 2 3 6 9 8 7 4 5
Correct. Now 3 × 4:
1 2 3 4 8 12 11 10 9 5 6 7 6
5 6 7 and then 6 again: thirteen numbers from a matrix of twelve. And the single row 1 3 / 1 2 3:
1 2 3 2 1
It went along the row and came straight back the same way. A single column (3 1 / 1 / 2 / 3) fails too:
1 2 3 2
Why it fails: the walls crossed in the middle of a ring
1 x 3: right along top: 1 2 3 → top = 1, bottom = 0 (top > bottom: no rows left!)
...but the bottom-row loop still runs on row 0: 2 1
The while only checks the walls at the start of a ring. In a non-square matrix the last ring is a single line, and the walls cross halfway through it. In the 3 × 4 case the last ring is the middle row 5 6 7: after going right along it, top > bottom, but the left-going loop ran on it again and printed 6.
Fix: check the walls again before the last two sides
#include <iostream>
#include <vector>
using namespace std;
vector<int> spiral(const vector<vector<int>>& a) {
int top = 0, bottom = a.size() - 1;
int left = 0, right = a[0].size() - 1;
vector<int> out;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) out.push_back(a[top][j]);
top++;
for (int i = top; i <= bottom; i++) out.push_back(a[i][right]);
right--;
if (top <= bottom) { // a bottom row is left
for (int j = right; j >= left; j--) out.push_back(a[bottom][j]);
bottom--;
}
if (left <= right) { // a left column is left
for (int i = bottom; i >= top; i--) out.push_back(a[i][left]);
left++;
}
}
return out;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
for (int x : spiral(a)) cout << x << " ";
cout << "\n";
return 0;
}
The single row:
1 2 3
3 × 4, twelve numbers, each once:
1 2 3 4 8 12 11 10 9 5 6 7
3 × 3:
1 2 3 6 9 8 7 4 5
The single column (3 1 / 1 / 2 / 3):
1 2 3
And 2 × 2 (1 2 / 3 4):
1 2 4 3
O(n·m) time (every number once), O(1) extra space besides the answer. (a[0].size() assumes at least one row: an empty matrix would be undefined behaviour, so check a.empty() first if that can happen.)
Q3: Search a row- and column-sorted matrix
Problem. Every row is sorted left to right, and every column is sorted top to bottom. Is the number t in the matrix?
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
| t | Output |
|---|---|
| 5 | found |
| 13 | found |
| 15 | not found |
Think out loud. Checking every cell works but is O(n·m). The data is sorted, so we should be able to do better. Edge cases: t smaller than everything, bigger than everything, a matrix that isn't square.
The obvious attempt: binary search on the cells as one long list
Number the cells 0 … n·m − 1 in reading order (row-major). Cell number mid is in row mid / m, column mid % m.
#include <iostream>
#include <vector>
using namespace std;
bool found(const vector<vector<int>>& a, int t) {
int n = a.size(), m = a[0].size();
int lo = 0, hi = n * m - 1; // cells 0 .. n*m-1
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = a[mid / m][mid % m]; // cell -> row, column
if (v == t) return true;
if (v < t) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
int main() {
int n, m, t;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
cin >> t;
cout << (found(a, t) ? "found" : "not found") << "\n";
return 0;
}
Input: the 4 × 4 matrix above, then 5:
not found
Five is right there, in row 1, column 1. On the same matrix it also says not found for 13, while it does find 1 and 17 (the first and last cells).
Why it fails: the cells are NOT sorted in reading order
read row by row: 1 4 7 11 | 2 5 8 12 | 3 6 9 16 | 10 13 14 17
↑ 11 then 2: it goes DOWN
Binary search needs one sorted line. Here only each row and each column is sorted, which is a different promise. (Binary search on the flattened matrix is correct for a different question, where each row starts after the previous row ends, such as 1 3 5 / 7 9 11.)
The shelf trick. Start at the top-right cell:
- bigger than t → everything below it is bigger too: drop this column,
c--; - smaller than t → everything to its left is smaller too: drop this row,
r++.
Every look throws out a whole row or a whole column, so there are at most n + m looks. The path looks like a staircase.
Fix: the staircase from the top-right
#include <iostream>
#include <vector>
using namespace std;
bool found(const vector<vector<int>>& a, int t) {
int r = 0, c = a[0].size() - 1; // start at the top-right
while (r < (int)a.size() && c >= 0) {
if (a[r][c] == t) return true;
if (a[r][c] > t) c--; // the column below is bigger
else r++; // the row to the left is smaller
}
return false;
}
int main() {
int n, m, t;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
cin >> t;
cout << (found(a, t) ? "found" : "not found") << "\n";
return 0;
}
t = 5 (11 too big, left; 7 too big, left; 4 too small, down; 5):
found
t = 13:
found
t = 15 (it walks off the bottom of the matrix):
not found
t = 0 (smaller than everything) and t = 99 (bigger than everything):
not found
not found
A matrix that isn't square, 2 3 / 1 3 5 / 2 4 6, t = 4:
found
O(n + m) time, O(1) space.
Why the top-right corner, and not the top-left?
top-left (1): everything right AND below is bigger → t bigger? both ways go up. Stuck.
top-right (11): left is smaller, below is bigger → one way down, one way up. A choice!
The bottom-left corner works too, for the same reason: up is smaller, right is bigger. The bottom-right does not (both ways go down).
Complexity summary
| Program | Time | Extra space |
|---|---|---|
rotate, write a[j][n-1-i] into the same matrix |
O(n²), wrong | O(1) |
| rotate, into a second matrix | O(n²) | O(n²) |
| rotate, transpose (all j) + reverse | O(n²), only mirrors | O(1) |
rotate, transpose (j = i + 1) + reverse |
O(n²) | O(1) |
| spiral, no inner checks | O(n·m), repeats numbers | O(1) besides the answer |
| spiral, with inner checks | O(n·m) | O(1) besides the answer |
| search, check every cell | O(n·m) | O(1) |
| search, binary search on all cells | O(log(n·m)), wrong | O(1) |
| search, staircase | O(n + m) | O(1) |
On a 1000 × 1000 matrix: checking every cell is a million looks, the staircase at most 2,000.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
a[j][n-1-i] = a[i][j] in place |
no error: 7 4 1 / 2 5 2 / 1 2 1 |
overwrites cells not read yet | transpose + reverse each row |
transpose with j from 0 |
no error: 3 2 1 / 6 5 4 / 9 8 7 (only mirrored) |
every pair swapped twice | j = i + 1 |
| spiral without the inner checks | no error: 1 2 3 2 1, … 5 6 7 6 |
walls cross mid-ring | if (top <= bottom) / if (left <= right) |
| binary search on all cells | no error: not found for 5 |
reading order isn't sorted | staircase from the top-right |
| staircase from the top-left | can't decide which way to go | both ways get bigger | top-right or bottom-left |
vector<vector<int>> a(n); then a[i][j] = … |
warnings, then Segmentation fault |
the rows are empty: undefined behaviour | a(n, vector<int>(m)) |
vector<vector<int>> a(n, m); |
compile error | the second argument must be a row, not a number | a(n, vector<int>(m)) |
a[0].size() on an empty matrix |
undefined behaviour | there is no row 0 | check a.empty() first |
The empty-rows mistake:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 2, m = 3;
vector<vector<int>> a(n); // n empty rows: no columns yet!
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) a[i][j] = i + j;
cout << "done\n";
return 0;
}
g++ warns at compile time:
main.cpp: In function 'int main()':
main.cpp:9:45: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds=]
9 | for (int j = 0; j < m; j++) a[i][j] = i + j;
cc1plus: note: source object is likely at address zero
main.cpp:9:45: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds=]
cc1plus: note: source object is likely at address zero
main.cpp:9:45: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds=]
cc1plus: note: source object is likely at address zero
main.cpp:9:45: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds=]
cc1plus: note: source object is likely at address zero
and the program then crashed with a segmentation fault (exit code 139) without printing done. a(n) makes n empty rows; a[i][j] reads past the end of an empty vector, and [] never checks the size. That is undefined behaviour: a crash here, but it could also silently corrupt memory. a[i].at(j) would throw std::out_of_range instead.
The wrong constructor, vector<vector<int>> a(n, m); on line 7, starts with:
main.cpp: In function 'int main()':
main.cpp:7:31: error: no matching function for call to 'std::vector<std::vector<int> >::vector(int&, int&)'
7 | vector<vector<int>> a(n, m);
(followed by a long list of every vector constructor that didn't match). The fill value of a vector of vectors must itself be a vector: vector<int>(m).
Your turn: count the negatives in a sorted matrix (solution)
Problem. Every row and every column is sorted in decreasing order. Count the negative numbers in O(n + m).
4 3 2 -1
3 2 1 -1 → 8
1 1 -1 -2
-1 -1 -2 -3
Idea. A staircase from the bottom-left. If a[r][c] is negative, then everything to its right in that row is negative too (the row decreases): add m - c and go up a row. If it isn't negative, step right. Each step drops a row or a column.
#include <iostream>
#include <vector>
using namespace std;
int countNegatives(const vector<vector<int>>& a) {
int n = a.size(), m = a[0].size();
int r = n - 1, c = 0, count = 0; // start at the bottom-left
while (r >= 0 && c < m) {
if (a[r][c] < 0) {
count += m - c; // this cell and everything to its right
r--; // go up a row
} else {
c++; // not negative: step right
}
}
return count;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
cout << countNegatives(a) << "\n";
return 0;
}
The example above:
8
No negatives (2 3 / 3 2 1 / 2 1 0):
0
All negative (2 2 / -1 -2 / -3 -4):
4
O(n + m) time, O(1) space.
Practice questions (with solutions)
1. Rotate an n × n matrix 90° anticlockwise, in place.
Solution
Transpose (with j = i + 1), then reverse the order of the rows (instead of each row). Turning a photo left: the top row becomes the left column, read upwards.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void rotateAnti(vector<vector<int>>& a) {
int n = a.size();
for (int i = 0; i < n; i++) // 1. transpose
for (int j = i + 1; j < n; j++)
swap(a[i][j], a[j][i]);
reverse(a.begin(), a.end()); // 2. reverse the ORDER of the rows
}
int main() {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (auto& row : a)
for (int& x : row) cin >> x;
rotateAnti(a);
for (auto& row : a) {
for (int x : row) cout << x << " ";
cout << "\n";
}
return 0;
}
Input 3 / 1 2 3 / 4 5 6 / 7 8 9:
3 6 9
2 5 8
1 4 7
Input 4 × 4 (1 … 16):
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
O(n²) time, O(1) space.
2. Set matrix zeroes, in place: if a cell is 0, make its whole row and whole column 0.
Solution
Zeroing as you go would spread new zeroes everywhere. Instead, use row 0 and column 0 as a notebook: for each 0 at [i][j], mark a[i][0] and a[0][j]. Two flags remember whether row 0 and column 0 had a 0 of their own. Then fill from the notes, and last of all fix row 0 and column 0.
#include <iostream>
#include <vector>
using namespace std;
void setZeroes(vector<vector<int>>& a) {
int n = a.size(), m = a[0].size();
bool row0 = false, col0 = false; // does row 0 / column 0 itself have a 0?
for (int j = 0; j < m; j++) if (a[0][j] == 0) row0 = true;
for (int i = 0; i < n; i++) if (a[i][0] == 0) col0 = true;
for (int i = 1; i < n; i++) // use row 0 and column 0 as notes
for (int j = 1; j < m; j++)
if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
for (int i = 1; i < n; i++) // fill from the notes
for (int j = 1; j < m; j++)
if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
if (row0) for (int j = 0; j < m; j++) a[0][j] = 0;
if (col0) for (int i = 0; i < n; i++) a[i][0] = 0;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
setZeroes(a);
for (auto& row : a) {
for (int x : row) cout << x << " ";
cout << "\n";
}
return 0;
}
Input 3 3 / 1 1 1 / 1 0 1 / 1 1 1:
1 0 1
0 0 0
1 0 1
Input 3 4 / 0 1 2 0 / 3 4 5 2 / 1 3 1 5:
0 0 0 0
0 4 5 0
0 3 1 0
O(n·m) time, O(1) extra space. (With two extra arrays, rowZero[n] and colZero[m], it is simpler and O(n + m) space.)
3. Print a matrix diagonal by diagonal.
Solution
All cells on one diagonal (going from top-right to bottom-left) have the same i + j. So loop d from 0 to n + m - 2 and print every cell with i + j == d, i.e. j = d - i, when that column exists.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& row : a)
for (int& x : row) cin >> x;
for (int d = 0; d <= n + m - 2; d++) { // cells with i + j == d
for (int i = 0; i < n; i++) {
int j = d - i;
if (j >= 0 && j < m) cout << a[i][j] << " ";
}
cout << "\n";
}
return 0;
}
Input 3 3 / 1 2 3 / 4 5 6 / 7 8 9:
1
2 4
3 5 7
6 8
9
Input 2 4 / 1 2 3 4 / 5 6 7 8:
1
2 5
3 6
4 7
8
O(n·(n + m)) as written (for each d we try every row); looping i only over the rows where 0 <= d - i < m makes it O(n·m).
Mini project: a tiny photo editor
A square "photo" is a grid of characters. Commands: right (90° clockwise), left (90° anticlockwise), mirror (left ↔ right), flip (upside down) and show. Every command is done in place with swaps and reverse, exactly as in Q1. A vector<string> works like a matrix of characters: p[i][j] is row i, column j.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// A tiny photo editor: the "photo" is an n x n grid of characters.
void show(const vector<string>& p) {
for (const string& row : p) cout << row << "\n";
cout << "--\n";
}
void transpose(vector<string>& p) {
int n = p.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) swap(p[i][j], p[j][i]);
}
void mirror(vector<string>& p) { // left <-> right
for (string& row : p) reverse(row.begin(), row.end());
}
int main() {
int n;
cin >> n;
vector<string> p(n);
for (string& row : p) cin >> row;
string cmd;
while (cin >> cmd) {
if (cmd == "right") { transpose(p); mirror(p); } // 90° clockwise
else if (cmd == "left") { transpose(p); reverse(p.begin(), p.end()); } // 90° anticlockwise
else if (cmd == "mirror") mirror(p);
else if (cmd == "flip") reverse(p.begin(), p.end()); // upside down
else if (cmd == "show") show(p);
else cout << "unknown command " << cmd << "\n";
}
return 0;
}
Input (an L shape, then commands):
4
#...
#...
#...
####
show
right
show
left
left
show
mirror
show
zoom
Output:
#...
#...
#...
####
--
####
#...
#...
#...
--
...#
...#
...#
####
--
#...
#...
#...
####
--
unknown command zoom
right turns the L so its upright becomes the top row; left twice turns it back and then one more step anticlockwise; mirror brings back the original L.
Quick quiz
1. What does this print? (the episode's quiz)
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> a = {{1, 2}, {3, 4}};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
swap(a[i][j], a[j][i]);
cout << a[0][1] << " " << a[1][0] << "\n";
return 0;
}
(A) 2 3 (B) 3 2 (C) 1 4 (D) 4 1
Answer
(A) 2 3. j starts at 0, so the pair (0,1) and (1,0) is swapped when i is 0 and swapped back when i is 1. The matrix is unchanged; a[0][1] is still 2.
2 3
2. What does this print?
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> a(3, vector<int>(5, 7));
cout << a.size() << " " << a[0].size() << " " << a[2][4] << "\n";
return 0;
}
(A) 5 3 7 (B) 3 5 7 (C) 3 5 0 (D) 15 5 7
Answer
(B) 3 5 7. 3 rows, each of 5 numbers, all filled with 7. a.size() is the number of rows, a[0].size() the number of columns.
3 5 7
3. What does this print?
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int sum = 0;
for (int i = 0; i < 3; i++) sum += a[i][i] + a[i][2 - i];
cout << sum << "\n";
return 0;
}
(A) 15 (B) 25 (C) 30 (D) 45
Answer
(C) 30. The diagonal is 1 + 5 + 9 = 15 and the anti-diagonal 3 + 5 + 7 = 15. The middle cell 5 is on both, so it is counted twice: 30. (The usual "diagonal sum" question subtracts it once for odd n: 25.)
30
4. In the staircase search for t = 9 on the Q3 matrix, how many cells are looked at?
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> a = {{1, 4, 7, 11}, {2, 5, 8, 12}, {3, 6, 9, 16}, {10, 13, 14, 17}};
int t = 9, r = 0, c = 3, looks = 0;
while (r < 4 && c >= 0) {
looks++;
if (a[r][c] == t) break;
if (a[r][c] > t) c--; else r++;
}
cout << looks << "\n";
return 0;
}
(A) 2 (B) 3 (C) 4 (D) 9
Answer
(C) 4. 11 (too big, left), 7 (too small, down), 8 (too small, down), 9 (found).
4
5. Which corner can the staircase search NOT start from? (A) top-right (B) bottom-left (C) top-left
Answer
(C) top-left (and the bottom-right too). From the top-left both directions get bigger, so a comparison doesn't tell you where to go.
Interview questions
- How do you store a matrix in C++?
vector<vector<int>> a(n, vector<int>(m));,a[i][j]is row i, column j. A fixed-sizeint a[N][M]also works; for speed, a singlevector<int>of size n·m indexeda[i * m + j]keeps everything in one block. - How do you rotate a square matrix 90° clockwise in place? Transpose (swap
a[i][j]anda[j][i]forj > i), then reverse each row. O(n²) time, O(1) space. - And anticlockwise? Transpose, then reverse the order of the rows (or: reverse each row, then transpose).
- Rotate 180°? Reverse the order of the rows, then reverse each row (or rotate 90° twice).
- Why does a transpose loop over all
jdo nothing? Every pair is visited twice,(i, j)and(j, i), and two swaps cancel out. - Can you rotate a non-square matrix in place? Not simply: an n × m matrix becomes m × n, so you build a new matrix
b[j][n-1-i] = a[i][j], O(n·m) space. - What is the trap in spiral order? The walls can cross in the middle of a ring (a single row or column is left); check
top <= bottomandleft <= rightagain before the bottom row and the left column. - How do you search a row- and column-sorted matrix? The staircase from the top-right (or bottom-left): bigger → move left, smaller → move down. O(n + m).
- When is binary search on the flattened matrix correct? When the whole matrix is sorted in reading order (each row starts after the previous row ends). Cell
midisa[mid / m][mid % m]; O(log(n·m)). - How do you set matrix zeroes in O(1) extra space? Use row 0 and column 0 as markers, plus two flags for row 0 and column 0 themselves.
- Which loop order is faster,
for i, for jorfor j, for i?ioutside,jinside: it walks each row in order, which is how the memory is laid out (row-major), so the CPU cache helps.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Matrix | Numbers arranged in rows and columns | a 3 × 3 grid 1 … 9 |
| Row | One horizontal line of a matrix, numbered from 0 | row 0 is 1 2 3 |
| Column | One vertical line of a matrix, numbered from 0 | column 0 is 1 4 7 |
vector<vector<int>> |
A vector whose items are vectors: the usual C++ matrix | a(n, vector<int>(m)) |
a[i][j] |
The cell in row i, column j | a[0][2] is 3 |
| n × m | A matrix with n rows and m columns | 3 × 4 has 12 cells |
| Square matrix | A matrix with as many rows as columns (n × n) | 3 × 3 |
| Diagonal (main diagonal) | The cells where i == j, top-left to bottom-right |
1 5 9 |
| Anti-diagonal | The cells where i + j == n - 1, top-right to bottom-left |
3 5 7 |
| In place | Changing the data itself, without a second copy: O(1) extra space | transpose + reverse |
| Transpose | Swap a[i][j] and a[j][i]: rows become columns (a flip on the diagonal) |
1 2 3 row → 1 2 3 column |
| Rotate 90° clockwise | Turn the matrix right: the top row becomes the right column | 1 2 3 / … → 7 4 1 / … |
| Reverse a row | Mirror it left to right, with reverse(row.begin(), row.end()) |
1 4 7 → 7 4 1 |
| Spiral order | Clockwise from the outside ring inward | 1 2 3 6 9 8 7 4 5 |
| Ring | One layer of the spiral: top row, right column, bottom row, left column | the outside 8 numbers of a 3 × 3 |
| Boundary / wall | The variables top, bottom, left, right that mark what is left to print |
top++ after the top row |
| Row-major order | The cells read row after row, the way they are stored | 1 4 7 11 2 5 … |
| Binary search | Halving a sorted range each step, O(log n) | needs ONE sorted line |
| Flattened matrix | The matrix seen as one list of n·m cells; cell k is a[k / m][k % m] |
cell 5 of a 4-wide matrix is a[1][1] |
| Row- and column-sorted | Every row increases to the right and every column increases downwards | the supermarket shelf |
| Staircase search | Start at the top-right; bigger → left, smaller → down; each step drops a row or a column | finds 5 in 4 looks |
| Undefined behaviour (UB) | Code the C++ rules give no meaning to; anything may happen | a[i][j] on an empty row |
| O(n²) | Work grows with the square of n | rotating an n × n matrix |
| O(n·m) | Work proportional to the number of cells | spiral order, checking every cell |
| O(n + m) | Work proportional to rows plus columns | the staircase search |
| O(1) extra space | Only a few variables, whatever the size | in-place rotation |
Summary
- A matrix in C++ is
vector<vector<int>> a(n, vector<int>(m));a[i][j]is row i, column j, both from 0.a(n)alone gives empty rows. - Rotate 90° clockwise in place: transpose, then reverse each row. Writing
a[j][n-1-i] = a[i][j]into the same matrix overwrites unread cells; a transpose must usej = i + 1or every pair is swapped back. O(n²) time, O(1) space. - Spiral order: four walls moved inward after each side; check
top <= bottomandleft <= rightagain before the bottom row and the left column. O(n·m). - Row- and column-sorted search: not binary search on the cells (reading order isn't sorted), but the staircase from the top-right. O(n + m).
- Matrix bugs rarely give errors: they give wrong answers, so always test a non-square matrix, a single row and a single column.
Next episode: Recursion questions: fast power, all subsets of a set, and all permutations of a string.