Sort Matrix by Diagonals - Practice Coding Problems

Sort Matrix by Diagonals - Problem

You are given an n × n square matrix of integers grid. Your task is to return the matrix such that:

• The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order (descending)

• The diagonals in the top-right triangle are sorted in non-decreasing order (ascending)

Each diagonal is a line of cells where the difference between row and column indices remains constant.

Input & Output

Example 1 — Basic 3×3 Matrix

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

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

💡 Note: Bottom-left diagonals [4], [2,2], [3,2,2] sorted descending. Top-right diagonals [3,1], [1] sorted ascending. Main diagonal [3,2,2] stays [3,2,2] when sorted descending.

Example 2 — Larger Matrix

$ Input: grid = [[7,6,5],[4,3,2],[1,8,9]]

› Output: [[7,5,6],[4,3,2],[1,8,9]]

💡 Note: Bottom-left: [1], [4,8], [7,3,9] sorted descending. Top-right: [6,2], [5] sorted ascending. Result has properly sorted diagonals.

Example 3 — Already Sorted

$ Input: grid = [[5,4],[3,2]]

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

💡 Note: Bottom-left diagonal [5,2] sorted descending stays [5,2]. Top-right diagonal [4] stays [4]. Cross-diagonal [3] stays [3].

Constraints

n == grid.length == grid[i].length
1 ≤ n ≤ 100
1 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3×3 matrix with unsorted diagonals

Identify Triangles

Bottom-left (blue) sorted descending, top-right (yellow) sorted ascending

Sorted Result

Each diagonal properly sorted according to rules

Key Takeaway

🎯 Key Insight: Use (row - col) to identify diagonals, then sort based on triangle position

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is that diagonals can be identified by the value (row - col), with negative values for top-right triangle and non-negative for bottom-left triangle. Best approach extracts each diagonal, sorts according to triangle rules (ascending for top-right, descending for bottom-left), then places back. Time: O(n² log n), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Extract and Sort Each Diagonal	O(n² log n)	O(n²)	Extract each diagonal, sort it according to rules, then place back in matrix
In-Place Diagonal Sorting	O(n² log n)	O(n)	Sort diagonals one by one without storing all elements separately

Extract and Sort Each Diagonal — Algorithm Steps

Step 1: For each possible diagonal (identified by row - col), extract all elements
Step 2: Sort each diagonal - descending for bottom-left triangle, ascending for top-right
Step 3: Place sorted elements back into their diagonal positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Diagonals

Group elements by (row - col) value

Sort Each Diagonal

Sort based on triangle position

Reconstruct Matrix

Place sorted elements back

Code -

solution.c — C

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

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

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

int** solution(int** grid, int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        (*returnColumnSizes)[i] = n;
    }
    
    // Create arrays for each diagonal
    int diagonals[2*n-1][n];
    int diagonal_sizes[2*n-1];
    memset(diagonal_sizes, 0, sizeof(diagonal_sizes));
    
    // Extract diagonals
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int key = i - j + n - 1; // Shift to positive index
            diagonals[key][diagonal_sizes[key]++] = grid[i][j];
        }
    }
    
    // Sort each diagonal
    for (int k = 0; k < 2*n-1; k++) {
        int original_key = k - n + 1;
        if (original_key >= 0) {
            qsort(diagonals[k], diagonal_sizes[k], sizeof(int), compare_desc);
        } else {
            qsort(diagonals[k], diagonal_sizes[k], sizeof(int), compare_asc);
        }
    }
    
    // Place back
    int diagonal_indices[2*n-1];
    memset(diagonal_indices, 0, sizeof(diagonal_indices));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int key = i - j + n - 1;
            grid[i][j] = diagonals[key][diagonal_indices[key]++];
        }
    }
    
    return grid;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for 2D array
    int n = 0;
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') n++;
        ptr++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse numbers
    ptr = line;
    int row = 0, col = 0;
    char num_str[20];
    int num_idx = 0;
    
    while (*ptr) {
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            num_str[num_idx++] = *ptr;
        } else if (num_idx > 0) {
            num_str[num_idx] = '\0';
            grid[row][col] = atoi(num_str);
            col++;
            if (col == n) {
                col = 0;
                row++;
            }
            num_idx = 0;
        }
        ptr++;
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(grid, n, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", result[i][j]);
            if (j < n-1) printf(",");
        }
        printf("]");
        if (i < n-1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Visit each cell once to extract O(n²), sort n diagonals of average length n/2 giving O(n² log n)

⚠ Quadratic Growth

Space Complexity

O(n²)

Store all diagonal elements in separate arrays before sorting

⚠ Quadratic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Extract and Sort Each Diagonal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler