Matrix Cells in Distance Order — LeetCode 1030 Python Solution
EasyGeometryArrayMathMatrixSorting
- Problem
- #1030
- Pattern
- Matrix and Grid
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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).
Example
- 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]
Python solution
Python
class Solution:
def allCellsDistOrder(
self, rows: int, cols: int, rCenter: int, cCenter: int
) -> List[List[int]]:
q = deque([[rCenter, cCenter]])
vis = [[False] * cols for _ in range(rows)]
vis[rCenter][cCenter] = True
ans = []
while q:
for _ in range(len(q)):
p = q.popleft()
ans.append(p)
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = p[0] + a, p[1] + b
if 0 <= x < rows and 0 <= y < cols and not vis[x][y]:
vis[x][y] = True
q.append([x, y])
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n log n) |
| Space | O(1) to O(n) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1030. Matrix Cells in Distance Order is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
LeetCode 2033Minimum Operations to Make a Uni-Value GridMediumLeetCode 2280Minimum Lines to Represent a Line ChartMediumLeetCode 462Minimum Moves to Equal Array Elements IIMediumLeetCode 539Minimum Time DifferenceMediumLeetCode 628Maximum Product of Three NumbersEasyLeetCode 891Sum of Subsequence WidthsHard
Frequently asked questions
- How hard is LeetCode 1030. Matrix Cells in Distance Order?
- LeetCode 1030. Matrix Cells in Distance Order is rated Easy on LeetCode.
- What topics does LeetCode 1030. Matrix Cells in Distance Order cover?
- LeetCode 1030. Matrix Cells in Distance Order is tagged Geometry, Array, Math, Matrix and Sorting on LeetCode.