Sort Matrix Diagonals By Their Values
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an `n x n` matrix of lowercase letters, consider every diagonal that runs from bottom-left to top-right. There are `2n - 1` such diagonals. Assign each diagonal an index from `0` to `2n - 2` in the order you encounter them when scanning starting positions from the bottom row left-to-right, then the left column bottom-to-top excluding the bottom-left cell. Return the diagonal indexes sorted by the string formed from each diagonal's letters.
Function signature:
```python
def sort_diagonal_indexes(matrix: list[list[str]]) -> list[int]:
pass
```
Constraints:
- `1 <= n <= 500`.
- Each cell contains one lowercase English letter.
- If two diagonal strings are equal, sort by smaller diagonal index first.
- The characters in a diagonal are read from bottom-left to top-right.
Examples:
```text
matrix = [['c','a'], ['b','d']]
Diagonals: index 0 -> 'ba', index 1 -> 'd', index 2 -> 'c'
Output: [0, 2, 1]
```
Quick Answer: Practice a matrix diagonal sorting problem that scans bottom-left to top-right diagonals and returns indexes ordered by their diagonal strings. The prompt targets careful indexing, deterministic tie-breaking, and translating a geometric traversal into reliable code.
Return the indexes of all bottom-left to top-right diagonals sorted by the string formed along each diagonal. Ties are broken by diagonal index.
Constraints
- The matrix is square.
- Each cell contains a lowercase letter.
Examples
Input: ([['c','a'],['b','d']])
Expected Output: [0,2,1]
Input: ([['a']])
Expected Output: [0]
Hints
- Generate the start positions in the specified index order.
- Read each diagonal upward and rightward.