1030. Matrix Cells in Distance Order
Problem Description
You are tasked with finding the coordinates of all cells in a given matrix, ordered by their distance from a specified center cell. Given four integers (row
, cols
, rCenter
, cCenter
), the problem defines a matrix of size rows x cols
. Your position in the matrix is initially at the cell with coordinates (rCenter, cCenter)
.
The goal is to return a list of coordinates of all cells in the matrix, sorted based on their Manhattan distance from the center cell (rCenter, cCenter)
. The Manhattan distance between two points (r1, c1)
and (r2, c2)
is calculated as |r1 - r2| + |c1 - c2|
. In other words, it's the sum of the absolute differences of their corresponding coordinates.
You have the flexibility to provide the sorted coordinates in any order as long as they are arranged from the nearest to the farthest distance from the center cell.
Intuition
The intuition behind the solution to this problem lies in the properties of the Manhattan distance and an algorithmic technique known as Breadth-First Search (BFS).
Manhattan distance has an interesting property where cells that are an equal distance from a given point form a diamond shape when graphed on the matrix. Since the problem asks us to order the cells by their distance from a center cell, using the BFS algorithm, we can ensure that we process cells in layers - starting with the center cell and moving outwards one distance unit at a time.
Therefore, the approach is to create a queue and start from the center cell, adding it to the queue. We repeatedly take a cell from the front of the queue, add it to our answer list, and then add all its unvisited neighboring cells that are one unit away. To avoid adding the same cell multiple times, we also keep track of all visited cells using a boolean matrix called vis
.
This method ensures that we add cells to our answer list in increasing distance order without explicitly calculating the distance for every cell from the center. Once there are no more cells to add, we have processed the whole matrix, and our answer list contains all cells in the required sorted order.
Solution Approach
The implementation of the solution uses Breadth-First Search (BFS) to explore the matrix starting from the given center. Here's a step-by-step walkthrough explaining how the given Python code achieves this:
-
Initialize Data Structures: A queue
q
is used to store cells for exploration, and it's implemented using adeque
to allow efficient popping from the front. A 2-dimensional listvis
keeps track of visited cells; initially, all cells are marked as unvisited (False
). -
Queue Starting Cell: The starting cell, given by the coordinates
(rCenter, cCenter)
, is added to the queue and marked as visited in thevis
matrix. -
Process Cells in Queue: The algorithm enters a while-loop that continues until the queue is empty. At each step, we process all cells currently in the queue, ensuring that all neighbors one unit away are considered before moving to a larger distance.
-
Explore Neighbors: Within the loop, for each cell
(p)
taken from the queue, its neighbors are determined by iterating over the relative positions represented by(-1, 0, 1, 0, -1)
using thepairwise
function which gives us pairs of relative coordinates for the four directions (up, right, down, left). These are used to calculate the neighboring cells' coordinates(x, y)
. -
Boundary and Visit Checks: Before a neighboring cell is added to the queue, there are two checks:
- Boundary Check: The coordinates
(x, y)
must be inside the matrix, which is checked with0 <= x < rows
and0 <= y < cols
. - Visit Check: The
vis
matrix is checked to ensure the cell has not been visited before. If it hasn't, it is marked as visited.
- Boundary Check: The coordinates
-
Enqueue and Store Results: If a neighbor passes these checks, it is appended to the queue for subsequent exploration and also added to the growing result set
ans
. -
Return Results: After the
while
loop exits (when the queue is empty), it means that all cells have been explored according to their distance from the center, and theans
list contains them in the order of increasing Manhattan distance. The listans
is returned as the final output.
The algorithm efficiently traverses the matrix in a manner that naturally sorts the cells by their Manhattan distance, eliminating the need for an explicit sort operation, and is a classic example of BFS applied to grid traversal problems.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose our matrix size is defined by rows = 3
and cols = 3
, creating a 3x3 grid. The center cell is given by rCenter = 1
and cCenter = 1
. The matrix with Manhattan distance from the center cell looks like this:
1 1 1 1 0 1 1 1 1
Initialization:
- Queue
q
is initialized and contains the starting cell coordinates(1, 1)
. - Visited matrix
vis
is initialized with all values set toFalse
.
Queue Starting Cell:
- Starting cell
(1, 1)
is marked as visited invis
and added toq
.
Process Cells in Queue:
- We begin processing by popping
(1, 1)
from the queue.
Explore Neighbors:
- The neighbors of
(1, 1)
are(1, 0)
,(2, 1)
,(1, 2)
,(0, 1)
.
Boundary and Visit Checks:
- All neighbors are within the boundaries of the matrix and none of them are visited. They are marked as visited and added to the queue
q
.
Enqueue and Store Results:
- The order of neighbors being added to
q
and result setans
may vary, but let's assume they're added in the sequence(1, 0)
,(2, 1)
,(1, 2)
,(0, 1)
.
Return Results:
- The next level of neighbors would be the corners,
(0, 0)
,(0, 2)
,(2, 0)
,(2, 2)
, each with Manhattan distance of 2. - The process continues until all cells have been added to
ans
.
In the end, ans
would look like [(1, 1), (1, 0), (2, 1), (1, 2), (0, 1), (0, 0), (0, 2), (2, 0), (2, 2)]
or any other such sequence that preserves the non-decreasing Manhattan distance order.
This demonstrates how the BFS approach efficiently processes each layer of cells, grouped by their Manhattan distance to the center cell, until all cells have been visited and added to the result in the required sorted order.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def allCellsDistOrder(self, rows: int, cols: int, r_center: int, c_center: int) -> List[List[int]]:
6 # Initialize a queue with the starting cell, which is the center cell
7 queue = deque([[r_center, c_center]])
8 # Create a 2D list to keep track of visited cells
9 visited = [[False] * cols for _ in range(rows)]
10 visited[r_center][c_center] = True
11
12 # List to store the cells in the order of increasing distance from the center
13 result = []
14
15 # Directions for moving up, right, down, and left
16 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
17
18 # Perform a Breadth-First Search (BFS) starting from the center cell
19 while queue:
20 # Dequeue the front cell of the queue
21 current_cell = queue.popleft()
22 result.append(current_cell)
23
24 # Try moving in all four directions from the current cell
25 for delta_row, delta_col in directions:
26 new_row = current_cell[0] + delta_row
27 new_col = current_cell[1] + delta_col
28
29 # Check if the new cell is within grid bounds and hasn't been visited
30 if 0 <= new_row < rows and 0 <= new_col < cols and not visited[new_row][new_col]:
31 # Mark the new cell as visited
32 visited[new_row][new_col] = True
33 # Add the new cell to the queue to explore its neighbors later
34 queue.append([new_row, new_col])
35
36 # Return the cells in the order they were visited
37 return result
38
1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5 // Method to return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter)
6 public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
7 // Initialize a queue to perform the breadth-first search
8 Deque<int[]> queue = new ArrayDeque<>();
9 // Start from the center cell
10 queue.offer(new int[] {rCenter, cCenter});
11
12 // Create a visited matrix to keep track of visited cells
13 boolean[][] visited = new boolean[rows][cols];
14 // Mark the center cell as visited
15 visited[rCenter][cCenter] = true;
16
17 // Create a result array to hold all cells in the required order
18 int[][] result = new int[rows * cols][2];
19 // Use the `dirs` array to explore in all four directions
20 int[] dirs = {-1, 0, 1, 0, -1};
21 // Index to insert the next point in `result`
22 int index = 0;
23
24 // Perform breadth-first search
25 while (!queue.isEmpty()) {
26 for (int size = queue.size(); size > 0; size--) {
27 // Get the current cell from the queue
28 int[] point = queue.poll();
29 // Assign the current cell's coordinates to the result array
30 result[index++] = point;
31
32 // Explore the neighbors of the current cell
33 for (int k = 0; k < 4; ++k) {
34 int x = point[0] + dirs[k], y = point[1] + dirs[k + 1];
35 // Check for valid boundary conditions and unvisited state
36 if (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y]) {
37 // Mark the new cell as visited
38 visited[x][y] = true;
39 // Add new cell's coordinates to the queue
40 queue.offer(new int[] {x, y});
41 }
42 }
43 }
44 }
45 // Return the result array containing all cell coordinates
46 return result;
47 }
48}
49
1#include <vector>
2#include <queue>
3#include <cstring>
4
5class Solution {
6public:
7 vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
8 // Queue to perform BFS
9 queue<pair<int, int>> queue;
10 queue.emplace(rCenter, cCenter); // Start from the center cell
11
12 // Initialize answer vector
13 vector<vector<int>> answer;
14
15 // Visited matrix to keep track of visited cells
16 bool visited[rows][cols];
17 memset(visited, false, sizeof(visited)); // Set all cells to unvisited
18 visited[rCenter][cCenter] = true; // Mark the center cell as visited
19
20 // Array to easily access all 4 surrounding cells (up, right, down, left)
21 int directions[5] = {-1, 0, 1, 0, -1};
22
23 // Perform BFS
24 while (!queue.empty()) {
25 int queueSize = queue.size(); // Number of elements at current level
26 while (queueSize--) {
27 auto [currentRow, currentCol] = queue.front();
28 queue.pop();
29
30 // Add the current cell to the answer
31 answer.push_back({currentRow, currentCol});
32
33 // Explore the neighboring cells
34 for (int k = 0; k < 4; ++k) {
35 int newRow = currentRow + directions[k];
36 int newCol = currentCol + directions[k + 1];
37
38 // Check if the new cell is within bounds and not visited
39 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
40 visited[newRow][newCol] = true; // Mark cell as visited
41 queue.emplace(newRow, newCol); // Add the cell to the queue for further BFS
42 }
43 }
44 }
45 }
46
47 return answer; // Return the cells sorted by their distance from the center
48 }
49};
50
1type Cell = [number, number]; // Defines a type for cells
2
3// Define a function to calculate all cells in distance order
4function allCellsDistOrder(rows: number, cols: number, rCenter: number, cCenter: number): Cell[] {
5 // Queue to perform BFS
6 const queue: Cell[] = [[rCenter, cCenter]];
7
8 // Initialize answer array
9 const answer: Cell[] = [];
10
11 // Visited matrix to keep track of visited cells. Initialize with false values.
12 const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
13
14 // Mark the center cell as visited
15 visited[rCenter][cCenter] = true;
16
17 // Array to easily access all 4 adjacent cells (up, right, down, left)
18 const directions: number[] = [-1, 0, 1, 0, -1];
19
20 // Perform BFS
21 while (queue.length > 0) {
22 const [currentRow, currentCol] = queue.shift()!; // Get the first cell in the queue ! non-null assertion operator since Array.prototype.shift can return `undefined`
23
24 // Add the current cell to the answer
25 answer.push([currentRow, currentCol]);
26
27 // Explore the neighboring cells
28 for (let k = 0; k < 4; k++) {
29 const newRow: number = currentRow + directions[k];
30 const newCol: number = currentCol + directions[k + 1];
31
32 // Check if the new cell is within bounds and not visited
33 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
34 visited[newRow][newCol] = true; // Mark cell as visited
35 queue.push([newRow, newCol]); // Add the cell to the queue for further BFS
36 }
37 }
38 }
39
40 // Return the cells sorted by their distance from the center
41 return answer;
42}
43
Time and Space Complexity
Time Complexity
The given code uses a BFS (Breadth-First Search) approach to traverse the matrix starting from the center cell (rCenter, cCenter)
. For each cell, it checks all four adjacent cells (up, down, left, right), which are represented by the pairwise combinations (-1, 0, 1, 0, -1)
.
The time complexity of this approach is O(R * C)
, where R
is the number of rows and C
is the number of columns in the matrix. This is because each cell is visited exactly once. The check 0 <= x < rows and 0 <= y < cols
happens for 4 neighbors for each of the R * C
cells, but since each neighbor is only enqueued once (guarded by vis[x][y]
), the total number of operations is still proportional to the number of cells.
Space Complexity
The space complexity of the code is also O(R * C)
. The main factors contributing to the space complexity are:
- The
vis
array, which is a 2D array used to keep track of visited cells, consumingR * C
space. - The queue
q
, which in the worst case may contain all cells before being dequeued, thus also requiring up toR * C
space. - The
ans
array, which will eventually hold allR * C
cells in the order they were visited.
Therefore, the space required is proportional to the number of cells in the matrix.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!