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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort the Matrix Diagonally

Difficulty: Medium

Problem Description

Given an m x n matrix of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Key Insights

  • A matrix diagonal starts from the top row or the leftmost column and proceeds downward to the right.
  • Each diagonal can be identified by its starting point, which is either located in the first row or the first column of the matrix.
  • Sorting each diagonal involves collecting elements, sorting them, and placing them back in their original diagonal positions.

Space and Time Complexity

Time Complexity: O(m * n log(min(m, n))) - where m and n are the dimensions of the matrix. Each diagonal can contain at most min(m, n) elements, which need to be sorted.

Space Complexity: O(min(m, n)) - for storing the elements of each diagonal during sorting.

Solution

To solve the problem, we can use the following approach:

  1. Iterate over each starting point in the first row and the first column to identify diagonals.
  2. For each diagonal, collect the elements into a list.
  3. Sort the list of elements.
  4. Place the sorted elements back into their respective diagonal positions in the matrix.

This method uses arrays (lists) for temporary storage of diagonal elements and sorts them using a comparison-based sorting algorithm.

Code Solutions

def diagonalSort(mat):
    from collections import defaultdict
    
    # Dictionary to hold the diagonals
    diagonals = defaultdict(list)
    
    # Collecting elements in diagonals based on their coordinates
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            diagonals[i - j].append(mat[i][j])
    
    # Sorting each diagonal
    for key in diagonals:
        diagonals[key].sort()
    
    # Placing the sorted elements back to their original positions
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            mat[i][j] = diagonals[i - j].pop(0)  # Take the first element from the sorted diagonal
    
    return mat
← Back to All Questions