Problem Description

You are given an n x n square matrix of integers called grid. Your task is to sort the elements along the diagonals of this matrix according to specific rules and return the modified matrix.

The matrix needs to be sorted as follows:

1. Bottom-left triangle (including the main diagonal): All diagonals in this region should be sorted in non-increasing order (from largest to smallest as you move along each diagonal).

2. Top-right triangle: All diagonals in this region should be sorted in non-decreasing order (from smallest to largest as you move along each diagonal).

To clarify the regions:

• The bottom-left triangle includes all positions (i, j) where i >= j (row index is greater than or equal to column index)
• The top-right triangle includes all positions (i, j) where i < j (row index is less than column index)
• The main diagonal (where i == j) belongs to the bottom-left triangle

For example, in a 3x3 matrix:

• The bottom-left triangle consists of positions: (0,0), (1,0), (1,1), (2,0), (2,1), (2,2)
• The top-right triangle consists of positions: (0,1), (0,2), (1,2)

Each diagonal should be sorted independently. A diagonal is a line of elements where the difference between row and column indices remains constant. After sorting all diagonals according to their respective rules, return the resulting matrix.

Intuition

The key insight is to recognize that we need to process diagonals independently, and each diagonal can be identified by a unique pattern. In any diagonal, as we move from one element to the next, both the row index and column index increase by 1. This means elements (i, j), (i+1, j+1), (i+2, j+2), etc., all belong to the same diagonal.

For the bottom-left triangle, we can start from each element in the leftmost column (where j = 0) and traverse diagonally upward and to the right. Each starting position (k, 0) where k ranges from n-1 down to 0 gives us a different diagonal. As we collect elements along each diagonal, we can sort them and then place them back in reverse order (using pop()) to achieve non-increasing order.

For the top-right triangle, we can start from each element in the rightmost column (where j = n-1) and traverse diagonally upward and to the left. Each starting position (k, n-1) where k ranges from n-2 down to 1 gives us a different diagonal. We collect elements, sort them, and place them back in reverse order to achieve non-decreasing order when traversing from top-right to bottom-left.

The reason we use pop() after sorting is clever: when we sort the array in ascending order and then pop elements (which removes from the end), we get elements in descending order. This works perfectly for the bottom-left triangle where we want non-increasing order. For the top-right triangle, since we're traversing in the opposite direction (from bottom-right to top-left), popping sorted elements also gives us the desired non-decreasing order when read from top-right to bottom-left.

The solution elegantly handles the main diagonal as part of the bottom-left triangle processing, avoiding any special cases or duplicate processing.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a simulation approach with sorting, processing diagonals in two phases:

Phase 1: Process Bottom-Left Triangle (including main diagonal)

We iterate through starting positions along the left column, from bottom to top using k from n-2 down to -1:

• For each k, we start at position (k, 0)
• Initialize empty list t to collect diagonal elements
• Traverse diagonally using i and j, where both increment by 1 in each step
• Continue while both i < n and j < n to stay within bounds
• Collect all elements along this diagonal into list t

After collecting elements:

• Sort t in ascending order using t.sort()
• Reset to starting position (k, 0)
• Traverse the same diagonal again
• Place elements back using t.pop(), which removes elements from the end
• Since t is sorted ascending and we're popping from the end, we place elements in descending order along the diagonal

Phase 2: Process Top-Right Triangle

We iterate through starting positions along the right column, from second-to-last row down to first row using k from n-2 down to 1:

• For each k, we start at position (k, n-1)
• Initialize empty list t to collect diagonal elements
• Traverse diagonally using i and j, where both decrement by 1 in each step
• Continue while both i >= 0 and j >= 0 to stay within bounds
• Collect all elements along this diagonal into list t

After collecting elements:

• Sort t in ascending order using t.sort()
• Reset to starting position (k, n-1)
• Traverse the same diagonal again (from bottom-right to top-left)
• Place elements back using t.pop()
• Since we're traversing from bottom-right to top-left and popping sorted elements, the diagonal ends up in non-decreasing order when read from top-left to bottom-right

Time Complexity: O(n² log n) - We visit each element twice (once to collect, once to place back), and sorting each diagonal takes O(m log m) where m is the diagonal length. In the worst case, the main diagonal has n elements.

Space Complexity: O(n) - The temporary list t can hold at most n elements (for the main diagonal).

The solution modifies the grid in-place and returns it after all diagonals have been properly sorted according to their region's requirements.

Example Walkthrough

Let's walk through a small 3×3 example to illustrate the solution approach.

Initial Grid:

grid = [[3, 9, 4],
        [7, 2, 8],
        [5, 6, 1]]

Phase 1: Process Bottom-Left Triangle (including main diagonal)

We start with k = 1 (n-2), then k = 0, then k = -1.

When k = 1:

• Start at position (1, 0) which has value 7
• Traverse diagonally: (1,0) → (2,1)
• Collect elements: t = [7, 6]
• Sort t: [6, 7]
• Place back using pop():
  • Position (1,0) gets t.pop() = 7
  • Position (2,1) gets t.pop() = 6
• Grid remains: [[3,9,4], [7,2,8], [5,6,1]]

When k = 0:

• Start at position (0, 0) which has value 3
• Traverse diagonally: (0,0) → (1,1) → (2,2)
• Collect elements: t = [3, 2, 1]
• Sort t: [1, 2, 3]
• Place back using pop():
  • Position (0,0) gets t.pop() = 3
  • Position (1,1) gets t.pop() = 2
  • Position (2,2) gets t.pop() = 1
• Grid becomes: [[3,9,4], [7,2,8], [5,6,1]]

When k = -1:

• Start at position (-1, 0) which is out of bounds
• When adjusted: start at (0, 1) after incrementing both i and j
• Traverse diagonally: (0,1) → (1,2)
• But wait, (0,1) is in the top-right triangle, not bottom-left
• Actually, this diagonal only has position (2,0) = 5 in the bottom-left region
• Since it's a single element, sorting doesn't change it
• Grid remains: [[3,9,4], [7,2,8], [5,6,1]]

Actually, let me reconsider the traversal pattern. Looking at the code more carefully:

When k = 1:

• Start at (1, 0), traverse to (2, 1)
• Elements: [7, 6] → sorted: [6, 7] → placed back as [7, 6]

When k = 0:

• Start at (0, 0), traverse to (1, 1), then (2, 2)
• Elements: [3, 2, 1] → sorted: [1, 2, 3] → placed back as [3, 2, 1]

When k = -1:

• Start would be at (-1, 0), but after incrementing, we start at (0, 1)
• This is actually processing a different diagonal in the top section, so nothing happens here for bottom-left

After Phase 1: [[3,9,4], [7,2,8], [5,6,1]]

Phase 2: Process Top-Right Triangle

We process k = 1 (since k goes from n-2 down to 1).

When k = 1:

• Start at position (1, 2) which has value 8
• Traverse diagonally backwards: (1,2) → (0,1)
• Collect elements: t = [8, 9]
• Sort t: [8, 9]
• Place back using pop():
  • Position (1,2) gets t.pop() = 9
  • Position (0,1) gets t.pop() = 8
• Grid becomes: [[3,8,4], [7,2,9], [5,6,1]]

Now we need to process the remaining diagonal in top-right:

• The diagonal containing just (0,2) = 4 remains unchanged (single element)

Final Result:

grid = [[3, 8, 4],
        [7, 2, 9],
        [5, 6, 1]]

Let's verify:

• Bottom-left diagonals (read along each diagonal):
  • (2,0): [5] - trivially sorted ✓
  • (1,0)→(2,1): [7, 6] - non-increasing ✓
  • (0,0)→(1,1)→(2,2): [3, 2, 1] - non-increasing ✓
• Top-right diagonals (read along each diagonal):
  • (0,1)→(1,2): [8, 9] - non-decreasing ✓
  • (0,2): [4] - trivially sorted ✓

The solution correctly sorts each diagonal according to its region's requirements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2 log n), and the space complexity is O(n).

Time Complexity Analysis:

• The code processes diagonals of the matrix in two separate loops
• First loop: processes diagonals starting from the leftmost column (from row n-2 to row 0)
• Second loop: processes anti-diagonals starting from the rightmost column (from row n-2 to row 1)
• For each diagonal/anti-diagonal:
  • Collecting elements takes O(d) time where d is the diagonal length
  • Sorting takes O(d log d) time
  • Placing sorted elements back takes O(d) time
• The longest diagonal has length n, and there are approximately 2n diagonals total
• The sum of all diagonal lengths is approximately n^2
• The dominant operation is sorting, giving us: Σ(d log d) for all diagonals
• Since the maximum diagonal length is n and we process O(n) diagonals with average length O(n), the total complexity is O(n^2 log n)

Space Complexity Analysis:

• The temporary array t stores elements from one diagonal at a time
• The maximum diagonal length is n (the main diagonal)
• Therefore, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Diagonal Coverage

Pitfall: The current implementation doesn't correctly cover all diagonals in the matrix. It processes diagonals starting from the left edge (column 0) and bottom edge (row n-1), but this misses several important diagonals and incorrectly processes others.

Issues:

• The first loop starts from row n-2 and column 0, missing the bottom-left corner diagonal starting at (n-1, 0)
• The second loop processes diagonals from the bottom edge instead of the right edge, which doesn't align with the top-right triangle requirement
• Some diagonals in the top-right triangle are never processed

Solution: Process diagonals systematically by their starting positions:

• For bottom-left triangle: Start from the left edge (column 0) and then the bottom edge
• For top-right triangle: Start from the top edge (row 0) excluding the top-left corner

2. Incorrect Sorting Direction Application

Pitfall: The code uses pop() to place elements in descending order for both regions, but the top-right triangle should be in ascending order.

Issues:

• The second phase incorrectly places elements in descending order when it should place them in ascending order
• The traversal direction and popping strategy don't align with the required sorting order

Solution: Use different placement strategies for each region:

• Bottom-left: Use pop() to place in descending order
• Top-right: Use index-based placement or pop(0) to place in ascending order

Corrected Implementation:

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
      
        # Process bottom-left triangle (including main diagonal)
        # Start from left edge (column 0)
        for start_row in range(n):
            row, col = start_row, 0
            diagonal_values = []
          
            # Collect diagonal elements
            while row < n and col < n and row >= col:  # Stay in bottom-left triangle
                diagonal_values.append(grid[row][col])
                row += 1
                col += 1
          
            # Sort and place back in descending order
            diagonal_values.sort()
            row, col = start_row, 0
            while row < n and col < n and row >= col:
                grid[row][col] = diagonal_values.pop()  # Pop gives largest first
                row += 1
                col += 1
      
        # Process bottom-left triangle diagonals starting from bottom edge
        for start_col in range(1, n):
            row, col = n - 1, start_col
            diagonal_values = []
          
            # Collect diagonal elements
            while row >= 0 and col < n and row >= col:
                diagonal_values.append(grid[row][col])
                row -= 1
                col += 1
          
            # Sort and place back in descending order
            diagonal_values.sort()
            row, col = n - 1, start_col
            while row >= 0 and col < n and row >= col:
                grid[row][col] = diagonal_values.pop()
                row -= 1
                col += 1
      
        # Process top-right triangle
        # Start from top edge (row 0), excluding (0,0)
        for start_col in range(1, n):
            row, col = 0, start_col
            diagonal_values = []
          
            # Collect diagonal elements
            while row < n and col < n:
                diagonal_values.append(grid[row][col])
                row += 1
                col += 1
          
            # Sort and place back in ascending order
            diagonal_values.sort()
            row, col = 0, start_col
            idx = 0
            while row < n and col < n:
                grid[row][col] = diagonal_values[idx]  # Place in ascending order
                row += 1
                col += 1
                idx += 1
      
        # Process top-right triangle diagonals starting from right edge
        for start_row in range(1, n - 1):
            row, col = start_row, n - 1
            diagonal_values = []
          
            # Collect diagonal elements
            while row < n and col >= 0 and row < col:
                diagonal_values.append(grid[row][col])
                row += 1
                col -= 1
          
            # Sort and place back in ascending order
            diagonal_values.sort()
            row, col = start_row, n - 1
            idx = 0
            while row < n and col >= 0 and row < col:
                grid[row][col] = diagonal_values[idx]
                row += 1
                col -= 1
                idx += 1
      
        return grid