Sort Every Concentric Matrix Border Clockwise
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Sort Every Concentric Matrix Border Clockwise
Given a nonempty rectangular integer matrix, process each concentric layer independently.
For a layer, list its coordinates clockwise starting at that layer's top-left cell. Sort the values from that border in ascending order, then write them back along the same clockwise coordinate order. Return the transformed matrix.
The innermost layer may be a single row, a single column, or one cell. Every matrix cell belongs to exactly one layer.
## Function Signature
```python
def sort_matrix_borders(matrix: list[list[int]]) -> list[list[int]]:
...
```
## Constraints
- `1 <= len(matrix) <= 200`
- `1 <= len(matrix[0]) <= 200`
- Every row has the same length.
- `-1_000_000_000 <= matrix[r][c] <= 1_000_000_000`
## Example
```text
Input:
[[9, 8, 7],
[6, 5, 4],
[3, 2, 1]]
Output:
[[1, 2, 3],
[9, 5, 4],
[8, 7, 6]]
```
The outer values are written in ascending order along the clockwise path from the top-left cell; the center cell forms its own layer.
Quick Answer: Sort the values on each concentric border of a rectangular matrix, then write them back clockwise from the layer's top-left cell. The exercise tests precise coordinate traversal and edge cases where an inner layer collapses to a row, column, or single cell.
Given a nonempty rectangular integer matrix, process each concentric layer (border ring) independently and return the transformed matrix.
Layer `k` consists of every cell on the border of the sub-matrix with corners `(k, k)` and `(rows - 1 - k, cols - 1 - k)`. Every cell of the matrix belongs to exactly one layer, and each cell appears exactly once in its layer's traversal.
For each layer:
1. List the layer's coordinates **clockwise, starting at that layer's top-left cell** `(k, k)`:
- top row left to right, then right column top to bottom (excluding the top-right corner already visited), then bottom row right to left (excluding the bottom-right corner), then left column bottom to top (excluding both the bottom-left and the top-left corners);
- if the layer is a **single row**, its order is simply left to right;
- if the layer is a **single column**, its order is simply top to bottom.
2. Read the values along that coordinate list and sort them in **ascending** order.
3. Write the sorted values back along the **same** clockwise coordinate list.
The innermost layer may be a single row, a single column, or a single cell. Layers are independent: values never move between layers.
## Function Signature
```python
def sort_matrix_borders(matrix: list[list[int]]) -> list[list[int]]:
...
```
## Example 1
```text
Input:
[[9, 8, 7],
[6, 5, 4],
[3, 2, 1]]
Output:
[[1, 2, 3],
[9, 5, 4],
[8, 7, 6]]
```
The outer border read clockwise from (0, 0) is [9, 8, 7, 4, 1, 2, 3, 6]; sorted ascending it becomes [1, 2, 3, 4, 6, 7, 8, 9], written back along the same clockwise path. The center cell 5 forms its own single-cell layer and stays in place.
## Example 2
```text
Input:
[[7, -1, 4, 4],
[0, 9, -3, 2]]
Output:
[[-3, -1, 0, 2],
[9, 7, 4, 4]]
```
A 2 x 4 matrix has a single layer covering all eight cells. Clockwise from (0, 0) the values read [7, -1, 4, 4, 2, -3, 9, 0]; sorted they are [-3, -1, 0, 2, 4, 4, 7, 9] and are written back along the same path (top row left to right, then bottom row right to left).
The output is fully determined: exactly one result matrix is correct for any input.
Constraints
- 1 <= rows <= 200
- 1 <= cols <= 200
- Every row has the same length (the matrix is rectangular).
- -10^9 <= matrix[r][c] <= 10^9
- The matrix is nonempty: it always has at least one row and one column.
Examples
Input: ([[9, 8, 7], [6, 5, 4], [3, 2, 1]],)
Expected Output: [[1, 2, 3], [9, 5, 4], [8, 7, 6]]
Explanation: Post example: the 3x3 outer ring sorts clockwise from (0,0); the center cell 5 is its own layer.
Input: ([[5]],)
Expected Output: [[5]]
Explanation: Single-cell matrix: the only layer holds one value, so the matrix is unchanged.
Hints
- Layer k is bounded by top = left = k and bottom = rows - 1 - k, right = cols - 1 - k; there are (min(rows, cols) + 1) // 2 layers in total.
- Generate the clockwise coordinate list once per layer, read the values through it, sort them, then write them back through the very same list — the traversal order is the whole contract.
- Treat a single-row or single-column layer as a special case so no cell is visited twice.