Sort Matrix by Diagonals
Source: leetcode
Difficulty: Medium
Tags: array, sorting, matrix

You are given an `n x n` square matrix of integers `grid`. Return the matrix such that:


- The diagonals in the **bottom\-left triangle** (including the middle diagonal) are sorted in **non\-increasing order**.
- The diagonals in the **top\-right triangle** are sorted in **non\-decreasing order**.


 


**Example 1:**



**Input:** grid \= \[\[1,7,3],\[9,8,2],\[4,5,6]]


**Output:** \[\[8,2,3],\[9,6,7],\[4,5,1]]


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/12/29/4052example1drawio.png)


The diagonals with a black arrow (bottom\-left triangle) should be sorted in non\-increasing order:


- `[1, 8, 6]` becomes `[8, 6, 1]`.
- `[9, 5]` and `[4]` remain unchanged.


The diagonals with a blue arrow (top\-right triangle) should be sorted in non\-decreasing order:


- `[7, 2]` becomes `[2, 7]`.
- `[3]` remains unchanged.



**Example 2:**



**Input:** grid \= \[\[0,1],\[1,2]]


**Output:** \[\[2,1],\[1,0]]


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/12/29/4052example2adrawio.png)


The diagonals with a black arrow must be non\-increasing, so `[0, 2]` is changed to `[2, 0]`. The other diagonals are already in the correct order.



**Example 3:**



**Input:** grid \= \[\[1]]


**Output:** \[\[1]]


**Explanation:**


Diagonals with exactly one element are already in order, so no changes are needed.



 


**Constraints:**


- `grid.length == grid[i].length == n`
- `1 <= n <= 10`
- `-105 <= grid[i][j] <= 105`




C++ solution:
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        map<int, vector<pair<int, int>>> diagonals;
        
        for (int k = -(n-1); k <= n-1; ++k) {
            vector<pair<int, int>> cells;
            for (int i = 0; i < n; ++i) {
                int j = i - k;
                if (j >= 0 && j < n) {
                    cells.emplace_back(i, j);
                }
            }
            if (!cells.empty()) {
                diagonals[k] = cells;
            }
        }
        
        for (auto& entry : diagonals) {
            int k = entry.first;
            auto& cells = entry.second;
            vector<int> values;
            for (auto& cell : cells) {
                values.push_back(grid[cell.first][cell.second]);
            }
            if (k >= 0) {
                sort(values.rbegin(), values.rend());
            } else {
                sort(values.begin(), values.end());
            }
            for (int i = 0; i < cells.size(); ++i) {
                int x = cells[i].first;
                int y = cells[i].second;
                grid[x][y] = values[i];
            }
        }
        
        return grid;
    }
};

Go solution:
func sortMatrix(grid [][]int) [][]int {
    n := len(grid)
    diagonals := make(map[int][]int)
    
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            k := i - j
            diagonals[k] = append(diagonals[k], grid[i][j])
        }
    }
    
    for k, list := range diagonals {
        if k >= 0 {
            sort.Slice(list, func(a, b int) bool {
                return list[a] > list[b]
            })
        } else {
            sort.Slice(list, func(a, b int) bool {
                return list[a] < list[b]
            })
        }
        diagonals[k] = list
    }
    
    pos := make(map[int]int)
    for k := range diagonals {
        pos[k] = 0
    }
    
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            k := i - j
            grid[i][j] = diagonals[k][pos[k]]
            pos[k]++
        }
    }
    
    return grid
}

Java solution:
class Solution {
    public int[][] sortMatrix(int[][] grid) {
        int n = grid.length;
        if (n == 0) return grid;
        
        for (int d = 0; d < n; d++) {
            java.util.List<Integer> diagonal = new java.util.ArrayList<>();
            for (int k = 0; d + k < n && k < n; k++) {
                int row = d + k;
                int col = k;
                if (row >= n || col >= n) break;
                diagonal.add(grid[row][col]);
            }
            diagonal.sort(java.util.Collections.reverseOrder());
            int index = 0;
            for (int k = 0; d + k < n && k < n; k++) {
                int row = d + k;
                int col = k;
                if (row >= n || col >= n) break;
                grid[row][col] = diagonal.get(index++);
            }
        }
        
        for (int d = 1; d < n; d++) {
            java.util.List<Integer> diagonal = new java.util.ArrayList<>();
            for (int k = 0; k < n; k++) {
                int row = k;
                int col = d + k;
                if (row >= n || col >= n) break;
                diagonal.add(grid[row][col]);
            }
            java.util.Collections.sort(diagonal);
            int index = 0;
            for (int k = 0; k < n; k++) {
                int row = k;
                int col = d + k;
                if (row >= n || col >= n) break;
                grid[row][col] = diagonal.get(index++);
            }
        }
        
        return grid;
    }
}

JavaScript solution:
var sortMatrix = function(grid) {
    const n = grid.length;
    const diagonals = {};
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const d = i - j;
            const key = d.toString();
            if (!diagonals[key]) diagonals[key] = [];
            diagonals[key].push({ value: grid[i][j], i: i, j: j });
        }
    }
    Object.keys(diagonals).forEach(dStr => {
        const d = parseInt(dStr, 10);
        const entries = diagonals[dStr];
        entries.sort((a, b) => a.i - b.i);
        const values = entries.map(e => e.value);
        if (d >= 0) values.sort((a, b) => b - a);
        else values.sort((a, b) => a - b);
        entries.forEach((entry, idx) => {
            grid[entry.i][entry.j] = values[idx];
        });
    });
    return grid;
};

Python solution:
class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        diag_dict = defaultdict(list)
        
        for i in range(n):
            for j in range(n):
                k = i - j
                diag_dict[k].append((i, j))
        
        for k in diag_dict:
            positions = diag_dict[k]
            values = [grid[i][j] for i, j in positions]
            if k >= 0:
                sorted_values = sorted(values, reverse=True)
            else:
                sorted_values = sorted(values)
            for idx, (i, j) in enumerate(positions):
                grid[i][j] = sorted_values[idx]
        
        return grid

Ruby solution:
def sort_matrix(grid)
  n = grid.size
  return grid if n == 0

  diagonals = Hash.new { |h, k| h[k] = [] }

  n.times do |i|
    n.times do |j|
      d = i - j
      diagonals[d] << [i, j]
    end
  end

  diagonals.each do |d, cells|
    values = cells.map { |i, j| grid[i][j] }

    sorted_values = if d >= 0
                      values.sort.reverse
                    else
                      values.sort
                    end

    cells.each_with_index do |(i, j), idx|
      grid[i][j] = sorted_values[idx]
    end
  end

  grid
end