Problem Breakdown
We are given an 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 where the difference between column index and row index () remains constant.
Key Observations:
- Diagonal Identification: All cells belonging to the same diagonal satisfy . This invariant uniquely identifies each diagonal line in a rectangular grid.
- Input/Output: Input is
mat, Output is sortedmat. 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. - Constraints: Matrix dimensions up to . Values are small (). 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 , 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 ().
Key Insight: We can group elements into their respective diagonals using the invariant . 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
- Grouping: Iterate over every cell 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). - Sorting: Once populated, iterate through the values associated with each key and sort them individually. This ensures every diagonal is sorted ascendingly.
- Reconstruction: Iterate over the matrix again using row-major order. For each cell , 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 intomat[r][c]. - Return: Return the modified matrix.
Complexity Analysis
- Time Complexity: . We visit each cell twice (). Sorting takes time proportional to sum of lengths squared? No, sorting disjoint sets sums up to roughly , bounded by total elements times log of max diagonal length. With constraints , this is extremely fast.
- Space Complexity: 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 or . 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 , the hash map approach scales well without hitting memory limits ( space).