Problem Description

You have a matrix with dimensions rows x cols, and you start at a specific cell located at coordinates (rCenter, cCenter).

Your task is to return a list containing the coordinates of all cells in the matrix, but arranged in a specific order: they must be sorted by their Manhattan distance from your starting position (rCenter, cCenter), from smallest to largest distance.

The Manhattan distance between any two cells (r1, c1) and (r2, c2) is calculated as: |r1 - r2| + |c1 - c2|

For example, if you have a 3x3 matrix and start at position (1, 1) (the center), the cells would be ordered as:

• Distance 0: [1, 1] (the starting cell itself)
• Distance 1: [0, 1], [1, 0], [1, 2], [2, 1] (cells one step away)
• Distance 2: [0, 0], [0, 2], [2, 0], [2, 2] (cells two steps away)

When multiple cells have the same distance from the center, they can be returned in any order as long as all cells with the same distance appear together in the correct distance group.

The solution uses a BFS (Breadth-First Search) approach with a queue. Starting from (rCenter, cCenter), it explores cells layer by layer - first visiting all cells at distance 1, then distance 2, and so on. A visited array tracks which cells have been processed to avoid duplicates. The pairwise function with (-1, 0, 1, 0, -1) generates the four directional movements: up, right, down, and left.

Intuition

When we need to visit all cells sorted by their distance from a starting point, we can think about how distances naturally expand outward like ripples in water. If we drop a stone at (rCenter, cCenter), the ripples would reach cells at distance 1 first, then distance 2, then distance 3, and so on.

This pattern immediately suggests BFS (Breadth-First Search) because BFS explores nodes level by level - it visits all nodes at distance k before visiting any node at distance k+1. This is exactly what we need!

Starting from our center cell, we can think of the problem as exploring a graph where:

• Each cell is a node
• Each cell is connected to its 4 adjacent neighbors (up, down, left, right)
• Moving from one cell to an adjacent cell increases the Manhattan distance by exactly 1

By using BFS with a queue, we naturally process cells in order of increasing distance:

1. Start with the center cell (distance 0)
2. Add all unvisited neighbors (distance 1) to the queue
3. Process all cells at distance 1, adding their unvisited neighbors (distance 2)
4. Continue this pattern until all cells are visited

The key insight is that BFS guarantees we'll visit cells in non-decreasing order of their distance from the starting point. We don't need to explicitly calculate or sort by distances - the BFS traversal order automatically gives us the correct sorting!

We use a vis (visited) array to ensure each cell is added to our result exactly once. The directional movements (-1, 0, 1, 0, -1) paired together give us the four directions: up (-1, 0), right (0, 1), down (1, 0), and left (0, -1).

Learn more about Math and Sorting patterns.

Solution Approach

The implementation uses BFS with a queue to traverse the matrix layer by layer from the center point:

1. Initialization:

• Create a queue q and initialize it with the starting cell [rCenter, cCenter]
• Create a 2D boolean array vis of size rows x cols to track visited cells, initially all False
• Mark the starting cell as visited: vis[rCenter][cCenter] = True
• Create an empty list ans to store the result

2. BFS Traversal:

while q:
    for _ in range(len(q)):  # Process all cells at current distance
        p = q.popleft()       # Get next cell
        ans.append(p)         # Add to result

The outer while loop continues until the queue is empty. The inner for loop processes all cells at the current distance level before moving to the next distance level.

3. Exploring Neighbors:

for a, b in pairwise((-1, 0, 1, 0, -1)):
    x, y = p[0] + a, p[1] + b

The pairwise function with (-1, 0, 1, 0, -1) generates pairs:

• (-1, 0) → move up
• (0, 1) → move right
• (1, 0) → move down
• (0, -1) → move left

For each direction, we calculate the new coordinates (x, y).

4. Boundary Check and Visit:

if 0 <= x < rows and 0 <= y < cols and not vis[x][y]:
    vis[x][y] = True
    q.append([x, y])

For each neighbor:

• Check if it's within matrix bounds
• Check if it hasn't been visited
• If both conditions are met, mark it as visited and add to queue

Why This Works:

BFS naturally processes cells in layers:

• Layer 0: Just the center cell (distance 0)
• Layer 1: All cells one step away (distance 1)
• Layer 2: All cells two steps away (distance 2)
• And so on...

Since each move to an adjacent cell increases Manhattan distance by exactly 1, BFS guarantees we visit cells in order of increasing distance. The vis array prevents revisiting cells, ensuring each cell appears exactly once in the result.

Time Complexity: O(rows × cols) - we visit each cell exactly once Space Complexity: O(rows × cols) - for the visited array and queue

Example Walkthrough

Let's walk through a concrete example with a 3×3 matrix where we start at position (1, 1):

Matrix:
[0,0] [0,1] [0,2]
[1,0] [1,1] [1,2]
[2,0] [2,1] [2,2]

Starting position: (1, 1) - the center cell

Initial Setup:

• Queue: [[1, 1]]
• Visited array: All False except vis[1][1] = True
• Result: []

Round 1 (Distance 0):

• Process [1, 1] from queue
• Add [1, 1] to result
• Check 4 neighbors:
  • Up: (0, 1) - valid, not visited → mark visited, add to queue
  • Right: (1, 2) - valid, not visited → mark visited, add to queue
  • Down: (2, 1) - valid, not visited → mark visited, add to queue
  • Left: (1, 0) - valid, not visited → mark visited, add to queue
• Queue: [[0, 1], [1, 2], [2, 1], [1, 0]]
• Result: [[1, 1]]

Round 2 (Distance 1): Process all 4 cells currently in queue:

1. Process [0, 1]:

   • Add to result
   • Check neighbors: (0, 0) and (0, 2) are unvisited → add to queue

2. Process [1, 2]:

   • Add to result
   • Check neighbors: (0, 2) already visited, (2, 2) unvisited → add to queue

3. Process [2, 1]:

   • Add to result
   • Check neighbors: (2, 0) and (2, 2) - add (2, 0) (2,2 already in queue)

4. Process [1, 0]:

   • Add to result
   • Check neighbors: (0, 0) already in queue, (2, 0) already in queue

• Queue: [[0, 0], [0, 2], [2, 2], [2, 0]]
• Result: [[1, 1], [0, 1], [1, 2], [2, 1], [1, 0]]

Round 3 (Distance 2): Process all 4 corner cells:

• Each cell is processed and added to result
• No new unvisited neighbors (all cells have been visited)
• Queue becomes empty
• Result: [[1, 1], [0, 1], [1, 2], [2, 1], [1, 0], [0, 0], [0, 2], [2, 2], [2, 0]]

Final Result Verification:

• Distance 0: [1, 1] ✓
• Distance 1: [0, 1], [1, 2], [2, 1], [1, 0] ✓
• Distance 2: [0, 0], [0, 2], [2, 2], [2, 0] ✓

The BFS approach naturally groups cells by their Manhattan distance without explicitly calculating distances!

Solution Implementation

Time and Space Complexity

Time Complexity: O(rows * cols)

The algorithm uses BFS (Breadth-First Search) to traverse all cells in the matrix starting from the center position. Each cell is visited exactly once due to the visited array vis. For each cell, we perform constant-time operations:

• Dequeuing from the queue: O(1)
• Appending to the answer list: O(1)
• Checking 4 adjacent cells using pairwise iteration: O(4) = O(1)
• Marking cells as visited and enqueuing: O(1)

Since we visit all rows * cols cells exactly once, the total time complexity is O(rows * cols).

Space Complexity: O(rows * cols)

The space complexity consists of:

• The vis (visited) array: O(rows * cols) to track which cells have been visited
• The queue q: In the worst case, the queue can contain O(rows * cols) elements (though in practice it's much smaller due to BFS level-by-level processing)
• The answer array ans: O(rows * cols) to store all cell coordinates
• The temporary list p and variables: O(1)

The dominant factor is the space needed for the visited array and the answer array, giving us a total space complexity of O(rows * cols).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Processing Cells Level by Level

A critical mistake is forgetting to process all cells at the current distance before moving to the next distance level. Without the inner loop that processes len(queue) cells, the BFS would mix cells from different distances:

Incorrect Implementation:

while queue:
    current_cell = queue.popleft()
    result.append(current_cell)
    # Add neighbors to queue...

This would process cells in the order they're added to the queue, not strictly by distance layers.

Correct Implementation:

while queue:
    level_size = len(queue)
    for _ in range(level_size):  # Process all cells at current distance
        current_cell = queue.popleft()
        result.append(current_cell)
        # Add neighbors to queue...

2. Marking Cells as Visited After Dequeuing

A common BFS mistake is marking cells as visited when they're dequeued rather than when they're enqueued. This causes duplicate cells in the queue:

Incorrect Pattern:

while queue:
    current_cell = queue.popleft()
    if visited[current_cell[0]][current_cell[1]]:
        continue
    visited[current_cell[0]][current_cell[1]] = True  # Too late!
    result.append(current_cell)

This allows the same cell to be added to the queue multiple times from different neighbors, leading to:

• Duplicate cells in the result
• Inefficient processing
• Potentially incorrect ordering

Correct Pattern:

if not visited[new_row][new_col]:
    visited[new_row][new_col] = True  # Mark immediately when adding
    queue.append([new_row, new_col])

3. Using Wrong Distance Calculation

Some might try to optimize by calculating actual Manhattan distances and sorting, which is unnecessary and error-prone:

Overcomplicated Approach:

all_cells = []
for r in range(rows):
    for c in range(cols):
        dist = abs(r - rCenter) + abs(c - cCenter)
        all_cells.append((dist, [r, c]))
all_cells.sort()
return [cell for _, cell in all_cells]

While this works, it's less efficient (O(n log n) sorting) and doesn't leverage the natural ordering that BFS provides.

4. Incorrect Direction Arrays

Using inconsistent or incorrect direction arrays can miss cells or cause index errors:

Common Mistakes:

# Mistake 1: Only 2 directions
directions = [(0, 1), (1, 0)]  # Missing up and left

# Mistake 2: Diagonal movements (wrong for Manhattan distance)
directions = [(1, 1), (-1, -1), (1, -1), (-1, 1)]

# Mistake 3: Typos in coordinates
directions = [(1, 0), (0, 1), (-1, 0), (0, 1)]  # Duplicate (0,1)

Correct Implementation:

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # All 4 cardinal directions