Sort Every Concentric Matrix Border Clockwise
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
## Problem
For each concentric border of a rectangular integer matrix, sort that border's values in ascending order and write them back clockwise starting at the border's top-left cell. Process every valid border through the center and return the transformed matrix.
### Function Contract
Implement `sort_matrix_borders(matrix) -> list[list[int]]`. Do not mutate the input.
### Constraints
- `1 <= rows, columns <= 200` and all rows have equal length.
- Border `k` has top row `k`, bottom row `rows-1-k`, left column `k`, and right column `columns-1-k`.
- Clockwise order is top left-to-right, right top-to-bottom, bottom right-to-left, then left bottom-to-top, without visiting a cell twice.
- A one-row or one-column center is one border vector.
### Examples
- `[[4,3],[2,1]]` returns `[[1,2],[4,3]]` because clockwise cells are top-left, top-right, bottom-right, bottom-left.
- A one-row matrix is returned as that row sorted ascending.
```hint Enumerate coordinates first
Generate each border's coordinate sequence once, collect and sort its values, then zip the sorted values back to those coordinates.
```
### Edge Cases
- Odd dimensions can leave one center cell.
- A rectangular center may be a one-row or one-column vector.
- Duplicates and negative values retain their multiplicities.
Overview: Sort the values on every concentric border of a rectangular matrix and write them back clockwise from each border's top-left cell. Traverse corners exactly once, preserve interior layer boundaries, handle single-row or single-column centers, and leave the input unchanged.
Read the full ByteDance Software Engineer interview experience this question came from
For every concentric border of a nonempty rectangular integer matrix, sort that border's values in ascending order and write them back clockwise beginning at the border's top-left cell. Clockwise order is the top edge left to right, right edge top to bottom, bottom edge right to left, and left edge bottom to top, without visiting a cell twice. Process all valid borders through the center and return a transformed copy without mutating the input. A one-row or one-column center is one border vector.
Constraints
- 1 <= rows, columns <= 200, and all rows have equal length.
- Border k uses top row k, bottom row rows - 1 - k, left column k, and right column columns - 1 - k.
- Clockwise traversal never visits a border cell twice.
- A one-row or one-column center is one border vector.
- Do not mutate the input matrix.
Examples
Input: ([[4, 3], [2, 1]],)
Expected Output: [[1, 2], [4, 3]]
Explanation: This is the source example; sorted values are written in clockwise border order.
Input: ([[3, 1, 2]],)
Expected Output: [[1, 2, 3]]
Explanation: A one-row matrix is one border vector sorted left to right.
Hints
- Generate each border's clockwise coordinate sequence before collecting values.
- Sort the collected values, then pair them with coordinates in sequence order.