Facebook Pixel

3446. Sort Matrix by Diagonals

MediumArrayMatrixSorting
Leetcode Link

Problem Description

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.

Intuition

To solve the problem, we need to sort the diagonals of a given square matrix, focusing specifically on two distinct triangular sections of the matrix:

  1. Bottom-left triangle including the middle diagonal: This section is sorted in non-increasing order. To achieve this, we start sorting from the bottom rows moving upwards.

  2. Top-right triangle: Here, the sorting is in non-decreasing order. This section is handled by sorting from the top rows downwards.

The key intuition here is to identify and isolate each diagonal, sort its elements, and then replace them in the grid in the required order. By iterating through the starting points of each diagonal, extracting the elements, sorting them, and repopulating the grid, we achieve the desired configuration. This approach leverages the properties of diagonals, ensuring ordered transitions across matrix elements.

Learn more about Sorting patterns.

Solution Approach

The referenced solution approach employs a simulation and sorting strategy to arrange the matrix diagonals as required.

  1. Extracting Diagonals:

    • For the bottom-left section, including the main diagonal, we iterate downward across each diagonal starting from the second last row upwards. Using two nested loops, diagonals are extracted by running through them using indices (i, j).
    • For the top-right section, we iterate diagonally upwards, excluding the very first diagonal, essentially dealing with sections that start from the top.

  2. Sorting Diagonals:

    • For the bottom-left diagonals, the respective list of elements are sorted in non-increasing order.
    • Conversely, for the top-right diagonals, the elements are sorted in non-decreasing order.

  3. Reassigning Sorted Values:

    • The sorted lists are then reassembled into the matrix. For each diagonal, the list of sorted values is inserted back into their original diagonal positions using another pair of loops similar to extraction.

By leveraging loops that specifically target diagonal entries and using Python's built-in sorting to rearrange these entries, the solution efficiently meets the requirements of the matrix transformation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simple 3x3 matrix as an example to illustrate the solution approach.

Original matrix grid:

3 8 1
4 9 6
7 2 5

Step 1: Extracting Diagonals

  • Bottom-Left Triangle:

    • From (2,0) to (0,2), the diagonals are:
      • Diagonal from (2,0): [7]
      • Diagonal from (1,0) to (2,1): [4, 2]
      • Diagonal from (0,0) to (1,1) to (2,2): [3, 9, 5]

  • Top-Right Triangle:

    • From (0,1) to (2,2), the diagonals are:
      • Diagonal from (0,1) to (1,2): [8, 6]
      • Diagonal from (0,2): [1]

Step 2: Sorting Diagonals

  • Bottom-Left Triangle: Sort in Non-Increasing Order

    • [7] remains [7]
    • [4, 2] becomes [4, 2]
    • [3, 9, 5] becomes [9, 5, 3]

  • Top-Right Triangle: Sort in Non-Decreasing Order

    • [8, 6] becomes [6, 8]
    • [1] remains [1]

Step 3: Reassigning Sorted Values

  • Place sorted diagonals back into the matrix:
    • Fill [7] into (2,0)
    • Fill [4, 2] into (1,0) and (2,1)
    • Fill [9, 5, 3] into (0,0), (1,1), and (2,2)
    • Fill [6, 8] into (0,1) and (1,2)
    • Fill [1] into (0,2)

Resulting grid:

9 6 1
4 5 8
7 2 3

By following this approach, the matrix diagonals are transformed as required, demonstrating a systematic application of the solution's instructions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
5        # Get the size of the grid (assuming square matrix)
6        n = len(grid)
7      
8        # Process the diagonals starting from the lower left to the main diagonal
9        for k in range(n - 2, -1, -1):
10            i, j = k, 0
11            diagonal_elements = []
12            # Collect elements along the diagonal starting at (k, 0)
13            while i < n and j < n:
14                diagonal_elements.append(grid[i][j])
15                i += 1
16                j += 1
17            # Sort these collected elements
18            diagonal_elements.sort()
19            # Place sorted elements back along the diagonal
20            i, j = k, 0
21            while i < n and j < n:
22                grid[i][j] = diagonal_elements.pop(0)
23                i += 1
24                j += 1
25      
26        # Process the diagonals starting from the upper right to below the main diagonal
27        for k in range(n - 2, 0, -1):
28            i, j = k, n - 1
29            diagonal_elements = []
30            # Collect elements along the diagonal starting at (k, n-1)
31            while i >= 0 and j >= 0:
32                diagonal_elements.append(grid[i][j])
33                i -= 1
34                j -= 1
35            # Sort these collected elements
36            diagonal_elements.sort()
37            # Place sorted elements back along the diagonal
38            i, j = k, n - 1
39            while i >= 0 and j >= 0:
40                grid[i][j] = diagonal_elements.pop(0)
41                i -= 1
42                j -= 1
43
44        return grid
45
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    public int[][] sortMatrix(int[][] grid) {
7        int n = grid.length;
8      
9        // Sort the diagonals starting from the last column and moving upwards
10        for (int startRow = n - 2; startRow >= 0; --startRow) {
11            int i = startRow, j = 0;
12            List<Integer> diagonalElements = new ArrayList<>();
13          
14            // Collect elements of the current diagonal
15            while (i < n && j < n) {
16                diagonalElements.add(grid[i][j]);
17                i++;
18                j++;
19            }
20          
21            // Sort the collected diagonal elements
22            Collections.sort(diagonalElements);
23          
24            // Place the sorted elements back into the grid
25            for (int element : diagonalElements) {
26                grid[--i][--j] = element;
27            }
28        }
29      
30        // Sort the diagonals starting from the last row and moving to the first row
31        for (int startColumn = n - 2; startColumn > 0; --startColumn) {
32            int i = startColumn, j = n - 1;
33            List<Integer> diagonalElements = new ArrayList<>();
34          
35            // Collect elements of the current diagonal
36            while (i >= 0 && j >= 0) {
37                diagonalElements.add(grid[i][j]);
38                i--;
39                j--;
40            }
41          
42            // Sort the collected diagonal elements
43            Collections.sort(diagonalElements);
44          
45            // Place the sorted elements back into the grid
46            for (int element : diagonalElements) {
47                grid[++i][++j] = element;
48            }
49        }
50      
51        // Return the sorted grid
52        return grid;
53    }
54}
55
1#include <vector>
2#include <algorithm> // For std::sort
3
4class Solution {
5public:
6    // Function to sort diagonals of a square matrix
7    std::vector<std::vector<int>> sortMatrix(std::vector<std::vector<int>>& grid) {
8        int n = grid.size();
9      
10        // Sort diagonals starting from the second last row to the first row
11        for (int startRow = n - 2; startRow >= 0; --startRow) {
12            int i = startRow, j = 0;
13            std::vector<int> diagonalElements;
14          
15            // Collect elements along the diagonal from (startRow, 0)
16            while (i < n && j < n) {
17                diagonalElements.push_back(grid[i][j]);
18                i++;
19                j++;
20            }
21          
22            // Sort the collected diagonal elements
23            std::sort(diagonalElements.begin(), diagonalElements.end());
24          
25            // Place sorted elements back into the grid
26            for (int element : diagonalElements) {
27                i--;
28                j--;
29                grid[i][j] = element;
30            }
31        }
32      
33        // Sort diagonals starting from the second column to the last column
34        for (int startCol = n - 2; startCol > 0; --startCol) {
35            int i = startCol, j = n - 1;
36            std::vector<int> diagonalElements;
37          
38            // Collect elements along the diagonal from (startCol, lastCol)
39            while (i >= 0 && j >= 0) {
40                diagonalElements.push_back(grid[i][j]);
41                i--;
42                j--;
43            }
44          
45            // Sort the collected diagonal elements
46            std::sort(diagonalElements.begin(), diagonalElements.end());
47          
48            // Place sorted elements back into the grid
49            for (int element : diagonalElements) {
50                i++;
51                j++;
52                grid[i][j] = element;
53            }
54        }
55      
56        return grid;
57    }
58};
59
1/**
2 * Sorts each diagonal in the given matrix in non-decreasing order.
3 * @param grid A 2D array (matrix) of numbers.
4 * @returns The matrix with each diagonal sorted in non-decreasing order.
5 */
6function sortMatrix(grid: number[][]): number[][] {
7    const n = grid.length;
8
9    // Process each diagonal going from bottom-left to top-right, excluding the main diagonal
10    for (let k = n - 2; k >= 0; --k) {
11        let i = k, j = 0;
12        const tempDiagonal: number[] = [];
13
14        // Collect all elements of the current diagonal
15        while (i < n && j < n) {
16            tempDiagonal.push(grid[i++][j++]);
17        }
18
19        // Sort the collected diagonal elements
20        tempDiagonal.sort((a, b) => a - b);
21
22        // Write back the sorted elements to the respective diagonal positions
23        for (const value of tempDiagonal) {
24            grid[--i][--j] = value;
25        }
26    }
27
28    // Process each diagonal going from top-right to bottom-left, excluding the main diagonal
29    for (let k = n - 2; k > 0; --k) {
30        let i = k, j = n - 1;
31        const tempDiagonal: number[] = [];
32
33        // Collect all elements of the current diagonal
34        while (i >= 0 && j >= 0) {
35            tempDiagonal.push(grid[i--][j--]);
36        }
37
38        // Sort the collected diagonal elements
39        tempDiagonal.sort((a, b) => a - b);
40
41        // Write back the sorted elements to the respective diagonal positions
42        for (const value of tempDiagonal) {
43            grid[++i][++j] = value;
44        }
45    }
46
47    return grid;
48}
49

Time and Space Complexity

The time complexity of the given code is O(n^2 log n). This is due to the sorting of diagonals in the matrix, where each diagonal can contain up to n elements, and sorting them requires O(n log n) time. As there are n diagonals (both above and below the main diagonal), the total time complexity sums up to O(n^2 log n).

The space complexity is O(n). This is because for each diagonal being processed, we store its elements in a temporary list t, which can contain up to n elements.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More