Skip to main content

Matrix

Sort the Matrix Diagonally Solution In C++/Python/java/JS

Problem Description

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

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]

Sort the Matrix Diagonally-Problem-Description

Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Explanation: Each diagonal is sorted independently. For example:

  • The diagonal starting at (0,0) with values [3, 2, 1] becomes [1, 2, 3].
  • The diagonal starting at (0,1) with values [3, 1] becomes [1, 3].
  • The diagonal starting at (0,2) with values [1, 2] becomes [1, 2].
  • The diagonal starting at (1,0) with values [2, 1] becomes [1, 2].
  • The diagonal starting at (2,0) with value [1] stays [1].

After sorting each diagonal, we get the final sorted matrix.

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]]
Explanation: For this larger matrix, each diagonal is sorted independently:

  • The diagonal starting at (0,0) with values [11, 55, 36, 25, 50] becomes [5, 11, 25, 36, 50].
  • The diagonal starting at (0,1) with values [25, 17, 44, 68] becomes [4, 17, 25, 44].
  • The diagonal starting at (0,2) with values [66, 45, 58] becomes [4, 45, 66].
  • The diagonal starting at (1,0) with values [23, 75, 33] becomes [14, 23, 33].

Each diagonal is sorted and the matrix is updated accordingly, resulting in the sorted output.

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • 1 <= mat[i][j] <= 100
💡
Try Solving "Sort the Matrix Diagonally" Yourself First !!
Figuring out "Sort the Matrix Diagonally" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

We're given a 2D matrix, and we're supposed to sort all diagonals going from top-left to bottom-right. First, let’s make sure we agree on what a diagonal means here.

So a diagonal means we move down and to the right at the same time — both the row and the column increase by one together, right?

Exactly! For example, starting at position [1][2], the diagonal would be all elements like [1][2], [2][3], [3][4], and so on — as long as we stay within the matrix boundaries.

So our job is: each of these diagonals must be sorted independently — without affecting others.

Let’s Use a Simple Example

Let’s visualize a 3x4 matrix like this:

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

Now let’s pick out all diagonals that move from top-left to bottom-right:

  • Starting at (0, 0) → [7, 8, 2]
  • Starting at (0, 1) → [3, 1, 3]
  • Starting at (0, 2) → [5, 4]
  • Starting at (0, 3) → [2]
  • Starting at (1, 0) → [9, 0]
  • Starting at (2, 0) → [6]

Notice how every diagonal is independent — we don’t mix elements across diagonals. Our goal is just to sort each one of these lines.

 So, What’s the Game Plan?

Let’s walk through how we might handle one diagonal. Pick the one starting at (0, 1) → [3, 1, 3].

How could we sort this?

We can walk along that diagonal, collect all its numbers into a temporary list, sort the list, and then go back along the same diagonal and place them back one by one.

Right on. So if we generalize this, our approach becomes:

  1. For each diagonal:
  2. Move along it and collect its numbers.
  3. Sort those numbers.
  4. Then move along the diagonal again and write the sorted numbers back in place.

Seems clean. Now the only challenge is — how do we cover every diagonal exactly once?

How Do We Visit Every Diagonal?

Let’s think about the diagonals’ starting points. Where do diagonals begin?

Well, every diagonal has a top-left corner. So if we walk along the top row, and for each column, start a diagonal from there — that gives us the upper set of diagonals.

Great. That gives us all the diagonals starting at positions like (0, 0), (0, 1), (0, 2), and so on.

But we’re still missing the diagonals that start from the first column, like (1, 0), (2, 0), etc.

Ah! So we just go down the first column, starting from row 1 onwards, and grab those diagonals too. That way, no diagonal is repeated.

Perfect — now we have a strategy to reach every diagonal exactly once.

What’s the Best Way to Sort While We Walk?

Now here’s a question.

When we collect all the numbers of a diagonal — do we sort them all at once after collecting them, or is there a smarter way?

I’d say just collect and sort using a simple list.

That’s totally fine. But let’s ask — what if we wanted to keep things sorted as we go, so that we always had access to the smallest number?

Then we’d need a structure where the smallest number always comes out first.

Exactly! That’s where something called a min-heap comes in. It’s just a special kind of structure where the smallest number is always on top — so we can remove it instantly, and adding a new number keeps the structure sorted.

Some programming languages call this a priority queue — where priority is based on value, and smaller values come first.

Final Plan

Here’s how we put everything together:

  1. Go along the top row and first column to pick each diagonal’s starting point.
  2. For each diagonal:
    • Walk through it and collect all values.
    • Sort the values. We can use a regular list and sort it later, or use a structure that keeps them sorted like a min-heap.
    • Then walk again along the diagonal and place the sorted values back in.

This way, each diagonal is handled independently and sorted, and the final matrix has all diagonals sorted from top-left to bottom-right.

Well explained! Now, if we take a step back and ask — what kind of strategy did we really use here?

We didn’t brute-force every possible rearrangement of diagonals or try all matrix permutations.

Instead, we broke the 2D problem into simpler, independent 1D problems — one diagonal at a time. That’s a classic divide-and-conquer mindset!

Exactly! We decomposed the matrix into disjoint diagonals, handled each one locally by sorting, and then recombined them into the original matrix. This problem teaches us how a complex-looking 2D transformation can be simplified by spotting independent linear structures within — and solving them in isolation.

Let's now see how our algorithm looks!

Sort the Matrix Diagonally Algorithm

1. Traverse All Diagonal Start Points:

  • For each column index col from 0 to n - 1, start a diagonal from position (0, col).
  • For each row index row from 1 to m - 1, start a diagonal from position (row, 0).

2. Extract Diagonal Elements:

  • From a given start point (row, col), move diagonally using row++ and col++.
  • Push all elements of the current diagonal into a min-heap (or priority queue) for automatic sorting.

3. Replace Sorted Elements Back:

  • Reset to the same start point (row, col).
  • Traverse diagonally again and poll elements from the heap one by one, placing them back into the matrix.

4. Repeat For All Diagonals: Continue this process for each start point until all diagonals have been sorted and updated in the matrix.

Approach

  1. Identify All Diagonals:
    • Start from each element in the top row (row = 0, all columns).
    • Also start from each element in the leftmost column (col = 0, all rows starting from row = 1).
    • These starting points help us capture every diagonal in the matrix exactly once.
  1. Extract Diagonal Elements: From each starting point, traverse the diagonal (down-right) and collect its elements into a temporary list or structure.
  2. Sort and Replace:
    • Sort the collected diagonal.
    • Traverse the same diagonal again and replace original values with the sorted ones.
Sort the Matrix Diagonally - Optimal-Approach

Dry-Run

Input: mat =
[[11, 25, 66, 1],
[23, 55, 17, 45],
[75, 31, 36, 44],
[22, 27, 33, 25]]

Output:
[[11, 17, 45, 1],
[23, 25, 25, 66],
[27, 31, 36, 44],
[22, 75, 33, 55]]

Explanation

We want to sort each diagonal from top-left to bottom-right independently.

We'll process diagonals starting from:

  • Top row: (0,0) → (0,1) → (0,2) → (0,3)
  • Left column: (1,0) → (2,0) → (3,0)

Let’s go one diagonal at a time.

Diagonal from (0,0)

Values: [11, 55, 36, 25]

  • Sorted: [11, 25, 36, 55]

Update in-place:

mat[0][0] = 11
mat[1][1] = 25
mat[2][2] = 36
mat[3][3] = 55

Diagonal from (0,1)

Values: [25, 17, 44]

  • Sorted: [17, 25, 44]

Update:

mat[0][1] = 17
mat[1][2] = 25
mat[2][3] = 44

Diagonal from (0,2)

Values: [66, 45]

  • Sorted: [45, 66]

Update:

mat[0][2] = 45
mat[1][3] = 66

Diagonal from (0,3)

Values: [1] (only one element — already sorted)

No change.

Diagonal from (1,0)

Values: [23, 31, 33]

  • Sorted: [23, 31, 33]

Already sorted — update back as is.

Confirm:

mat[1][0] = 23
mat[2][1] = 31
mat[3][2] = 33

Diagonal from (2,0)

Values: [75, 27]

  • Sorted: [27, 75]

Update:

mat[2][0] = 27
mat[3][1] = 75

Diagonal from (3,0)

Values: [22] (single element)

No change.

Final Matrix After Diagonal Sort

[[11, 17, 45, 1],
[23, 25, 25, 66],
[27, 31, 36, 44],
[22, 75, 33, 55]]

Sort the Matrix Diagonally Solution

Now let's checkout the "Sort the Matrix Diagonally code" in C++, Java, Python and JavaScript.

"Sort the Matrix Diagonally" Code in all Languages.
1. Sort the Matrix Diagonally solution in C++ Try on Compiler 
class Solution {
public:

    // Sorts all diagonals from top-left to bottom-right
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

        int m = mat.size();
        int n = mat[0].size();

        // Loop through each column of the top row to start diagonals
        for (int col = 0; col < n; col++) {

            // Sort diagonal starting at (0, col)
            sortDiagonal(mat, 0, col, m, n);
        }

        // Loop through each row of the first column (excluding first cell)
        for (int row = 1; row < m; row++) {

            // Sort diagonal starting at (row, 0)
            sortDiagonal(mat, row, 0, m, n);
        }

        return mat;
    }

private:

    // Sort one diagonal using a min-heap
    void sortDiagonal(vector<vector<int>>& mat, int row, int col, int m, int n) {

        // Use min-heap to store values in sorted order
        priority_queue<int, vector<int>, greater<int>> minHeap;

        int r = row, c = col;

        // Collect all values along the diagonal
        while (r < m && c < n) {
            minHeap.push(mat[r][c]);
            r++;
            c++;
        }

        r = row;
        c = col;

        // Place sorted values back into the diagonal
        while (r < m && c < n) {
            mat[r][c] = minHeap.top();
            minHeap.pop();
            r++;
            c++;
        }
    }
};

2. Sort the Matrix Diagonally Solution in Java Try on Compiler 
class Solution {

    // Sorts all diagonals from top-left to bottom-right
    public int[][] diagonalSort(int[][] mat) {

        int m = mat.length;
        int n = mat[0].length;

        // Loop over top row diagonals
        for (int col = 0; col < n; col++) {

            // Sort diagonal starting from (0, col)
            sortDiagonal(mat, 0, col, m, n);
        }

        // Loop over left column diagonals (excluding top-left corner)
        for (int row = 1; row < m; row++) {

            // Sort diagonal starting from (row, 0)
            sortDiagonal(mat, row, 0, m, n);
        }

        return mat;
    }

    private void sortDiagonal(int[][] mat, int row, int col, int m, int n) {

        // Use a min-heap to collect and sort diagonal values
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        int r = row, c = col;

        // Collect values along the diagonal
        while (r < m && c < n) {
            minHeap.offer(mat[r][c]);
            r++;
            c++;
        }

        r = row;
        c = col;

        // Write sorted values back into the diagonal
        while (r < m && c < n) {
            mat[r][c] = minHeap.poll();
            r++;
            c++;
        }
    }
}

3. Sort the Matrix Diagonally Solution in Python Try on Compiler 
import heapq

class Solution:

    # Sorts all diagonals from top-left to bottom-right
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:

        m, n = len(mat), len(mat[0])

        # Traverse all columns in the top row
        for col in range(n):

            # Sort the diagonal that starts at (0, col)
            self.sort_diagonal(mat, 0, col, m, n)

        # Traverse all rows in the first column except (0, 0)
        for row in range(1, m):

            # Sort the diagonal that starts at (row, 0)
            self.sort_diagonal(mat, row, 0, m, n)

        return mat

    # Helper method to sort a single diagonal
    def sort_diagonal(self, mat: List[List[int]], row: int, col: int, m: int, n: int):

        # Use a min-heap to store elements of the diagonal
        heap = []

        r, c = row, col

        # Collect all values along this diagonal
        while r < m and c < n:
            heapq.heappush(heap, mat[r][c])
            r += 1
            c += 1

        r, c = row, col

        # Write back sorted values into the diagonal
        while r < m and c < n:
            mat[r][c] = heapq.heappop(heap)
            r += 1
            c += 1

4. Sort the Matrix Diagonally solution in JavaScript Try on Compiler 
/**
 * Sorts all diagonals in a matrix independently
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(mat) {

    const m = mat.length;
    const n = mat[0].length;

    // Loop through each column of top row to start diagonals
    for (let col = 0; col < n; col++) {

        // Sort diagonal starting at (0, col)
        sortDiagonal(mat, 0, col, m, n);
    }

    // Loop through each row of first column (excluding top-left)
    for (let row = 1; row < m; row++) {

        // Sort diagonal starting at (row, 0)
        sortDiagonal(mat, row, 0, m, n);
    }

    return mat;
};

// Helper function to sort one diagonal
function sortDiagonal(mat, row, col, m, n) {

    // Collect values along the diagonal
    const values = [];
    let r = row, c = col;

    while (r < m && c < n) {
        values.push(mat[r][c]);
        r++;
        c++;
    }

    // Sort collected values
    values.sort((a, b) => a - b);

    r = row;
    c = col;
    let i = 0;

    // Write sorted values back to matrix
    while (r < m && c < n) {
        mat[r][c] = values[i++];
        r++;
        c++;
    }
}

Sort the Matrix Diagonally Complexity Analysis

Time Complexity: O((m + n) × log(min(m, n)))

The Sort the Matrix Diagonally algorithm involves two main operations:

a. Collecting and sorting each diagonal:
For every diagonal starting from either the top row or the leftmost column, we:

    • Traverse the diagonal and collect all elements.
    • Sort the collected elements (using a sorting algorithm or a min-heap).
    • Traverse again and write sorted values back into their original diagonal positions.
      This takes O(D log D) time for each diagonal, where D is the diagonal length.

b. Processing all diagonals:

    • Total number of diagonals = (rows + columns - 1).
    • Each diagonal’s length is at most min(m, n) (where m = rows, n = columns).

Total Time Complexity:

Each diagonal takes O(D log D) time, where D ≤ min(m, n).
Since there are O(m + n) diagonals,

Overall Time Complexity = O((m + n) × log(min(m, n)))

Space Complexity: O(m × n)

Auxiliary space refers to the extra space required by the algorithm other than the input grid.

  1. Min-heap (for sorting each diagonal):
    The min-heap stores up to min(m, n) elements for each diagonal, so its space complexity is O(min(m, n)) for each diagonal.
  2. Result array (input grid):
    The grid itself is O(m × n), which is the space for the matrix.
  3. Other variables:
    Constant space, O(1), for loop counters and other variables.

Total Space Complexity:

  1. Input grid:
    O(m × n) for the matrix itself.
  2. Auxiliary space (min-heap):
    O(min(m, n)) for storing diagonal elements during sorting.
  3. Other variables:
    Constant space, O(1).

Total space complexity:
O(m × n) for the input grid + O(min(m, n)) for the heap. Thus, the total space complexity is: O(m × n).

Similar Problems

Sort Matrix by Diagonals

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.

Diagonal Traverse

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.