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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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.

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

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:

11 1 1
21 0 1
31 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

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1030. Matrix Cells in Distance Order

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings