Minimum Operations to Write the Letter Y on a Grid — Medium Problem & Solution

Problem statement

grid is an n x n matrix with odd n whose cells hold 0, 1 or 2. The letter Y consists of these cells:

• the diagonal from the top-left corner down to the centre,
• the diagonal from the top-right corner down to the centre,
• the vertical line from the centre down to the bottom edge.

The Y is written on the grid when every Y cell holds the same value, every non-Y cell holds the same value, and those two values are different.

One operation changes any cell to 0, 1 or 2. Return the minimum number of operations needed to write the letter Y.

Example 1

Input: grid = [[1,2,2],[1,1,0],[0,1,0]]
Output: 3
Explanation: The Y cells are `(0,0)`, `(0,2)`, `(1,1)`, `(2,1)`. Making them all 1 and every other cell 0 changes `(0,2)`, `(0,1)` and `(1,0)`.

Example 2

Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: Repainting the four Y cells is cheaper than repainting the five background cells.

Example 3

Input: grid = [[2,0,2],[0,2,0],[0,2,0]]
Output: 0
Explanation: The Y already reads 2 on a background of 0.

Constraints

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

How to solve Minimum Operations to Write the Letter Y on a Grid

Choose the Y value a and background value b (a ≠ b); with the counts of each value inside and outside the Y, the cost of every choice is immediate.

Approach

1. Let h = (n - 1) / 2. A cell (r, c) is on the Y when r <= h and c == r or c == n - 1 - r, or when r >= h and c == h.
2. Count inY[v] and outY[v] for v = 0, 1, 2, and the totals Ysize and restSize.
3. For each pair a ≠ b, the cost is (Ysize - inY[a]) + (restSize - outY[b]); return the minimum.

Why it works

Each cell is changed independently and at most once, and a cell needs changing exactly when it does not hold its target value. Trying every valid pair of targets therefore covers every possible final picture.

Complexity

• Time — O(n²)
• Space — O(1)

Pitfalls

• The centre cell belongs to all three strokes — count it once.
• The Y value and the background value must be different; a == b is not allowed even if cheaper.
• The lower stroke runs from the centre down only, never up.

Reference solution

Python

from typing import List

def minimumOperationsToWriteY(grid: List[List[int]]) -> int:
    n = len(grid)
    h = n // 2
    in_y = [0, 0, 0]
    out_y = [0, 0, 0]
    for r in range(n):
        for c in range(n):
            if (r <= h and (c == r or c == n - 1 - r)) or (r >= h and c == h):
                in_y[grid[r][c]] += 1
            else:
                out_y[grid[r][c]] += 1
    y_size = sum(in_y)
    rest = sum(out_y)
    best = n * n
    for a in range(3):
        for b in range(3):
            if a != b:
                best = min(best, y_size - in_y[a] + rest - out_y[b])
    return best

JavaScript

var minimumOperationsToWriteY = function(grid) {
    var n = grid.length, h = (n - 1) / 2;
    var inY = [0, 0, 0], outY = [0, 0, 0];
    for (var r = 0; r < n; r++) {
        for (var c = 0; c < n; c++) {
            if ((r <= h && (c === r || c === n - 1 - r)) || (r >= h && c === h)) inY[grid[r][c]]++;
            else outY[grid[r][c]]++;
        }
    }
    var ySize = inY[0] + inY[1] + inY[2], rest = outY[0] + outY[1] + outY[2];
    var best = n * n;
    for (var a = 0; a < 3; a++) {
        for (var b = 0; b < 3; b++) {
            if (a !== b) best = Math.min(best, ySize - inY[a] + rest - outY[b]);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium