We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Matrix by Diagonals

Number: 3748

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an n x n square matrix, sort each of its diagonals in one of two ways:

  • For diagonals in the bottom-left triangle (including the main diagonal), sort them in non-increasing order.
  • For diagonals in the top-right triangle, sort them in non-decreasing order. Then, update the matrix with the sorted diagonals.

Key Insights

  • Diagonals in a matrix can be grouped by the value of (row index - column index).
  • If the key (i - j) is non-negative (>= 0), the diagonal belongs to the bottom-left triangle; if it is negative (< 0), the diagonal is in the top-right triangle.
  • Collect each diagonal into a list, sort the list based on the required order, and then reassign the sorted elements back to their respective positions.
  • Process each diagonal independently to keep the solution clear and modular.

Space and Time Complexity

Time Complexity: O(n^2 log n) – Each diagonal (at most n elements) is sorted. Space Complexity: O(n^2) – Extra space is used to store the diagonals in a dictionary.

Solution

The solution involves iterating over each cell in the matrix and grouping elements into diagonals using the key (i - j). For each diagonal:

  • If the key is >= 0 (bottom-left), sort the list in descending order.
  • If the key is < 0 (top-right), sort the list in ascending order. Once sorted, iterate over the matrix again and, based on the same diagonal key, replace the element with the next value from the sorted list. The dictionary of diagonals is used to both gather and then reassign the elements with the sorted order.

Code Solutions

# Python solution
def sortMatrixByDiagonals(grid):
    n = len(grid)
    # Dictionary to store each diagonal's elements with key as (i - j)
    diagonals = {}
    # Step 1: Collect elements for each diagonal
    for i in range(n):
        for j in range(n):
            key = i - j
            if key not in diagonals:
                diagonals[key] = []
            diagonals[key].append(grid[i][j])
    
    # Step 2: Sort each diagonal according to its triangle
    for key in diagonals:
        # Bottom-left triangle: key >= 0, sort in non-increasing order (descending)
        if key >= 0:
            diagonals[key].sort(reverse=True)
        # Top-right triangle: key < 0, sort in non-decreasing order (ascending)
        else:
            diagonals[key].sort()
    
    # Step 3: Write the sorted numbers back into grid
    for i in range(n):
        for j in range(n):
            key = i - j
            # Pop the first element from the sorted list for the diagonal
            grid[i][j] = diagonals[key].pop(0)
    
    return grid

# Example usage:
grid = [[1,7,3],[9,8,2],[4,5,6]]
print(sortMatrixByDiagonals(grid))
← Back to All Questions