Skip to main content
Talentd

Sort Matrix by Diagonals - Solution & Explanation

MediumArraySortingMatrix10 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given an n x n square matrix of integers grid. Return the matrix such that:

  • The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order.
  • The diagonals in the top-right triangle are sorted in non-decreasing order.

 

Example 1:

Input: grid = [[1,7,3],[9,8,2],[4,5,6]]

Output: [[8,2,3],[9,6,7],[4,5,1]]

Explanation:

The diagonals with a black arrow (bottom-left triangle) should be sorted in non-increasing order:

  • [1, 8, 6] becomes [8, 6, 1].
  • [9, 5] and [4] remain unchanged.

The diagonals with a blue arrow (top-right triangle) should be sorted in non-decreasing order:

  • [7, 2] becomes [2, 7].
  • [3] remains unchanged.

Example 2:

Input: grid = [[0,1],[1,2]]

Output: [[2,1],[1,0]]

Explanation:

The diagonals with a black arrow must be non-increasing, so [0, 2] is changed to [2, 0]. The other diagonals are already in the correct order.

Example 3:

Input: grid = [[1]]

Output: [[1]]

Explanation:

Diagonals with exactly one element are already in order, so no changes are needed.

 

Constraints:

  • grid.length == grid[i].length == n
  • 1 <= n <= 10
  • -105 <= grid[i][j] <= 105

Approach Overview

Problem Overview: You are given a matrix and need to sort every diagonal independently. Elements that lie on the same top-left to bottom-right diagonal must be reordered while the rest of the matrix structure remains unchanged.

Approach 1: Diagonal Simulation + Sorting (O(m * n log k) time, O(k) space)

Iterate over all diagonals, collect their elements, sort them, and write them back into the matrix. A diagonal is uniquely identified by its starting point on the first row or the first column. From each start cell, walk down-right using (row+1, col+1) until the boundary is reached.

During the traversal, push values into a temporary list. Sort the list using a standard comparison sort, then traverse the same diagonal again and overwrite the matrix cells with the sorted values. The length of each diagonal is at most k = min(m, n), so sorting dominates the cost. This straightforward simulation works well because each cell belongs to exactly one diagonal.

This method relies only on basic iteration and sorting, making it easy to implement in languages like Python, Java, or C++. The matrix itself acts as the final storage while the temporary array holds the elements of a single diagonal at a time.

Approach 2: Hash Map Grouping by Diagonal Index (O(m * n log k) time, O(m * n) space)

Every cell in the matrix belongs to a diagonal identified by the key row - col. Cells with the same difference lie on the same top-left to bottom-right diagonal. Use a hash map where the key is row - col and the value is a list of elements on that diagonal.

First pass: iterate through the matrix and push each value into its diagonal bucket. Second step: sort each bucket individually. Final pass: iterate through the matrix again and place elements back from the corresponding bucket in sorted order. Depending on implementation, you can pop from the front or maintain a pointer.

This approach separates grouping from reconstruction, which can make the logic cleaner when handling many diagonals. The tradeoff is higher memory usage since all diagonal elements are stored simultaneously.

Both approaches rely on fundamentals from array traversal combined with matrix navigation and sorting techniques.

Recommended for interviews: The diagonal simulation approach is usually expected. It demonstrates that you can identify diagonal traversal patterns and apply sorting to substructures of a matrix. Interviewers often appreciate seeing the simple simulation first because it clearly shows the relationship between indices. The hash map grouping version is also acceptable but uses more memory.

Solution

We can simulate the diagonal sorting process as described in the problem.

First, we sort the diagonals of the lower-left triangle, including the main diagonal, in non-increasing order. Then, we sort the diagonals of the upper-right triangle in non-decreasing order. Finally, we return the sorted matrix.

The time complexity is O(n^2 log n), and the space complexity is O(n). Here, n is the size of the matrix.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Diagonal Simulation + SortingO(m * n log k)O(k)Best general approach; simple implementation and minimal extra memory
Hash Map Grouping by (row - col)O(m * n log k)O(m * n)Useful when grouping diagonals first simplifies processing logic

Video Solution

Sort Matrix by Diagonals | 2 Approaches | Without Map | Leetcode 3446 | codestorywithMIK • codestorywithMIK • 6,516 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort Matrix by Diagonals easy or hard?
Sort Matrix by Diagonals is generally considered a medium difficulty problem. The main challenge is identifying how diagonals are traversed and ensuring each diagonal is processed exactly once while keeping the matrix structure intact.
Sort Matrix by Diagonals Python/Java solution
In Python or Java, iterate through diagonal starting points, push elements into a list, sort the list, and rewrite values along the same diagonal. Python typically uses a list with sort(), while Java implementations use ArrayList with Collections.sort().
How to solve Sort Matrix by Diagonals in O(n)?
An exact O(n) solution is not feasible if arbitrary values must be sorted because sorting requires at least O(k log k) comparisons for a diagonal of length k. The practical optimal approach remains O(m * n log k) using simulation and sorting.
What is the best approach for Sort Matrix by Diagonals?
The most practical solution is diagonal simulation with sorting. Start from each diagonal's first cell (first row and first column), collect the values along the diagonal, sort them, and write them back. This runs in O(m * n log k) time where k is the maximum diagonal length and uses O(k) extra space.
Is Sort Matrix by Diagonals asked at Google/Amazon/Meta?
Matrix traversal and diagonal processing problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as diagonal traversal, diagonal sorting, and matrix grouping test indexing logic and array manipulation skills.
What data structure is used in Sort Matrix by Diagonals?
The solution primarily uses arrays or dynamic lists to temporarily store diagonal elements before sorting. Some implementations also use a hash map keyed by row - col to group elements belonging to the same diagonal.
What is the time complexity of Sort Matrix by Diagonals?
The typical solution runs in O(m * n log k) time. Each matrix cell is visited once to gather elements, and each diagonal of length k is sorted using a comparison sort. Since k is at most min(m, n), sorting dominates the runtime.

Ready to solve this problem?

Practice Sort Matrix by Diagonals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort the Matrix Diagonally