Sort the Matrix Diagonally - Practice Coding Problems

Sort the Matrix Diagonally - 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.

Input & Output

Example 1 — Basic 3x3 Matrix

$ 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]]

💡 Note: Main diagonal [3,2,1] becomes [1,2,3]. Diagonal starting at [0,1]: [3,2,1] becomes [1,2,3]. Each diagonal is sorted independently while maintaining structure.

Example 2 — Rectangular 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]]

💡 Note: Each diagonal is sorted independently. The main diagonal [11,55,36,25,5] becomes [5,11,25,36,55].

Example 3 — Single Row

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

› Output: [[1,2,3,4]]

💡 Note: Each element forms its own diagonal, so no sorting is needed. Matrix remains unchanged.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Original matrix with unsorted diagonals

Identify Diagonals

Group elements by diagonal lines

Sorted Result

Each diagonal sorted in ascending order

Key Takeaway

🎯 Key Insight: Elements on the same diagonal have the same (row - col) value, allowing efficient grouping and sorting

Asked in

f Facebook 35 a Amazon 28 G Google 22 M Microsoft 18

The key insight is that all cells on the same diagonal share the same (row - col) value. We can group elements by this coordinate difference, sort each group, then redistribute back. Best approach uses coordinate mapping with Time: O(m×n×log(min(m,n))), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Coordinate Mapping	O(m×n×log(min(m,n)))	O(m×n)	Use (row - col) to group diagonal elements, then sort each group
Extract, Sort, Replace	O(m×n×log(min(m,n)))	O(min(m,n))	Extract each diagonal into an array, sort it, then place back

Coordinate Mapping — Algorithm Steps

Group elements by (row - col) coordinate
Sort each group separately
Redistribute sorted elements back to matrix

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Keys

Each cell gets key = row - col

Group & Sort

Elements with same key form one diagonal

Redistribute

Place sorted values back by key order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 500

struct DiagonalElement {
    int value;
    int count;
};

struct Diagonal {
    int elements[MAX_SIZE];
    int size;
};

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int** solution(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = matSize;
    *returnColumnSizes = (int*)malloc(matSize * sizeof(int));
    for (int i = 0; i < matSize; i++) {
        (*returnColumnSizes)[i] = matColSize[i];
    }
    
    if (matSize == 0 || matColSize[0] == 0) return mat;
    
    int m = matSize, n = matColSize[0];
    
    // Group elements by diagonal (simplified for C)
    struct Diagonal diagonals[MAX_SIZE];
    int diag_keys[MAX_SIZE];
    int diag_count = 0;
    
    // Initialize
    for (int i = 0; i < MAX_SIZE; i++) {
        diagonals[i].size = 0;
    }
    
    // Collect elements by diagonal
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int key = i - j + m; // Offset to make positive index
            diagonals[key].elements[diagonals[key].size++] = mat[i][j];
        }
    }
    
    // Sort each diagonal
    for (int k = 0; k < MAX_SIZE; k++) {
        if (diagonals[k].size > 0) {
            qsort(diagonals[k].elements, diagonals[k].size, sizeof(int), compare);
        }
    }
    
    // Place back sorted elements
    int indices[MAX_SIZE] = {0};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int key = i - j + m;
            mat[i][j] = diagonals[key].elements[indices[key]++];
        }
    }
    
    return mat;
}

int main() {
    printf("Implementation requires JSON parsing\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×log(min(m,n)))

One pass to group O(m×n), sorting all diagonals O(m×n×log(min(m,n)))

⚡ Linearithmic

Space Complexity

O(m×n)

Hash map stores all matrix elements grouped by diagonal

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Coordinate Mapping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler