Sort Every Diagonal
MediumMatrix
Problem
A seed tray is laid out as an m × n grid of germination scores. The gardener wants every diagonal running from top-left to bottom-right sorted in ascending order from its top-left end to its bottom-right end, without moving any value off its diagonal.
Return the grid after sorting each such diagonal independently.
Example 1
- Input:
- grid = [[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]
- Output:
- [[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]
The main diagonal 3, 2, 1 becomes 1, 2, 3; the diagonal 3, 1, 2 starting at (0, 1) becomes 1, 2, 3.
Example 2
- Input:
- grid = [[3, 2, 1]]
- Output:
- [[3, 2, 1]]
In a single row every diagonal has one cell.
Constraints
- 1 ≤ m, n ≤ 300
- -10^4 ≤ grid[i][j] ≤ 10^4
Hint
Show the first hint
Cells on the same top-left to bottom-right diagonal share r - c. Where does each diagonal start?
Walkthrough
How to approach it
01Clarify before coding
- Ascending from top-left to bottom-right? Yes.
- Do values move between diagonals? Never: each diagonal is sorted on its own.
- Return a new grid or modify? Either works; returning the sorted grid is what is checked.
02Brute force
Repeatedly scan the grid and swap any cell with its lower-right neighbour when it is larger, until no swap happens (a bubble sort on every diagonal at once).
Cost: O(min(m, n)) sweeps of O(m · n) each, i.e. O(m · n · min(m, n)): roughly 2.7 · 10^7 for 300 × 300, and clumsy to reason about.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.