Sort Matrix Diagonally

Solutions for sorting each diagonal of a matrix.

View on GitHub

Problem

Given an m x n matrix, sort each diagonal in ascending order and return the resulting matrix.

Key Ideas

  • Each diagonal is identified by (row - col).
  • Collect numbers per diagonal, sort once, then rebuild.

Tests

Input:

3 3 1
2 2 1
1 1 1

Output:

1 1 1
1 2 3
1 2 3

Map-based, O(mn log k)

Collect -> sort -> put back.

function diagonalSort(matrix: number[][]) {
  const m = matrix.length;
  const n = matrix[0]?.length ?? 0;


  if (m === 0 || n === 0) return matrix;


  // collect diagonals
  const diagonals = new Map<number, number[]>();


  for (let row = 0; row < m; row++) {
    const row = matrix[row]!;


    for (let col = 0; col < n; col++) {
      const key = row - col;
      const value = row[col]!;
      const diagonal = diagonals.get(key);


      if (diagonal) {
        diagonal.push(value);
      } else {
        diagonals.set(key, [value]);
      }
    }
  }


  // sort descending for easy pop()
  for (const diagonal of diagonals.values()) {
    diagonal.sort((a, b) => b - a);
  }


  // rebuild
  for (let row = 0; row < m; row++) {
    const row = matrix[row]!;


    for (let col = 0; col < n; col++) {
      const key = row - col;
      const diagonal = diagonals.get(key)!;
      const sortedValue = diagonal.pop()!;


      row[col] = sortedValue;
    }
  }


  return matrix;
}

Variants

  • Sort diagonals descending instead of ascending.
  • Only sort upper/lower triangular diagonals.
  • Handle streaming updates (insert new rows dynamically).

Takeaways

  • Diagonal ID = row - col.
  • Collect -> sort -> rebuild.
  • Efficient since each diagonal is sorted once.

Thank you for reading ❤️.

Last updated on

Back to all notes