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

Number: 1253

Difficulty: Medium

Paid? No

Companies: Amazon, Yandex, Quora

Problem Description

Given an m x n matrix of integers, sort each matrix diagonal in ascending order and return the resulting matrix. A matrix diagonal is defined as the set of elements that start at any element in the top row or leftmost column and extend in the bottom-right direction until reaching the matrix’s end.

Key Insights

  • Diagonals are defined by their starting points in the first row and first column.
  • Each diagonal can be processed independently.
  • Sorting each diagonal in isolation ensures that elements along the same diagonal are in increasing order.
  • The size of each diagonal is determined by the smaller of the remaining row or column counts from the starting point.

Space and Time Complexity

Time Complexity: O(m * n * log(min(m, n))) – each diagonal is sorted independently and its length is at most min(m, n). Space Complexity: O(min(m, n)) – additional space is used to temporarily store the elements of one diagonal.

Solution

The approach involves iterating over every diagonal in the matrix. For each diagonal, we perform the following steps:

  1. Collect all elements along the diagonal into a temporary list.
  2. Sort the list.
  3. Write the sorted elements back along the same diagonal positions. This method efficiently handles each diagonal without additional complex data structures, and the solution leverages simple iteration combined with built-in sort operations.

Code Solutions

def diagonalSort(mat):
    m, n = len(mat), len(mat[0])
    
    # Function that collects, sorts, and writes back a diagonal starting at (row, col)
    def sort_diagonal(row, col):
        diagonal = []
        r, c = row, col
        
        # Collect diagonal elements
        while r < m and c < n:
            diagonal.append(mat[r][c])
            r += 1
            c += 1
        
        # Sort the diagonal elements
        diagonal.sort()
        
        # Write sorted elements back to the matrix
        r, c = row, col
        for num in diagonal:
            mat[r][c] = num
            r += 1
            c += 1

    # Process diagonals starting from each element in the first row
    for col in range(n):
        sort_diagonal(0, col)
    
    # Process diagonals starting from each element in the first column (excluding top-left)
    for row in range(1, m):
        sort_diagonal(row, 0)
    
    return mat

# Example usage:
if __name__ == "__main__":
    matrix = [[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]
    print(diagonalSort(matrix))
← Back to All Questions