Sort the Matrix Diagonally

Medium
287.

Sort the Matrix Diagonally

Sort the Matrix Diagonally is a medium coding problem on arrays, sorting and matrix, asked in Amazon, Google and Microsoft interviews.

A matrix diagonal is a run of cells starting on the top row or the leftmost column and going down-right to the edge of the matrix.

Given an m × n matrix mat, sort each diagonal in ascending order and return the result.

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 = [[2,1],[1,2]]
Output
[[2,1],[1,2]]
Explanation
Each diagonal here has at most one out-of-place element.

Example 3

Input
mat = [[9]]
Output
[[9]]

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • 1 <= mat[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort the Matrix Diagonally — Solution in Python, Java & C++

Sort the Matrix Diagonally solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sort the Matrix Diagonally is a medium coding problem on arrays, sorting and matrix, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Matrix
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A matrix diagonal is a run of cells starting on the top row or the leftmost column and going down-right to the edge of the matrix.

Given an m × n matrix mat, sort each diagonal in ascending order and return the result.

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 = [[2,1],[1,2]]
Output: [[2,1],[1,2]]
Explanation: Each diagonal here has at most one out-of-place element.

Example 3

Input: mat = [[9]]
Output: [[9]]

Constraints

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

Hints for Sort the Matrix Diagonally

  1. Hint 1

    Cells on the same down-right diagonal share the value r - c. Bucket by it.

  2. Hint 2

    Sort each bucket, then walk the matrix again writing the sorted values back in order.

  3. Hint 3

    Keep a per-diagonal cursor so each bucket is consumed from front to back.

How to solve Sort the Matrix Diagonally

Cells on a down-right diagonal share r - c. Bucket by that key, sort each bucket, and write the sorted values back with a per-diagonal cursor.

Approach

  1. Group every value by r - c.
  2. Sort each group.
  3. Walk the matrix again, emitting the next value from the group for r - c.

Why it works

The traversal visits each diagonal's cells in top-left to bottom-right order, so consuming each sorted bucket from the front places values in ascending order along the diagonal.

Complexity

  • Time — O(m · n · log(min(m, n)))
  • Space — O(m · n)

Pitfalls

  • Values are bounded (≤ 100), so a counting sort per bucket removes the log factor.

Reference solution

Python

def diagonalSort(mat):
    m, n = len(mat), len(mat[0])
    groups = {}
    for r in range(m):
        for c in range(n):
            groups.setdefault(r - c, []).append(mat[r][c])
    for key in groups:
        groups[key].sort()
    cursor = {}
    out = []
    for r in range(m):
        row = []
        for c in range(n):
            key = r - c
            idx = cursor.get(key, 0)
            row.append(groups[key][idx])
            cursor[key] = idx + 1
        out.append(row)
    return out

Java

public static int[][] diagonalSort(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    Map<Integer, List<Integer>> groups = new HashMap<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            groups.computeIfAbsent(r - c, x -> new ArrayList<>()).add(mat[r][c]);
        }
    }
    for (List<Integer> g : groups.values()) Collections.sort(g);
    Map<Integer, Integer> cursor = new HashMap<>();
    int[][] out = new int[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int key = r - c;
            int idx = cursor.getOrDefault(key, 0);
            out[r][c] = groups.get(key).get(idx);
            cursor.put(key, idx + 1);
        }
    }
    return out;
}

C++

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
    int m = (int) mat.size(), n = (int) mat[0].size();
    map<int, vector<int>> groups;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) groups[r - c].push_back(mat[r][c]);
    }
    for (auto& kv : groups) sort(kv.second.begin(), kv.second.end());
    map<int, int> cursor;
    vector<vector<int>> out(m, vector<int>(n, 0));
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int key = r - c;
            out[r][c] = groups[key][cursor[key]];
            cursor[key]++;
        }
    }
    return out;
}

JavaScript

var diagonalSort = function(mat) {
    const m = mat.length, n = mat[0].length;
    const groups = new Map();
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            const key = r - c;
            if (!groups.has(key)) groups.set(key, []);
            groups.get(key).push(mat[r][c]);
        }
    }
    groups.forEach(function(arr) { arr.sort(function(a, b) { return a - b; }); });
    const cursor = new Map();
    const out = [];
    for (let r = 0; r < m; r++) {
        const row = [];
        for (let c = 0; c < n; c++) {
            const key = r - c;
            const idx = cursor.get(key) || 0;
            row.push(groups.get(key)[idx]);
            cursor.set(key, idx + 1);
        }
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms