0952MediumArrayHash TableMatrixCounting

Repainting a Board Into a Wye

Tracked in this browser only

Trains the technique from

LeetCode 3071Minimum Operations to Write the Letter Y on a Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A square board of odd side is given as grid, each cell holding 0, 1 or 2. One repaint changes a single cell to any of the three values.

The wye is the set of cells on the two diagonals running down from the top corners as far as the middle cell, together with the cells straight below the middle cell. Every other cell is outside the wye.

The board shows a wye when every cell of the wye holds one value, every cell outside holds one value, and those two values differ. Return the fewest repaints that leave the board showing a wye.

Examples

Example 1

Input: grid = [[1, 0, 1], [0, 1, 0], [0, 1, 0]]
Output: 0

The wye holds the corners of the top row, the middle cell and the two cells below it, and those already read 1, 1, 1, 1, 1. Everything outside already reads 0, so the board already shows a wye.

Example 2

Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Output: 4

Every cell reads 0, so one of the two parts has to be repainted, and the wye is the smaller of the two.

Example 3

Input: grid = [[2, 0, 2], [1, 2, 1], [0, 1, 0]]
Output: 3

Painting the wye 2 leaves three of its five cells to change, and painting everything else 1 leaves two of the four outside cells to change.

Constraints

3 <= grid.length <= 49
grid.length == grid[i].length
grid.length is odd
0 <= grid[i][j] <= 2

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_operations_to_write_y(grid: list[list[int]]) -> int:

Java

public int minimumOperationsToWriteY(int[][] grid)

The intended approach

Time O(n^2) for a board of side n: one sweep to tally, then a constant number of pairs.Space O(1): two tallies of three entries.

The finished board is settled by two choices: the value the wye takes and the value everything else takes, and those two must differ. With only three values there are six such pairs, so all of them can be tried. For a given pair, the repaints needed are the wye cells not already holding the wye's value plus the outside cells not already holding the other value. Those counts come from two tallies of three entries each, built in one sweep over the board: a cell belongs to the wye when it sits on either diagonal above the middle row, or in the middle column at or below the middle row. Reading the tallies then answers all six pairs at once.

Pythonentry point: minimum_operations_to_write_y

def minimum_operations_to_write_y(grid):
    n = len(grid)
    mid = n // 2
    inside = [0, 0, 0]
    outside = [0, 0, 0]
    for r in range(n):
        for c in range(n):
            on_wye = False
            if r <= mid and (c == r or c == n - 1 - r):
                on_wye = True
            elif r > mid and c == mid:
                on_wye = True
            if on_wye:
                inside[grid[r][c]] += 1
            else:
                outside[grid[r][c]] += 1
    total_in = inside[0] + inside[1] + inside[2]
    total_out = outside[0] + outside[1] + outside[2]
    best = None
    for wye in range(3):
        for rest in range(3):
            if wye == rest:
                continue
            cost = (total_in - inside[wye]) + (total_out - outside[rest])
            if best is None or cost < best:
                best = cost
    return best

The obvious version

Work out which cells belong to the wye by walking the two diagonals and the stem outright, marking them on a board of flags, then for each of the six value pairs count the mismatching cells one by one. Sweeps the whole board once per pair rather than tallying first.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_operations_to_write_y(grid):
    n = len(grid)
    mid = n // 2
    flag = [[False] * n for _ in range(n)]
    for step in range(mid + 1):
        flag[step][step] = True
        flag[step][n - 1 - step] = True
    for r in range(mid, n):
        flag[r][mid] = True
    best = None
    for wye in range(3):
        for rest in range(3):
            if wye == rest:
                continue
            cost = 0
            for r in range(n):
                for c in range(n):
                    want = wye if flag[r][c] else rest
                    if grid[r][c] != want:
                        cost += 1
            if best is None or cost < best:
                best = cost
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in