1030. Matrix Cells in Distance Order LeetCode Solution
In this guide, you will get 1030. Matrix Cells in Distance Order LeetCode Solution with the best time and space complexity. The solution to Matrix Cells in Distance Order problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Matrix Cells in Distance Order
You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).
Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.
The distance between two cells (r1, c1) and (r2, c2) is |r1 – r2| + |c1 – c2|.
Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]
Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
Time Complexity: O(\texttt{rows} \cdot \texttt{cols})
Space Complexity: O(\texttt{rows} \cdot \texttt{cols})
1030. Matrix Cells in Distance Order LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter,
int cCenter) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> ans;
vector<vector<int>> seen(rows, vector<int>(cols));
queue<pair<int, int>> q{{{rCenter, cCenter}}};
seen[rCenter][cCenter] = true;
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
ans.push_back({i, j});
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == rows || y < 0 || y == cols)
continue;
if (seen[x][y])
continue;
seen[x][y] = true;
q.emplace(x, y);
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1030. Matrix Cells in Distance Order LeetCode Solution in Java
class Solution {
public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
List<int[]> ans = new ArrayList<>();
boolean[][] seen = new boolean[rows][cols];
Queue<Pair<Integer, Integer>> q = new LinkedList<>(Arrays.asList(new Pair<>(rCenter, cCenter)));
seen[rCenter][cCenter] = true;
while (!q.isEmpty()) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
ans.add(new int[] {i, j});
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == rows || y < 0 || y == cols)
continue;
if (seen[x][y])
continue;
seen[x][y] = true;
q.offer(new Pair<>(x, y));
}
}
return ans.toArray(int[][] ::new);
}
} // code provided by PROGIEZ
1030. Matrix Cells in Distance Order LeetCode Solution in Python
class Solution:
def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> list[list[int]]:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
ans = []
q = collections.deque([(rCenter, cCenter)])
seen = {(rCenter, cCenter)}
while q:
i, j = q.popleft()
ans.append([i, j])
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == rows or y < 0 or y == cols:
continue
if (x, y) in seen:
continue
seen.add((x, y))
q.append((x, y))
return ans # code by PROGIEZ
