Two-colour a board with walls and fixed cells: Frontier Interview's solution

Question: Two-colour a board with walls and fixed cells

Companies: Netflix

Difficulty: Medium

Problem statement

You are given an M x N board as a matrix of integers. Each cell is one of:

1: already painted black
0: already painted white
9: empty, still to be painted
-1: a wall, which is never painted

Paint every empty cell black or white so that no two cells that share an edge (up, down, left, right) have the same colour. Walls take no colour and don't constrain their neighbours. Pre-painted cells keep their colour.

Implement color_grid(grid) -> list[list[int]] | None. It returns a new, fully painted board, or None if no valid painting exists. If more than one painting works, return any of them.

Constraints: 0 <= M, N <= 1000. Cell values are in {-1, 0, 1, 9}.

Example 1

input:            output:
 1  9  9           1  0  1
 9 -1  9           0 -1  0
 9  9  9           1  0  1

Example 2

input:  [[0, 9, 9, 0]]   -> None

The two white cells are three steps apart, so the cells between them can't alternate. Replace the third cell with a wall ([[0, 9, -1, 0]]) and the answer becomes [[0, 1, -1, 0]].

Then discuss: how many valid paintings exist, and what changes if diagonal neighbours also count as adjacent?

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Treat every non-boundary cell (0, 1 or 9) as a node and connect it to
its up, down, left and right neighbours that are also non-boundary. A -1
cell is a wall: it takes no colour and constrains nothing. The rule "no two
adjacent playable cells share a colour" is then a 2-colouring of this graph.

Key fact. A grid graph is bipartite: moving one step always flips the
parity of r + c. So inside one connected region there are exactly two
legal colourings:

colour = (r + c) % 2, or
colour = 1 - (r + c) % 2.

Pick one with a single bit k, so colour = (r + c + k) % 2. A pre-coloured
cell with value v forces k = (v - r - c) mod 2. The region can be
coloured only if every pre-coloured cell in it asks for the same k.

Brute force. Try both colours for each empty cell and backtrack: up to
O(2^E) for E empty cells. Say this out loud, then move on. The parity fact
removes the search.

Optimal.

Scan the grid. For each non-boundary cell not yet visited, BFS its region
and collect its cells.
While collecting, check each pre-coloured cell against the required k.
The first one sets k. A later one that disagrees means the board can't be
coloured: return None.
If the region has no pre-coloured cell, use k = 0 (any choice works; say
which tie-break you use).
Write (r + c + k) % 2 into every empty cell of the region.

Invariants. Every cell is enqueued at most once. When a region finishes,
every pre-coloured cell in it agrees with k, and so every pair of adjacent
cells in it differs. Regions never touch, because only walls lie between
them, so they are independent.

Comparing the parity of two pre-coloured cells is the same as checking
odd cycles in general BFS 2-colouring. Mention that the general version
(BFS, colour neighbours opposite, report a conflict) gives the same answer.
It is the method to fall back on if the interviewer changes the
adjacency rule (see Follow-ups).

Code

from collections import deque
from typing import List, Optional

BLACK, WHITE, EMPTY, WALL = 1, 0, 9, -1
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def color_grid(grid: List[List[int]]) -> Optional[List[List[int]]]:
    """Fill every EMPTY cell with BLACK or WHITE so that no two
    orthogonally adjacent non-wall cells share a colour.

    Returns a new grid, or None if the pre-coloured cells make it impossible.
    """
    if not grid or not grid[0]:
        return [row[:] for row in grid]
    m, n = len(grid), len(grid[0])
    out = [row[:] for row in grid]
    seen = [[False] * n for _ in range(m)]

    for sr in range(m):
        for sc in range(n):
            if grid[sr][sc] == WALL or seen[sr][sc]:
                continue
            # BFS one region, deciding its parity bit k on the way.
            k: Optional[int] = None
            region = []
            seen[sr][sc] = True
            queue = deque([(sr, sc)])
            while queue:
                r, c = queue.popleft()
                region.append((r, c))
                v = grid[r][c]
                if v in (BLACK, WHITE):
                    need = (v - r - c) % 2
                    if k is None:
                        k = need
                    elif k != need:
                        return None  # two fixed cells disagree
                elif v != EMPTY:
                    raise ValueError(f"bad cell value {v} at {(r, c)}")
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < m and 0 <= nc < n and not seen[nr][nc]
                            and grid[nr][nc] != WALL):
                        seen[nr][nc] = True
                        queue.append((nr, nc))
            if k is None:
                k = 0  # free region: either colouring is valid
            for r, c in region:
                if out[r][c] == EMPTY:
                    out[r][c] = (r + c + k) % 2
    return out


def is_valid(grid: List[List[int]]) -> bool:
    """Checker used by tests: no EMPTY left, no equal-coloured neighbours."""
    m, n = len(grid), len(grid[0]) if grid else 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == EMPTY:
                return False
            if grid[r][c] == WALL:
                continue
            for nr, nc in ((r + 1, c), (r, c + 1)):
                if nr < m and nc < n and grid[nr][nc] == grid[r][c]:
                    return False
    return True


if __name__ == "__main__":
    g = [[1, 9, 9],
         [9, -1, 9],
         [9, 9, 9]]
    res = color_grid(g)
    assert res == [[1, 0, 1], [0, -1, 0], [1, 0, 1]] and is_valid(res)

    # Two fixed cells of the same colour at odd distance: impossible.
    assert color_grid([[1, 9, 9, 1]]) is None
    # Same thing, but a wall splits them into two regions: fine.
    res = color_grid([[1, 9, -1, 1]])
    assert res == [[1, 0, -1, 1]] and is_valid(res)

    # Region with no fixed cell uses k = 0.
    assert color_grid([[9, 9], [9, 9]]) == [[0, 1], [1, 0]]
    # All walls / empty grid.
    assert color_grid([[-1, -1]]) == [[-1, -1]]
    assert color_grid([]) == []
    # Already-coloured invalid board is caught.
    assert color_grid([[0, 0]]) is None
    # Input not mutated.
    g2 = [[9, 0]]
    assert color_grid(g2) == [[1, 0]] and g2 == [[9, 0]]
    print("ok")

Complexity

For an M x N grid:

Time: O(M * N). Each cell is enqueued and dequeued at most once, and
each one checks 4 neighbours.
Space: O(M * N) for the output copy, the seen matrix, the queue and
the region list. You can drop seen and region by writing colours into
out during the BFS and using out[r][c] != EMPTY as the visited mark.
That needs a second pass over the region if k is only learned late, or
you can find k first with one BFS and colour with a second.
is_valid: O(M * N) time, O(1) extra space.

Test cases

[[1,9,9],[9,-1,9],[9,9,9]] → [[1,0,1],[0,-1,0],[1,0,1]]. The ring around
the wall has even length, so it can be coloured.
[[1,9,9,1]] → None. The two blacks are 3 apart (odd), so they need
different colours.
[[1,9,-1,1]] → [[1,0,-1,1]]. The wall makes two separate regions.
[[9,9],[9,9]] → [[0,1],[1,0]]. No fixed cell, so tie-break k = 0.
[[0,0]] → None. A board with no empty cells can still be invalid.
[[-1,-1]] → unchanged. [] → [].
[[9]] → [[0]]. A single empty cell.
[[1,9],[9,1]] → [[1,0],[0,1]]. Diagonal same colours are fine.
[[1,-1,0]] → unchanged. A wall between two cells imposes no constraint.
A large board, e.g. 1000x1000 all 9: must not recurse. BFS with a deque
avoids Python's recursion limit, which DFS would hit.

Follow-ups

Count the valid colourings. Each region with no fixed cell has 2
choices. Each region with a consistent fixed cell has 1. Each region with a
conflict has 0. Answer: 2^(free regions) if there is no conflict, else 0.
Use mod 1e9+7 if the interviewer asks for it.
Fewest repaints. Pre-coloured cells may be repainted at a cost of 1
each, and the board must become valid. In each region, count how many
fixed cells disagree with k = 0 and how many with k = 1. Take the
smaller count and add it up over regions. This is still O(MN).
Cells change over time. A stream of set(r, c, colour) or
wall(r, c) updates, each followed by "is it still colourable?". With
colourings only, keep a union-find with parity over regions. Setting a cell
checks its required k against the region's stored k. Adding walls
splits regions, which union-find can't undo. Rebuild the affected region
with BFS, or process the updates offline in reverse (removing walls merges
regions).
Different adjacency. With 8-neighbour adjacency, any 2x2 block of
non-wall cells is a triangle, so it can't be coloured. Parity no longer
applies. Switch to general BFS 2-colouring: give each neighbour the
opposite colour and fail on a conflict. Arbitrary edges (for example
"portals") need the same switch. The code above already holds the
BFS skeleton.
More than two colours. Three or more colours on an arbitrary graph is
NP-complete. On a plain grid with no fixed cells it is trivial,
because 2 colours already work. With fixed cells, reduce to
backtracking with constraint propagation. You could also do a profile DP
over rows when one side is small (O(M * k^N)).

Interviewer expectations

Mid-level (L4)

Restates the rule and asks what walls do: do they block adjacency, and
do they take a colour?
Writes a BFS/DFS 2-colouring that fills the board and spots a conflict.
Handles regions with no fixed cell, and the empty grid.

Senior (L5)

Sees that grid adjacency is bipartite by (r + c) parity. Reduces each
region to one bit and explains why two fixed cells conflict exactly when
their parity disagrees with their colours.
Uses iterative BFS (no recursion limit), doesn't mutate the input, and
writes a separate validity checker for tests.
Answers counting and fewest-repaints follow-ups quickly from the per-region
view.

Staff (L6+)

Explains which assumptions the parity shortcut depends on. Knows that
diagonal adjacency or arbitrary edges break it and that general 2-colouring
still works.
Designs the online version: union-find with parity for merges, and a plan
for splits from new walls (offline reversal or local rebuild).
Discusses k-colouring hardness and when a row-profile DP is practical.