Matrix Cells in Distance Order Solution In C++/Python/java/JS
Problem Description
Given a rows x cols matrix, we are provided with a starting position (rCenter, cCenter). The task is to return the coordinates of all cells in the matrix, sorted by their Manhattan distance from the center. The Manhattan distance between two points (r1, c1) and (r2, c2) is given by |r1 - r2| + |c1 - c2|. The output should list all cell coordinates in increasing order of distance from (rCenter, cCenter), and multiple valid orderings are possible if they satisfy this condition. Since rows and cols are at most 100, a sorting-based approach is feasible, but an optimized approach using Breadth-First Search (BFS) can achieve better efficiency. This problem is useful in grid-based pathfinding and signal propagation scenarios.
Example
Input 1: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation:
In the first example, the matrix consists of a single row with two columns, and the starting position is at (0,0). The Manhattan distance from (0,0) to itself is 0, while the distance to (0,1) is 1. Since there are only two cells, sorting by distance results in the output [[0,0], [0,1]].
Input 2: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation:
In the second example, the matrix is a 2x2 grid with the center at (0,1). The Manhattan distance from (0,1) to itself is 0, while the distances to (0,0) and (1,1) are both 1, and the distance to (1,0) is 2. Sorting these cells by distance gives one possible valid output [[0,1], [0,0], [1,1], [1,0]], though other orderings with the same distance grouping would also be correct.
Constraints
- 1 <= rows, cols <= 100
- 0 <= rCenter < rows
- 0 <= cCenter < cols
The first thought for solving this problem is to generate all possible cell coordinates in the matrix and compute their Manhattan distance from the given center (rCenter, cCenter). Since the problem requires sorting the cells based on distance, we can store the coordinates along with their distances and then sort them. Given the constraints, an O(n log n) sorting approach is feasible, where n = rows × cols. Another approach is to use Breadth-First Search (BFS), which can process cells in increasing order of distance without sorting, making it more efficient. Since the distance metric follows a layered expansion pattern, BFS ensures cells are visited in the correct order naturally.
Brute Force Approach
Intuition
The problem requires sorting all matrix cells based on their Manhattan distance from a given center. A straightforward way to achieve this is to first generate all possible cell coordinates in the matrix and then calculate their respective distances from (rCenter, cCenter). Since sorting is an efficient and well-optimized operation in most programming languages, we can leverage it to order the cells correctly. Given that the maximum number of cells is 10,000 (100 x 100), sorting them is feasible within the problem's constraints. This approach ensures correctness but can be further optimized using a more structured traversal method like BFS.
Approach
To solve this problem, we first need to generate all possible cell coordinates in the given rows x cols matrix. We can achieve this by iterating through all possible values of r (row index) and c (column index), storing each coordinate as a tuple (r, c). For each of these coordinates, we calculate their Manhattan distance from the given center (rCenter, cCenter) using the formula |r - rCenter| + |c - cCenter|. Since we need to return the cells in order of increasing distance, we store these tuples in a list. At this stage, we have a collection of all possible matrix cells, each associated with its corresponding distance from the center.
Once we have computed the distances for all cells, we sort the list based on the calculated distances. Sorting ensures that cells appear in the required order, from the closest to the farthest. Since Python's built-in sort function uses Timsort, which runs in O(n log n), sorting remains efficient for our problem constraints. After sorting, we extract only the cell coordinates, ignoring the distances, and return them in the correct order. This approach is simple and easy to implement, but its reliance on sorting makes it less optimal than a Breadth-First Search (BFS) approach, which can generate the required order without explicitly sorting the entire list.
Dry Run
Input:
rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2], [0,2], [1,1], [0,1], [1,0], [0,0]]
The output contains all the cells in the matrix, sorted by their Manhattan distance from the center (1,2). The closest cell is the center itself, followed by cells at distance 1, 2, and so on.
The first step is to generate all possible coordinates in a 2x3 matrix. We iterate through all row indices from 0 to 1 and all column indices from 0 to 2, collecting each cell as a coordinate pair (r, c). This results in a complete list of matrix cells: [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]. At this stage, we have all possible matrix positions stored, but they are not yet organized based on their distances from the given center (1,2).
Next, we compute the Manhattan distance for each cell using the formula |r - rCenter| + |c - cCenter|. Applying this formula to each coordinate, we get the distances: (0,0) has a distance of 3, (0,1) has a distance of 2, (0,2) has a distance of 1, (1,0) has a distance of 2, (1,1) has a distance of 1, and (1,2), which is the center itself, has a distance of 0. After computing these distances, we pair each cell with its respective value, resulting in a new list: [(0,0,3), (0,1,2), (0,2,1), (1,0,2), (1,1,1), (1,2,0)]. At this point, the data is structured but still unordered in terms of increasing distance.
After obtaining the distance values, we sort the list of cells based on their computed distances in ascending order. Sorting results in the sequence [(1,2,0), (0,2,1), (1,1,1), (0,1,2), (1,0,2), (0,0,3)], ensuring that the closest cells appear first. Once sorted, we extract only the coordinate pairs, removing the distance values, and return the final ordered list: [[1,2], [0,2], [1,1], [0,1], [1,0], [0,0]]. This guarantees that the cells are arranged according to their proximity to the center, with the closest appearing first and the farthest appearing last.
Final Output: true
The final output is the sorted list of cell coordinates based on their distance from (1,2). The closest cell is the center itself [1,2], followed by [0,2] and [1,1] at distance 1, then [0,1] and [1,0] at distance 2, and finally [0,0] at distance 3. The approach correctly orders all cells as required, but since it involves sorting, it is not the most optimal method.
Code for All Languages
C++
// Matrix Cells in Distance Order - Brute Force Approach CPP
// Function to compute Manhattan distance
int manhattanDistance(int r1, int c1, int r2, int c2) {
return abs(r1 - r2) + abs(c1 - c2);
}
// Comparator function to sort by Manhattan distance
bool compare(pair<int, int> a, pair<int, int> b, int rCenter, int cCenter) {
return manhattanDistance(a.first, a.second, rCenter, cCenter) <
manhattanDistance(b.first, b.second, rCenter, cCenter);
}
// Main function to find all matrix cells sorted by distance
vector<pair<int, int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
vector<pair<int, int>> cells;
// Generate all cells in the matrix
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cells.push_back({i, j});
}
}
// Sort cells based on Manhattan distance from (rCenter, cCenter)
sort(cells.begin(), cells.end(), [&](pair<int, int> a, pair<int, int> b) {
return compare(a, b, rCenter, cCenter);
});
return cells;
}Java
// Matrix Cells in Distance Order - Brute Force Approach Java
// Function to compute Manhattan distance
private static int manhattanDistance(int r1, int c1, int r2, int c2) {
return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}
// Function to get all matrix cells sorted by distance from (rCenter, cCenter)
public static List<int[]> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
List<int[]> cells = new ArrayList<>();
// Generate all cells in the matrix
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cells.add(new int[]{i, j});
}
}
// Sort the cells based on Manhattan distance from (rCenter, cCenter)
cells.sort(Comparator.comparingInt(cell -> manhattanDistance(cell[0], cell[1], rCenter, cCenter)));
return cells;
}Python
# Matrix Cells in Distance Order - Brute Force Approach Python
def manhattan_distance(r1, c1, r2, c2):
"""Compute Manhattan distance between two cells."""
return abs(r1 - r2) + abs(c1 - c2)
def all_cells_dist_order(rows, cols, rCenter, cCenter):
"""Generate all matrix cells and sort them by distance from (rCenter, cCenter)."""
cells = [(r, c) for r in range(rows) for c in range(cols)] # Generate all cells
# Sort cells based on Manhattan distance from (rCenter, cCenter)
cells.sort(key=lambda cell: manhattan_distance(cell[0], cell[1], rCenter, cCenter))
return cellsJavaScript
// Matrix Cells in Distance Order - Brute Force Approach JavaScript
// Function to compute Manhattan distance
function manhattanDistance(r1, c1, r2, c2) {
return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}
// Function to get all matrix cells sorted by distance from (rCenter, cCenter)
function allCellsDistOrder(rows, cols, rCenter, cCenter) {
let cells = [];
// Generate all cells in the matrix
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
cells.push([i, j]);
}
}
// Sort the cells based on Manhattan distance from (rCenter, cCenter)
cells.sort((a, b) =>
manhattanDistance(a[0], a[1], rCenter, cCenter) -
manhattanDistance(b[0], b[1], rCenter, cCenter)
);
return cells;
}Time Complexity - Matrix Cells in Distance Order - O(nlogn)
The brute force approach involves generating all possible matrix cells, computing their Manhattan distances, and then sorting them. Generating all cells takes O(rows × cols) = O(n) time, where n is the total number of cells. Computing the Manhattan distance for each cell is an O(1) operation, so this step also takes O(n) time. However, the dominant step is sorting, which takes O(n log n) due to the comparison-based sorting algorithm. Therefore, the overall time complexity is O(n log n), where n = rows × cols.
Space Complexity - Matrix Cells in Distance Order - O(N)
The space complexity primarily depends on the storage of the matrix cells. Since we store all cells along with their distances before sorting, the space required is O(n), where n is the total number of cells. Additionally, sorting does not require extra space beyond the input array (assuming an in-place sorting algorithm). Thus, the overall space complexity remains O(n).
Bridge between Brute Force and Optimized
The brute force approach for this problem involves generating all matrix cells, calculating their Manhattan distances, and sorting them, which results in an O(n log n) time complexity. While this method is straightforward, sorting introduces unnecessary overhead, making it inefficient for larger matrices. The key observation is that we don’t need to sort explicitly; instead, we can process cells in increasing order of their distances using a more structured approach like BFS (Breadth-First Search). BFS inherently explores cells in layers, ensuring that cells closer to the center are processed first, eliminating the need for sorting.
The transition from brute force to an optimized solution involves recognizing that a level-wise traversal (BFS) or a bucket-sorting approach can help us directly retrieve cells in the correct order without sorting explicitly. By using a queue (BFS) or a bucket array (counting-based approach), we can efficiently store and access cells based on their distances, reducing the time complexity to O(n). This shift significantly improves performance and makes the algorithm scalable for large matrices, bridging the gap between brute force and an optimal approach.
Optimized Approach
Intuition
The brute force approach involves generating all matrix cells, computing their Manhattan distances, and then sorting them. However, this introduces an O(n log n) complexity due to sorting, which is inefficient for larger matrices. Instead of sorting, we can recognize a pattern in how the cells expand outward from the center. The cells that are closer to the center should be processed first, followed by cells that are farther away. This suggests that a level-wise traversal method, such as Breadth-First Search (BFS), can be used to naturally explore cells in the correct order.
By using BFS, we start from the center and expand outward, visiting all cells at the same distance before moving to the next layer. This method eliminates the need for sorting because BFS inherently processes elements in the correct order. Each cell is only processed once, and its neighbors are explored in a structured manner. This insight allows us to achieve an optimized solution with O(n) time complexity, making it much more efficient than the brute-force approach.
Approach
To implement this optimized solution, we initialize a queue (FIFO structure) and insert the center cell as the starting point. We also maintain a visited set to track which cells have already been processed and to avoid revisiting them. From the center, we explore its four possible neighbors (up, down, left, right) and enqueue only those that fall within the matrix bounds and haven’t been visited. This ensures that we process all cells level by level, maintaining the correct distance order without explicitly sorting them.
As we process each cell, we mark it as visited and continue expanding outward until all cells are covered. Since every cell is added to the queue exactly once and dequeued exactly once, the time complexity remains O(n). This method eliminates the overhead of sorting while ensuring an accurate order of traversal, making it the most optimal way to solve the problem efficiently.
Dry Run
Input:
rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2], [0,2], [1,1], [0,1], [1,0], [0,0]]
Steps:
First, we initialize a queue with the center cell (1,2) and mark it as visited. The queue follows a FIFO (First In, First Out) structure, ensuring that the closest cells are processed first. Along with the queue, we maintain a visited set to keep track of already processed cells and prevent duplicates. At this stage, the queue contains only the starting point [(1,2)].
Next, we start processing cells level by level. The first cell dequeued is (1,2), which is the center itself. From here, we explore its four possible neighbors: (0,2), (1,1), (2,2), and (1,3). Among these, (2,2) and (1,3) are out of bounds, so we ignore them. We enqueue (0,2) and (1,1) and mark them as visited. The updated queue now contains [(0,2), (1,1)].
Now, we dequeue (0,2), the next closest cell. Its neighbors are (-1,2), (1,2), (0,1), and (0,3). The cells (-1,2) and (0,3) are out of bounds, and (1,2) is already visited, so we only enqueue (0,1). The queue updates to [(1,1), (0,1)].
Next, we process (1,1). Its neighbors are (0,1), (2,1), (1,0), and (1,2). The cells (1,2) and (0,1) are already visited, and (2,1) is out of bounds, so we enqueue (1,0). The queue now holds [(0,1), (1,0)].
Dequeuing (0,1), we check its neighbors: (-1,1), (1,1), (0,0), and (0,2). The cells (1,1) and (0,2) are already visited, and (-1,1) is out of bounds, so we enqueue (0,0). The queue becomes [(1,0), (0,0)].
Finally, processing (1,0) reveals its neighbors: (0,0), (2,0), (1,-1), and (1,1). The cells (1,1) and (0,0) are already visited, while (2,0) and (1,-1) are out of bounds, so no new elements are added to the queue. The last remaining cell, (0,0), is then dequeued, but all its neighbors are either visited or out of bounds. At this point, the queue is empty, and all cells have been processed.
Final Output: [[1,2], [0,2], [1,1], [0,1], [1,0], [0,0]]
At the end of the BFS traversal, we have visited all matrix cells in the correct order of increasing Manhattan distance. The final output is [[1,2], [0,2], [1,1], [0,1], [1,0], [0,0]]. This result follows the expected order where cells are processed level by level, expanding outward from the center. By using BFS, we avoid sorting and process each cell efficiently, making this an optimal approach with O(n) time complexity.
Cpp
// Matrix Cells in Distance Order - Optimised Approach CPP
vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
// Directions for moving up, down, left, right
vector<vector<int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
// Result vector to store the sorted cell coordinates
vector<vector<int>> result;
// Queue for BFS traversal
queue<pair<int, int>> q;
// Visited matrix to keep track of processed cells
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
// Start from the center cell
q.push({rCenter, cCenter});
visited[rCenter][cCenter] = true;
// BFS traversal
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
// Store the current cell in result
result.push_back({r, c});
// Explore all 4 possible directions
for (auto& dir : directions) {
int newR = r + dir[0];
int newC = c + dir[1];
// Check if the new cell is within bounds and not visited
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && !visited[newR][newC]) {
q.push({newR, newC});
visited[newR][newC] = true;
}
}
}
return result;
}Java
// Matrix Cells in Distance Order - Optimised Approach Java
public static List<int[]> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
// Directions for moving in four directions: right, down, left, up
int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
// List to store the result
List<int[]> result = new ArrayList<>();
// Queue for BFS traversal
Queue<int[]> queue = new LinkedList<>();
// Visited array to track visited cells
boolean[][] visited = new boolean[rows][cols];
// Start BFS from the center cell
queue.offer(new int[]{rCenter, cCenter});
visited[rCenter][cCenter] = true;
// BFS Traversal
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
// Store the current cell in result
result.add(new int[]{r, c});
// Explore all 4 possible directions
for (int[] dir : directions) {
int newR = r + dir[0];
int newC = c + dir[1];
// Check if the new cell is within bounds and not visited
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && !visited[newR][newC]) {
queue.offer(new int[]{newR, newC});
visited[newR][newC] = true;
}
}
}
return result;
}Python
# Matrix Cells in Distance Order - Optimised Approach Python
def allCellsDistOrder(rows, cols, rCenter, cCenter):
# Directions for moving in four directions: right, down, left, up
directions = [(0,1), (1,0), (0,-1), (-1,0)]
# List to store the result
result = []
# Queue for BFS traversal
queue = deque([(rCenter, cCenter)])
# Visited set to track visited cells
visited = set()
visited.add((rCenter, cCenter))
# BFS Traversal
while queue:
r, c = queue.popleft()
# Store the current cell in result
result.append([r, c])
# Explore all 4 possible directions
for dr, dc in directions:
newR, newC = r + dr, c + dc
# Check if the new cell is within bounds and not visited
if 0 <= newR < rows and 0 <= newC < cols and (newR, newC) not in visited:
queue.append((newR, newC))
visited.add((newR, newC))
return result
JavaScript
// Matrix Cells in Distance Order - Optimised Approach JavaScript
function allCellsDistOrder(rows, cols, rCenter, cCenter) {
// Directions for moving in four directions: right, down, left, up
const directions = [[0,1], [1,0], [0,-1], [-1,0]];
// Result array
let result = [];
// Queue for BFS traversal
let queue = [[rCenter, cCenter]];
// Set to track visited cells
let visited = new Set();
visited.add(`${rCenter},${cCenter}`);
// BFS Traversal
while (queue.length > 0) {
let [r, c] = queue.shift();
// Store the current cell in the result
result.push([r, c]);
// Explore all 4 possible directions
for (let [dr, dc] of directions) {
let newR = r + dr, newC = c + dc;
// Check if the new cell is within bounds and not visited
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && !visited.has(`${newR},${newC}`)) {
queue.push([newR, newC]);
visited.add(`${newR},${newC}`);
}
}
}
return result;
}Time Complexity - Matrix Cells in Distance Order - O (n)
The optimized approach utilizes Breadth-First Search (BFS) to traverse the matrix in order of increasing Manhattan distance from the center cell. Since every cell in the matrix is visited exactly once and added to the queue once, the overall time complexity is O(rows × cols). Additionally, each cell is processed in constant time, leading to an efficient traversal. Unlike the brute force approach, which involves sorting, this method avoids an O(N log N) sorting step, making it significantly faster for large matrices.
Space Complexity - Matrix Cells in Distance Order - O (n)
In terms of space, we maintain a queue to store cells to be processed and a set to track visited cells. In the worst case, when the queue holds the majority of the matrix cells (before processing them), it takes up O(rows × cols) space. The final result list also requires O(rows × cols) space to store the output. Therefore, the overall space complexity is O(rows × cols), which is optimal given that we must store all matrix cells in the final output.
Similar Questions
Given a binary matrix, find the distance of each cell from the nearest 0 using BFS. This ensures an efficient O(n) solution without sorting.
Find the water cell that is the farthest from any land cell using multi-source BFS. Returns the maximum distance found.