3446. Sort Matrix by Diagonals

Description

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:

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:

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

 

Solutions

Solution: Simulation

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
const sortMatrix = function (grid) {
  const n = grid.length;
  const matrixMap = new Map();

  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      const pos = row - col;

      if (!matrixMap.has(pos)) {
        matrixMap.set(pos, []);
      }

      matrixMap.get(pos).push(grid[row][col]);
    }
  }

  for (const [pos, values] of matrixMap) {
    values.sort((a, b) => (pos >= 0 ? a - b : b - a));
  }

  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      const pos = row - col;
      const values = matrixMap.get(pos);

      grid[row][col] = values.pop();
    }
  }

  return grid;
};