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.

Learn more about Math and Sorting patterns.

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 a deque to allow efficient popping from the front. A 2-dimensional list vis 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 the vis 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 the pairwise 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 with 0 <= x < rows and 0 <= 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.
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 the ans list contains them in the order of increasing Manhattan distance. The list ans 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 Evaluator

Example 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 to False.

Queue Starting Cell:

Starting cell (1, 1) is marked as visited in vis and added to q.

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 set ans 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, consuming R * C space.
The queue q, which in the worst case may contain all cells before being dequeued, thus also requiring up to R * C space.
The ans array, which will eventually hold all R * 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know