Coordinate navigation, spiral unwrapping, and 2D cellular automations
Navigate 2D grids as implicit graphs where each cell (r, c) has up to 4 orthogonal neighbors, using direction arrays [(0,1), (0,-1), (1,0), (-1,0)] and boundary checks.
Core Invariant: Grid = Graph where V = R × C and E ≤ 4 × R × C. Use direction vectors `DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]` to replace 4 repetitive if-statements with a single clean loop.
Grid has arbitrary jump teleports or diagonal movement when only orthogonal is specified.
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
queue = deque()
fresh_count = 0
# 1. Multi-source initialization: find all rotten oranges and count fresh
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_count += 1
if fresh_count == 0:
return 0
minutes = 0
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 2. BFS spreading level by level
while queue and fresh_count > 0:
minutes += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == 1:
grid[nr][nc] = 2 # Infect fresh orange
fresh_count -= 1
queue.append((nr, nc))
return minutes if fresh_count == 0 else -1# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #200 | Number of Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 100% | 64.7% | ||
| #54 | Spiral Matrix ArrayMatrixSimulation | Medium | 100% | 57.2% | ||
| #994 | Rotting Oranges ArrayBreadth-First SearchMatrix | Medium | 100% | 59.0% | ||
| #79 | Word Search ArrayStringBacktrackingDepth-First SearchMatrix | Medium | 100% | 47.7% | ||
| #48 | Rotate Image ArrayMathMatrix | Medium | 100% | 80.4% | ||
| #36 | Valid Sudoku ArrayHash TableMatrix | Medium | 100% | 64.7% | ||
| #221 | Maximal Square ArrayDynamic ProgrammingMatrix | Medium | 100% | 0.5% | ||
| #212 | Word Search II ArrayStringBacktrackingTrieMatrix | Hard | 90% | 38.6% | ||
| #73 | Set Matrix Zeroes ArrayHash TableMatrix | Medium | 89% | 63.3% | ||
| #74 | Search a 2D Matrix ArrayBinary SearchMatrix | Medium | 100% | 54.3% | ||
| #695 | Max Area of Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 100% | 74.1% | ||
| #329 | Longest Increasing Path in a Matrix ArrayDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryTopological SortMemoizationMatrixDirected Acyclic Graph | Hard | 93% | 56.8% | ||
| #37 | Sudoku Solver ArrayHash TableBacktrackingMatrixAlgorithm XDancing Links | Hard | 100% | 65.6% | ||
| #64 | Minimum Path Sum ArrayDynamic ProgrammingMatrix | Medium | 100% | 68.5% | ||
| #827 | Making A Large Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Hard | 90% | 56.9% | ||
| #240 | Search a 2D Matrix II ArrayBinary SearchDivide and ConquerMatrix | Medium | 88% | 57.6% | ||
| #407 | Trapping Rain Water II ArrayBreadth-First SearchHeap (Priority Queue)Matrix | Hard | 100% | 64.1% | ||
| #85 | Maximal Rectangle ArrayDynamic ProgrammingStackMatrixMonotonic Stack | Hard | 83% | 0.6% | ||
| #1293 | Shortest Path in a Grid with Obstacles Elimination ArrayBreadth-First SearchMatrix | Hard | 100% | 46.5% | ||
| #289 | Medium | 100% | 72.8% | |||
| #1091 | Shortest Path in Binary Matrix ArrayBreadth-First SearchMatrix | Medium | 81% | 51.8% | ||
| #417 | Pacific Atlantic Water Flow ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 100% | 61.2% | ||
| #317 | Shortest Distance from All Buildings ArrayBreadth-First SearchMatrix | Hard | 100% | 45.0% | ||
| #130 | Surrounded Regions ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 87% | 45.8% | ||
| #542 | 01 Matrix ArrayDynamic ProgrammingBreadth-First SearchMatrix | Medium | 100% | 54.4% | ||
| #490 | The Maze ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 63% | 60.5% | ||
| #348 | Design Tic-Tac-Toe ArrayHash TableDesignMatrixSimulation | Medium | 100% | 58.8% | ||
| #286 | Walls and Gates ArrayBreadth-First SearchMatrix | Medium | 100% | 64.1% | ||
| #694 | Number of Distinct Islands ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindSortingMatrixHash Function | Medium | 92% | 62.9% | ||
| #733 | Flood Fill ArrayDepth-First SearchBreadth-First SearchMatrix | Easy | 88% | 68.6% | ||
| #498 | Diagonal Traverse ArrayMatrixSimulation | Medium | 100% | 67.3% | ||
| #741 | Cherry Pickup ArrayDynamic ProgrammingMatrix | Hard | 100% | 39.9% | ||
| #378 | Kth Smallest Element in a Sorted Matrix ArrayBinary SearchSortingHeap (Priority Queue)Matrix | Medium | 100% | 0.7% | ||
| #63 | Unique Paths II ArrayDynamic ProgrammingMatrix | Medium | 75% | 0.5% | ||
| #909 | Snakes and Ladders ArrayBreadth-First SearchMatrix | Medium | 63% | 48.2% | ||
| #59 | Spiral Matrix II ArrayMatrixSimulation | Medium | 53% | 75.4% | ||
| #723 | Candy Crush ArrayTwo PointersMatrixSimulation | Medium | 100% | 77.6% | ||
| #296 | Best Meeting Point ArrayMathSortingMatrix | Hard | 100% | 61.5% | ||
| #778 | Swim in Rising Water ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMinimaxHeap (Priority Queue)MatrixDijkstra's Algorithm | Hard | 78% | 68.0% | ||
| #304 | Range Sum Query 2D - Immutable ArrayDesignMatrixPrefix Sum | Medium | 71% | 0.6% | ||
| #174 | Dungeon Game ArrayDynamic ProgrammingMatrix | Hard | 100% | 0.4% | ||
| #1861 | Rotating the Box ArrayTwo PointersMatrix | Medium | 100% | 82.5% | ||
| #311 | Sparse Matrix Multiplication ArrayHash TableMatrixLinear Algebra | Medium | 63% | 69.3% | ||
| #631 | Design Excel Sum Formula ArrayHash TableStringGraph TheoryDesignTopological SortMatrix | Hard | 100% | 39.6% | ||
| #529 | Minesweeper ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 78% | 68.8% | ||
| #1631 | Path With Minimum Effort ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixDijkstra's Algorithm | Medium | 67% | 63.6% | ||
| #463 | Island Perimeter ArrayDepth-First SearchBreadth-First SearchMatrix | Easy | 65% | 74.5% | ||
| #1926 | Nearest Exit from Entrance in Maze ArrayBreadth-First SearchMatrix | Medium | 53% | 48.8% | ||
| #419 | Battleships in a Board ArrayDepth-First SearchMatrix | Medium | 100% | 77.6% | ||
| #885 | Medium | 100% | 84.6% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Coordinate navigation, spiral unwrapping, and 2D cellular automations It is categorized under Trees & Graphs and features 250 curated interview problems across Easy (37), Medium (149), and Hard (64) difficulties.
Companies frequently asking Matrix & Grid Traversal questions include Google, Amazon, Microsoft, Meta, Bloomberg, Uber.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.