Domain 2MediumMEDIUM

Sort the Matrix Diagonally

Sorts each diagonal by grouping elements using column-row difference, sorting them individually in O(MN log(min(m,n))) time, then reconstructing the matrix.

Domain: medium•Updated: 2026-09-14
#hash map#sorting#O(MN log(min(m,n)))#O(MN)]

Problem Breakdown

We are given an m×nm \times n matrix of integers. The goal is to sort every diagonal line (extending from top-left towards bottom-right) in ascending order and return the modified matrix. A “diagonal” consists of cells (i,j)(i, j) where the difference between column index and row index (j−ij - i) remains constant.

Key Observations:

  1. Diagonal Identification: All cells belonging to the same diagonal satisfy col_idx−row_idx=constantcol\_idx - row\_idx = \text{constant}. This invariant uniquely identifies each diagonal line in a rectangular grid.
  2. Input/Output: Input is mat, Output is sorted mat. We can modify the matrix in-place or return a new one; modifying in-place saves space but requires careful reconstruction logic to maintain order.
  3. Constraints: Matrix dimensions up to 100×100100 \times 100. Values are small (≤100\le 100). This allows for standard sorting without needing specialized bucket sort optimizations, though the logic remains efficient regardless of value range.

Edge Cases:

  • Single row or single column: Diagonals reduce to just that line; code should handle naturally via loop ranges.
  • Duplicates in values: Sorting handles duplicates correctly (stable order doesn’t matter for integers).
  • Empty matrix: Constraints say m,n≥1m, n \ge 1, so we don’t need explicit checks for empty input based on constraints, but the logic holds if handled gracefully.

Intuition

A brute force approach might try to sort each diagonal individually by finding all cells belonging to it every time a cell is visited or iterating over start points repeatedly without efficient grouping. This would lead to redundant work and higher complexity (O(MN⋅(min⁡(m,n))2)O(MN \cdot (\min(m,n))^2)).

Key Insight: We can group elements into their respective diagonals using the invariant j−ij - i. By mapping each diagonal (identified by col_idx - row_idx) to a list of values, we extract all data for that line. Once extracted and sorted, we simply write them back in place. Since we iterate through the matrix in standard order (row-major), if we collect elements into lists based on their traversal order (which matches top-to-bottom along diagonals) or use an index tracker during reconstruction, we can restore the values correctly.

Approach

  1. Grouping: Iterate over every cell (r,c)(r, c) of the matrix. Calculate a unique key for each diagonal using c - r. Store all elements belonging to that key in a list within a hash map (dictionary).
  2. Sorting: Once populated, iterate through the values associated with each key and sort them individually. This ensures every diagonal is sorted ascendingly.
  3. Reconstruction: Iterate over the matrix again using row-major order. For each cell (r,c)(r, c), calculate its diagonal key c - r. Retrieve the next smallest value from that diagonal’s sorted list (using a pointer or popping) and place it into mat[r][c].
  4. Return: Return the modified matrix.

Complexity Analysis

  • Time Complexity: O(MNlog⁡(min⁡(m,n)))O(MN \log(\min(m, n))). We visit each cell twice (2MN2MN). Sorting takes time proportional to sum of lengths squared? No, sorting disjoint sets sums up to roughly ∑Lilog⁡Li\sum L_i \log L_i, bounded by total elements times log of max diagonal length. With constraints M,N≤100M,N \le 100, this is extremely fast.
  • Space Complexity: O(MN)O(MN) auxiliary space to store the lists in our hash map and pointers for reconstruction (or output matrix).

Solution

from collections import defaultdict

def diagonalSort(mat):
    m, n = len(mat), len(mat[0])
    
    # Dictionary mapping each diagonal key (col - row) to a list of values.
    diagonals = defaultdict(list)
    
    # Populate the map: iterate over every cell and group by diagonal identifier
    for r in range(m):
        for c in range(n):
            key = c - r  # Diagonal invariant is constant along bottom-right direction
            diagonals[key].append(mat[r][c])
            
    # Sort each collected list of values individually
    for k in diagonals:
        diagonals[k].sort()
        
    # Reconstruct the matrix by placing sorted values back into their original positions.
    # We use a separate index tracker to know where we are within each diagonal's sorted list,
    # as pop(0) is O(L) and while acceptable here, an explicit pointer is cleaner for analysis.
    diag_indices = defaultdict(int) 
    
    for r in range(m):
        for c in range(n):
            key = c - r
            val = diagonals[key][diag_indices[key]]
            mat[r][c] = val
            # Increment the index tracker for this diagonal so next cell gets next value
            diag_indices[key] += 1
            
    return mat

# Example usage:
# print(diagonalSort([[3,3,1,1],[2,2,1,2],[1,1,1,2]])) 

Edge Cases Handled

  • Single Row/Column: The loop ranges handle m=1m=1 or n=1n=1. Diagonals become single cells (sorted trivially) or full rows.
  • Duplicate Values: Standard sorting handles duplicates by maintaining relative order of identical values, which is valid for integers.
  • Large Dimensions within Constraints: With N≤100N \le 100, the hash map approach scales well without hitting memory limits (O(MN)O(MN) space).