Sort Matrix Diagonals By Their Values

Problem Statement

You are given an m x n matrix of lowercase English letters. Each anti-diagonal runs from bottom-left to top-right across the matrix. There are m + n - 1 such diagonals, uniquely identified by index k = r + c for 0 <= k < m + n - 1.

For each diagonal index k:

1. Collect characters along the diagonal starting from the bottom-left-most cell (largest row index r) and moving upward and rightward to the top-right-most cell (smallest row index r).
2. Concatenate these characters into a single string.

Return the list of diagonal indices k sorted lexicographically by their resulting diagonal strings. If two diagonals produce the exact same string, break the tie by sorting the diagonal indices k in ascending numerical order.

Function Signature

def sort_matrix_diagonals(matrix: list[list[str]]) -> list[int]:
    pass

Examples

Example 1

matrix = [
  ["b", "a"],
  ["a", "b"]
]

Output: [1, 0, 2]

Explanation:

• Diagonal k = 0: cell (0, 0) -> "b"
• Diagonal k = 1: cells (1, 0), (0, 1) -> "aa"
• Diagonal k = 2: cell (1, 1) -> "b"

Strings by index: 0: "b", 1: "aa", 2: "b". Lexicographical order gives "aa" first (index 1). Diagonals 0 and 2 both produce "b", so the tie is broken by index in ascending order (0 before 2). Result: [1, 0, 2].

Example 2

matrix = [
  ["c", "a", "t"],
  ["d", "o", "g"],
  ["e", "l", "m"]
]

Output: [0, 1, 2, 3, 4]

Explanation:

• k = 0: (0, 0) -> "c"
• k = 1: (1, 0), (0, 1) -> "da"
• k = 2: (2, 0), (1, 1), (0, 2) -> "eot"
• k = 3: (2, 1), (1, 2) -> "lg"
• k = 4: (2, 2) -> "m"

Alphabetical sort of strings: "c" (0), "da" (1), "eot" (2), "lg" (3), "m" (4).

Constraints

• m == len(matrix)
• n == len(matrix[0])
• 1 <= m, n <= 500
• 1 <= m * n <= 10^5
• matrix[i][j] is a single lowercase English letter ('a'–'z').