Sort Each Diagonal
MediumSorting & Searching
Problem
A pixel-art editor has a filter that sorts every diagonal of an image: a diagonal starts at a cell in the top row or left column and runs down and to the right to the edge.
Given the grid of brightness values (1 to 100), return the grid after sorting each diagonal so its values increase from top-left to bottom-right.
Example 1
- Input:
- grid = [[9, 4, 7], [3, 5, 1], [8, 2, 6]]
- Output:
- [[5, 1, 7], [2, 6, 4], [8, 3, 9]]
The main diagonal 9, 5, 6 becomes 5, 6, 9; the diagonal 4, 1 becomes 1, 4; the diagonal 3, 2 becomes 2, 3.
Example 2
- Input:
- grid = [[3, 1, 2, 7]]
- Output:
- [[3, 1, 2, 7]]
In a single row every diagonal has one cell.
Constraints
- 1 ≤ rows, cols ≤ 100
- 1 ≤ grid[r][c] ≤ 100
Hint
Show the first hint
How can you tell whether two cells lie on the same diagonal?
Walkthrough
How to approach it
01Clarify before coding
- Which direction are diagonals? Top-left to bottom-right.
- Return a new grid or modify? Either; returning the modified grid is fine.
- Can the grid be a single row or column? Yes: nothing changes.
02Brute force
Repeatedly scan the grid and swap any cell with its lower-right neighbour when it is larger (bubble sort along diagonals) until no swap happens.
Cost: O(m · n · min(m, n)) swaps in the worst case: slow and fiddly 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.