239. Sort the Diagonals
A quilt is stitched on a rectangular grid, and grid[i][j] is the shade of the patch at row i, column j. The quilter wants every diagonal stripe to fade smoothly. A stripe is a line of patches running from the top-left towards the bottom-right, that is [i][j], [i + 1][j + 1], [i + 2][j + 2] and so on, and it starts at a patch in the top row or in the left column.
Rearrange the patches inside every stripe so that the shades are in ascending order from the top-left end of the stripe to the bottom-right end. Patches never leave their own stripe. Return the new grid. The grid can contain hundreds of thousands of patches, so the sorting of the long diagonals must be efficient.
Example 1
- Input:
- grid = [[9,4,7],[3,8,2],[6,1,5]]
- Output:
- [[5,2,7],[1,8,4],[6,3,9]]
- Explanation:
The main diagonal 9,8,5 becomes 5,8,9. The diagonal 3,1 becomes 1,3 and the diagonal 4,2 becomes 2,4. The corner cells 6 and 7 are alone on their diagonals.
Example 2
- Input:
- grid = [[5,1],[2,3],[4,0]]
- Output:
- [[3,1],[0,5],[4,2]]
- Explanation:
A 3x2 grid: the diagonal 5,3 becomes 3,5 and the diagonal 2,0 becomes 0,2; the cells 1 and 4 stay.
Example 3
- Input:
- grid = [[8]]
- Output:
- [[8]]
- Explanation:
A single cell has nothing to sort.
Constraints
1 ≤ grid.length, grid[0].length ≤ 1000
1 ≤ grid.length × grid[0].length ≤ 106
-109 ≤ grid[i][j] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(m × n × log(min(m, n)))
- Space
- O(m × n)