Sort the Matrix Diagonally solution and explanation
Google
9 more videos on this problem
Sort the Matrix Diagonally | Leetcode 1329 | Similar to Leetcode 498 | codestorywithMIKcodestorywithMIK · 24:02 · 17K views
Sort the Matrix Diagonally | Live Coding with Explanation | Leetcode #1329Algorithms Made Easy · 8:23 · 14K views
Sort the Matrix Diagonally (Leetcode 1329)Coding Interviews · 5:56 · 5K views
Sort the Matrix Diagonally | leetcode 1329 | matrix | HashMapNaresh Gupta · 8:22 · 4K views
Leetcode - Sort the Matrix Diagonally (Python)Timothy H Chang · 15:45 · 2K views
LeetCode 1329. Sort the Matrix DiagonallyHappy Coding · 5:55 · 1K views
Sort the matrix diagonally | Leetcode 1329Coding Decoded · 9:18 · 1K views
Sort the Matrix Diagonally | LeetCode 1329 | Python SolutionThe Code Architect · 9:31 · 622 views
Daily Leetcode #880: Aug 28, 2022 - 1329. Sort the Matrix DiagonallyProgramming Live with Larry · 5:11 · 491 views
LeetCode 1329 : JAVA Solution | Sort the Matrix DiagonallyAmit Manjarly · 15:30 · 345 views
The problem
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.lengthn == mat[i].length1 <= m, n <= 1001 <= 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.
from collections import defaultdict
import heapq
def diagonalSort(mat):
diagonals = defaultdict(list)
m, n = len(mat), len(mat[0])
for i in range(m):
for j in range(n):
heapq.heappush(diagonals[i - j], mat[i][j])
for i in range(m):
for j in range(n):
mat[i][j] = heapq.heappop(diagonals[i - j])
return matimport java.util.*;
class Solution {
public int[][] diagonalSort(int[][] mat) {
Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();
int m = mat.length, n = mat[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
diagonals.putIfAbsent(i - j, new PriorityQueue<>());
diagonals.get(i - j).add(mat[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = diagonals.get(i - j).poll();
}
}
return mat;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>>& mat) {
std::unordered_map<int, std::vector<int>> diagonals;
int m = mat.size(), n = mat[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
diagonals[i - j].push_back(mat[i][j]);
}
}
for (auto& diag : diagonals) {
std::sort(diag.second.begin(), diag.second.end());
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mat[i][j] = diagonals[i - j].back();
diagonals[i - j].pop_back();
}
}
return mat;
}function diagonalSort(mat) {
let map = new Map();
let m = mat.length, n = mat[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let d = i - j;
if (!map.has(d)) map.set(d, []);
map.get(d).push(mat[i][j]);
}
}
for (let key of map.keys()) {
map.set(key, map.get(key).sort((a, b) => a - b));
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let d = i - j;
mat[i][j] = map.get(d).shift();
}
}
return mat;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 101
void sort(int *arr, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int** diagonalSort(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
int diagonals[MAX][MAX];
int diagCount[MAX];
memset(diagCount, 0, sizeof(diagCount));
*returnSize = matSize;
*returnColumnSizes = matColSize;
for (int i = 0; i < matSize; i++) {
for (int j = 0; j < matColSize[i]; j++) {
int d = i - j + 50;
diagonals[d][diagCount[d]++] = mat[i][j];
}
}
for (int d = 0; d < MAX; d++) {
if (diagCount[d] > 0) {
sort(diagonals[d], diagCount[d]);
}
}
for (int i = 0; i < matSize; i++) {
for (int j = 0; j < matColSize[i]; j++) {
int d = i - j + 50;
mat[i][j] = diagonals[d][matColSize[d]++];
}
}
return mat;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] DiagonalSort(int[][] mat) {
var diagonals = new Dictionary<int, List<int>>();
int m = mat.Length, n = mat[0].Length;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int d = i - j;
if (!diagonals.ContainsKey(d)) {
diagonals[d] = new List<int>();
}
diagonals[d].Add(mat[i][j]);
}
foreach (var key in diagonals.Keys) {
diagonals[key].Sort();
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int d = i - j;
mat[i][j] = diagonals[d][^1];
diagonals[d].RemoveAt(diagonals[d].Count - 1);
}
return mat;
}
}The Python solution uses a defaultdict with lists turned into heaps using heapq. After pushing all diagonal elements into respective heaps, they are popped in sorted order back into the matrix.
Time Complexity: O(m * n * log(min(m, n))) due to heap operations on diagonals.
Space Complexity: O(m * n) for storing diagonal elements.
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.
def diagonalSort(mat):
m, n = len(mat), len(mat[0])
def sort_diagonal(x, y):
diag = []
i, j = x, y
while i < m and j < n:
diag.append(mat[i][j])
i += 1
j += 1
diag.sort()
i, j = x, y
for value in diag:
mat[i][j] = value
i += 1
j += 1
for i in range(m):
sort_diagonal(i, 0)
for j in range(1, n):
sort_diagonal(0, j)
return matimport java.util.*;
class Solution {
public int[][] diagonalSort(int[][] mat) {
int m = mat.length, n = mat[0].length;
for (int i = 0; i < m; ++i) sortAndReplace(mat, i, 0);
for (int j = 1; j < n; ++j) sortAndReplace(mat, 0, j);
return mat;
}
private void sortAndReplace(int[][] mat, int row, int col) {
int m = mat.length, n = mat[0].length;
List<Integer> diag = new ArrayList<>();
int i = row, j = col;
while (i < m && j < n) {
diag.add(mat[i][j]);
i++; j++;
}
Collections.sort(diag);
i = row; j = col;
for (int value : diag) {
mat[i][j] = value;
i++; j++;
}
}
}#include <vector>
#include <algorithm>
void sortDiagonal(std::vector<std::vector<int>>& mat, int row, int col) {
int m = mat.size();
int n = mat[0].size();
std::vector<int> diag;
int i = row, j = col;
while (i < m && j < n) {
diag.push_back(mat[i][j]);
i++; j++;
}
std::sort(diag.begin(), diag.end());
i = row; j = col;
for (int value : diag) {
mat[i][j] = value;
i++; j++;
}
}
std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
for (int i = 0; i < m; ++i) sortDiagonal(mat, i, 0);
for (int j = 1; j < n; ++j) sortDiagonal(mat, 0, j);
return mat;
}function diagonalSort(mat) {
const m = mat.length, n = mat[0].length;
function sortAndReplace(row, col) {
let diag = [];
let i = row, j = col;
while (i < m && j < n) {
diag.push(mat[i][j]);
i++; j++;
}
diag.sort((a, b) => a - b);
i = row; j = col;
let k = 0;
while (i < m && j < n) {
mat[i][j] = diag[k++];
i++; j++;
}
}
for (let i = 0; i < m; ++i) sortAndReplace(i, 0);
for (let j = 1; j < n; ++j) sortAndReplace(0, j);
return mat;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void sort(int *array, int size) {
for (int step = 0; step < size - 1; ++step) {
for (int i = 0; i < size - step - 1; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
void sortDiagonal(int **mat, int m, int n, int x, int y) {
int array[100], idx = 0;
int i = x, j = y;
while (i < m && j < n) {
array[idx++] = mat[i][j];
i++; j++;
}
sort(array, idx);
i = x; j = y; idx = 0;
while (i < m && j < n) {
mat[i][j] = array[idx++];
i++; j++;
}
}
int** diagonalSort(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = matSize;
*returnColumnSizes = matColSize;
for (int i = 0; i < matSize; i++)
sortDiagonal(mat, matSize, *matColSize, i, 0);
for (int j = 1; j < *matColSize; j++)
sortDiagonal(mat, matSize, *matColSize, 0, j);
return mat;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] DiagonalSort(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
for (int i = 0; i < m; ++i) SortAndReplace(mat, i, 0);
for (int j = 1; j < n; ++j) SortAndReplace(mat, 0, j);
return mat;
}
private void SortAndReplace(int[][] mat, int row, int col) {
int m = mat.Length, n = mat[0].Length;
List<int> diag = new List<int>();
int i = row, j = col;
while (i < m && j < n) {
diag.Add(mat[i][j]);
i++; j++;
}
diag.Sort();
i = row; j = col;
foreach (int value in diag) {
mat[i][j] = value;
i++; j++;
}
}
}The Python solution employs a helper function to manage diagonal sorting, ensuring direct manipulation on the matrix itself with an intermediate list to sort elements.
Time Complexity: O(m * n * log(min(m, n))) driven by sort operation logic.
Space Complexity: O(min(m, n)), constrained to diagonal-to-list translation.
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.
function diagonalSort(mat: number[][]): number[][] {
const [m, n] = [mat.length, mat[0].length];
const g: number[][] = Array.from({ length: m + n }, () => []);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
g[m - i + j].push(mat[i][j]);
}
}
for (const e of g) {
e.sort((a, b) => b - a);
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
mat[i][j] = g[m - i + j].pop()!;
}
}
return mat;
}func diagonalSort(mat [][]int) [][]int {
m, n := len(mat), len(mat[0])
g := make([][]int, m+n)
for i, row := range mat {
for j, x := range row {
g[m-i+j] = append(g[m-i+j], x)
}
}
for _, e := range g {
sort.Sort(sort.Reverse(sort.IntSlice(e)))
}
for i, row := range mat {
for j := range row {
k := len(g[m-i+j])
mat[i][j] = g[m-i+j][k-1]
g[m-i+j] = g[m-i+j][:k-1]
}
}
return mat
}impl Solution {
pub fn diagonal_sort(mut mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let m = mat.len();
let n = mat[0].len();
let mut g: Vec<Vec<i32>> = vec![vec![]; m + n];
for i in 0..m {
for j in 0..n {
g[m - i + j].push(mat[i][j]);
}
}
for e in &mut g {
e.sort_by(|a, b| b.cmp(a));
}
for i in 0..m {
for j in 0..n {
mat[i][j] = g[m - i + j].pop().unwrap();
}
}
mat
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Hashmap for Diagonals | Time Complexity: |
| In-place Sorting without Extra Storage | Time Complexity: |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When 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 sort | O(mn * min(m,n)) | O(1) | When memory usage must stay constant and matrix size is small. |
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.