โ† OYO questions

Reach matrix boundary with color transition rules

Filed under OYO

Free read 2 of 3

Verify movement rules and confirm whether reaching any edge cell immediately returns true.

The question

Given an m x n matrix containing 'B' (Black), 'W' (White), and 'U' (Uncolored), starting at a given coordinate (i, j), determine if you can reach any boundary of the matrix. Movement is allowed in 4 directions. Transition rules: from 'B' go only to 'B' or 'U'; from 'W' go only to 'W' or 'U'; from 'U' go to any color.

Constraints

  • Matrix dimensions m, n <= 500
  • Valid cell values are strictly 'B', 'W', or 'U'

Examples

Input
matrix = [['B', 'U'], ['W', 'W']], start = (0, 0)
Output
True
Why
Can move from (0,0) 'B' to (0,1) 'U' which is on the boundary.

Approach

  1. Verify movement rules and confirm whether reaching any edge cell immediately returns true.

Solution

O(m * n) time, O(m * n) space

Python
from collections import deque
def can_reach_boundary(matrix, start):
    m, n = len(matrix), len(matrix[0])
    si, sj = start
    if si == 0 or si == m-1 or sj == 0 or sj == n-1:
        return True
    queue = deque([start])
    visited = {start}
    while queue:
        r, c = queue.popleft()
        if r == 0 or r == m-1 or c == 0 or c == n-1:
            return True
        curr_color = matrix[r][c]
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
                next_color = matrix[nr][nc]
                if curr_color == 'U' or next_color == 'U' or curr_color == next_color:
                    visited.add((nr, nc))
                    queue.append((nr, nc))
    return False

Tips

  • What they are testing: Test scenarios where the start is already on the boundary, and cases where color constraints completely block paths.
  • Common mistake: Forgetting to mark visited nodes, which leads to infinite loops in cyclic color transitions.

Follow-ups

  • What would happen if DFS were used instead of BFS? Will the best-case improve?

Related OYO questions

Collected from public candidate posts and coding forums. Updated Nov 2026.