Reviewing this in-place transpose, what does swapping m[i][j] and m[j][i] over every i and j produce?

## What the loop actually does An in-place transpose of an `n x n` grid must exchange the value at `(i, j)` with the value at `(j, i)` for each **unordered pair** of distinct positions. The buggy version writes the loop over **ordered** pairs: When the outer index is `i` and the inner index is `j`, the swap `(i, j) <-> (j, i)` happens. Later, when the outer index reaches `j` and the inner index reaches `i`, the *same two cells* are swapped again. A transposition applied twice is the identity permutation, so the pair ends up where it began. Iterate that over the whole grid and the result is the original grid, unchanged. The diagonal contributes nothing either way: when `i == j` the code swaps a cell with itself. So the double loop performs `n^2` swaps, of which `n` are self-swaps and the other `n^2 - n` cancel in pairs. Cost `Theta(n^2)`, effect zero. ## Why it survives careless testing This is the review lesson, and it is why the bug is worth recognising on sight rather than deriving each time. - A **symmetric** input — one that already equals its own transpose — is unchanged by a correct transpose too, so it cannot distinguish the two implementations. - An input where every row holds the same value, or every cell holds the same value, is symmetric in exactly this sense. - A test that builds the expected grid by calling the same buggy helper, or that asserts only on the shape or on the diagonal, passes. - The identity grid, and any grid built as "cell (i, j) = i + j", are symmetric. Reach for `i * n + j` instead: distinct in every cell and asymmetric everywhere off the diagonal. The minimum honest test is a two-by-two with four distinct values, checked cell by cell. ## The fix, and why that bound Restrict the inner loop so each unordered pair is generated exactly once: ``` for i in 0..n-1 for j in i+1..n-1 swap(m[i][j], m[j][i]) ``` That enumerates the strict upper triangle: `n(n-1)/2` pairs, one swap each. Starting the inner loop at `j = i` instead is also correct but wastes `n` self-swaps. Starting at `j = 0` and skipping only `j == i` does **not** fix anything — the double-visit is the disease, and skipping the diagonal treats a symptom that was already harmless. The mirror-image bound `j` from `0` to `i - 1` — the strict lower triangle — is equally correct. Both work because each unordered pair `{(i,j), (j,i)}` has exactly one representative with the row index smaller than the column index. ## The family of bugs this belongs to Every in-place transformation on a grid is really a permutation of cells, and a permutation decomposes into cycles. Your loop must touch **each cycle once**. The full double loop touches each two-cycle twice, and an even number of applications is the identity. The same trap appears in the ring-cycling formulation of a quarter-turn rotation, where each layer's cells fall into four-cycles: if the loop bounds let one four-cycle be rotated twice, you get a half turn on part of the board and a quarter turn elsewhere — visually obvious on a game board, and much harder to spot in a numeric assertion. It appears again in reversing rows: iterating the swap index across the whole row rather than the first half reverses the row and then reverses it back. The general rule worth stating in review: **an in-place swap loop must enumerate orbits, not positions.** Whenever you see a swap inside a full rectangular double loop, ask how many times each pair is visited before you ask anything else. ## What to say as a reviewer Don't just fix the bound. The comment that pays for itself is: "This is a no-op — each pair is swapped twice. Fix the inner bound to `i+1`, and add a case with distinct values in every cell, because the current test would pass either way." The second half is what stops the same defect from returning in the rotation code next sprint.