Skip to main content
Talentd

Sort the Matrix Diagonally - Solution & Explanation

MediumArraySortingMatrix20 min readAsked at: Amazon, Google, Quora +1
Practice this problem

Problem Statement

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

 

Example 1:

Input: mat = [[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]]

Example 2:

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • 1 <= mat[i][j] <= 100

Approach Overview

Problem Overview: You receive an m x n matrix. Every diagonal that runs from top-left to bottom-right must be sorted independently in ascending order. Elements stay within their original diagonal; only their order changes.

Approach 1: Using HashMap for Diagonals (O(mn log k) time, O(mn) space)

The key observation is that all cells on the same diagonal share the same value of row - col. Use this value as a key in a hash map and group elements belonging to the same diagonal. First pass: iterate through the matrix and push each value into map[row - col]. Second pass: sort each list of diagonal values. Third pass: iterate through the matrix again and pop the smallest element from the corresponding diagonal list to rebuild the matrix in sorted order.

This approach is easy to reason about and clean to implement. The sorting cost comes from sorting each diagonal separately. If the longest diagonal length is k = min(m, n), the total cost becomes O(mn log k). The extra memory stores all matrix elements inside the hash map. This solution relies on concepts from array, matrix, and sorting problems.

Approach 2: In-place Diagonal Sorting without Extra Storage (O(mn * min(m,n)) time, O(1) space)

If memory is constrained, process each diagonal directly inside the matrix. Every diagonal starts either from the first row or the first column. For each starting position, walk along the diagonal and perform an insertion-style ordering: compare the current element with previous elements along that diagonal and swap backward until the order is correct.

This behaves like insertion sort applied to each diagonal. Because each insertion may scan backward along the diagonal, the worst-case time for one diagonal is O(k^2) where k is its length. Across all diagonals, the total runtime becomes roughly O(mn * min(m,n)). The benefit is constant extra memory since the matrix itself stores the sorted values.

Recommended for interviews: The hash map diagonal grouping solution is the expected answer. It demonstrates recognition of the row - col diagonal invariant and applies straightforward sorting. Interviewers like this approach because it balances clarity and performance at O(mn log k). Mentioning the in-place alternative shows deeper understanding of memory tradeoffs and matrix traversal patterns.

Approach 1: Using Hashmap for Diagonals

The first approach involves using a hashmap or dictionary to store diagonals. For any element at (i, j), the diagonal can be identified by the key (i - j). This key is unique to all elements on the same diagonal. We then collect each diagonal's elements into a list, sort them, and place them back into the matrix.

This C solution uses a hashmap-like approach by leveraging an array diagonals, where the index represents the diagonal identified by (i - j + 50) to ensure positive index values. We first populate this array with elements from each diagonal, sort the array, and write the sorted values back into the matrix.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * log(min(m, n))) due to the sorting of up to min(m, n) elements for each diagonal.
Space Complexity: O(m * n) for storing diagonal elements.

Try this approach in the editor →

Approach 2: In-place Sorting without Extra Storage

This approach aims to perform cross-diagonal sorting directly within the matrix itself, minimizing additional storage usage. By extracting diagonal elements one at a time, sorting them, and reinserting them, we achieve the diagonal sorting task with constrained space complexity.

This C code sorts diagonals in place without extra structures. It iterates over each diagonal from top row and left column, extracts, sorts, and reinserts elements back directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * log(min(m, n))) due to sorting operations.
Space Complexity: O(min(m, n)) for temporary diagonal storage.

Try this approach in the editor →

Approach 3: Sorting

We can treat each diagonal of the matrix as an array, sort these arrays, and then fill the sorted elements back into the original matrix.

Specifically, we denote the number of rows in the matrix as m and the number of columns as n. Since any two elements (i_1, j_1) and (i_2, j_2) on the same diagonal satisfy j_1 - i_1 = j_2 - i_2, we can determine each diagonal based on the value of j - i. To ensure the value is positive, we add an offset m, that is, m - i + j.

Finally, we fill the sorted elements of each diagonal back into the original matrix.

The time complexity is O(m times n times log min(m, n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hashmap for Diagonals

Time Complexity: O(m * n * log(min(m, n))) due to the sorting of up to min(m, n) elements for each diagonal.
Space Complexity: O(m * n) for storing diagonal elements.

In-place Sorting without Extra Storage

Time Complexity: O(m * n * log(min(m, n))) due to sorting operations.
Space Complexity: O(min(m, n)) for temporary diagonal storage.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap grouping by (row - col)O(mn log k)O(mn)General case. Clean and commonly expected interview solution.
In-place diagonal insertion sortO(mn * min(m,n))O(1)When memory usage must stay constant and matrix size is small.

Video Solution

Sort the Matrix Diagonally | Leetcode 1329 | Similar to Leetcode 498 | codestorywithMIK • codestorywithMIK • 17,346 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort the Matrix Diagonally easy or hard?
Sort the Matrix Diagonally is classified as a Medium problem. The challenge is recognizing the invariant that cells on the same diagonal share the same (row - col) value and using that property to group and sort elements efficiently.
How to solve Sort the Matrix Diagonally in O(n)?
A strict O(n) solution is not achievable because each diagonal must be sorted. Sorting introduces a log factor, giving O(mn log k). The closest efficient method groups elements by (row - col), sorts each group, then writes them back.
What is the best approach for Sort the Matrix Diagonally?
The most common solution groups elements by diagonal using the key (row - column). Each diagonal's values are collected in a hash map, sorted, and written back into the matrix. This approach runs in O(mn log k) time where k is the diagonal length and uses O(mn) extra space.
What data structure is used in Sort the Matrix Diagonally?
A hash map is typically used to group matrix elements by diagonal using the key (row - col). Each key maps to a list that stores values from the same diagonal, which are then sorted before reconstructing the matrix.
What is the time complexity of Sort the Matrix Diagonally?
Using the hash map grouping technique, the complexity is O(mn log k). The matrix traversal costs O(mn) and each diagonal of length k is sorted. Since k is at most min(m, n), the sorting factor becomes log(min(m, n)).
Sort the Matrix Diagonally Python or Java solution approach?
Both Python and Java implementations follow the same idea: map diagonals using (row - col), store elements in lists, sort each list, and refill the matrix while iterating again. The logic stays identical across languages like C++, C#, and JavaScript.
Is Sort the Matrix Diagonally asked at Google or Amazon interviews?
Matrix traversal and diagonal processing problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve grouping by diagonals or manipulating matrix structure are common interview exercises.

Ready to solve this problem?

Practice Sort the Matrix Diagonally with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort Matrix by Diagonals