Katkat
Back

Sort Every Concentric Matrix Border Clockwise

Capital OneSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests array traversal, boundary management, and sorting logic by requiring you to isolate concentric layers of a matrix and sort their contents independently.

Problem Statement

Given an m x n integer matrix, perform a "layer-wise sort." A layer is defined as the outer border of the matrix. Once you peel off the outermost border, the next inner layer is the border of the remaining matrix. For each concentric layer:

  1. Extract all elements belonging to that layer.
  2. Sort these elements in ascending order.
  3. Place the sorted elements back into the same layer positions, starting from the top-left cell of the layer and proceeding in a clockwise direction.

Function Signature

def sort_matrix_layers(matrix: List[List[int]]) -> List[List[int]]

Examples

Example 1: Input:

[[9, 8, 7],
 [6, 5, 4],
 [3, 2, 1]]

Outer layer values: [9, 8, 7, 4, 1, 2, 3, 6]. Sorted: [1, 2, 3, 4, 6, 7, 8, 9]. Output:

[[1, 2, 3],
 [8, 5, 4],
 [9, 6, 7]]

Example 2: Input: [[1, 2], [3, 4]] Output: [[1, 2], [3, 4]]

Constraints

  • m, n are between 1 and 100.
  • Matrix elements are integers.
  • Handle cases where layers collapse into a single row or column (e.g., a 1xN or Nx1 matrix).

Hints

Hint 1

Identify the boundaries (top, bottom, left, right) for each layer using nested loops or recursion.

Hint 2

Extract the layer elements in clockwise order: top row, right column, bottom row (reversed), then left column (reversed), ensuring you don't double-count corners.

Hint 3

Use a list to store extracted elements, sort it, and then re-traverse the same boundary coordinates to overwrite the matrix with sorted values.

Follow-up questions

  • How would your approach change if you needed to sort layers in counter-clockwise order?
  • What is the time complexity of your solution in terms of total elements N?
  • How would you optimize the space complexity if the matrix was read-only and you had to return a new matrix?