Minimum Operations to Write the Letter Y on a Grid

Intuitionthe target shape reduces the grid to two frequency tables

The final grid has only two regions: cells that belong to the Y and cells outside it. Every Y cell must become one common value, and every non-Y cell must become another common value. Once you choose those two values, each cell can be handled independently: a cell already holding its region's chosen value stays unchanged, while every other cell costs one operation.

There are only three possible values, so there are just six valid ordered choices for the pair: one value for Y and a different value for non-Y. The grid scan records how often each value appears in each region. For a chosen Y value, the number of changes inside Y is its size minus its frequency; the same formula applies outside Y. Checking all six pairs guarantees that the best assignment is found.

Approach

1. 1Compute the center column as n / 2, because n is odd and the Y's junction is the middle row and middle column.
2. 2Classify each cell as Y or non-Y using its row and column: at or above the center row, the cell is on Y when it lies on either diagonal; below the center row, it is on Y only when it lies in the center column. This prevents the lower half from incorrectly including diagonal cells.
3. 3Increment the frequency table for the cell's value in the region you just identified. Keeping separate counts lets every candidate pair be evaluated without rescanning the grid.
4. 4Try every yVal from 0 to 2 and every nonYVal from 0 to 2, skipping equal values because the two regions must remain different.
5. 5For each valid pair, compute yCount - yFreq[yVal] plus nonYCount - nonYFreq[nonYVal]. These are exactly the cells whose current values disagree with their region's target values.
6. 6Keep the smallest candidate cost and return it after all six different pairs have been checked, because no other final grid can use values outside those choices.

Complexitythe grid is scanned once and the value choices are constant

Annotated solutionC++ · one scan plus six constant-size candidates

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumOperationsToWriteY(vector<vector<int>>& grid) {
        int n = grid.size();
        int center = n / 2;
        int yCount = 0;
        int nonYCount = 0;
        int yFreq[3] = {0, 0, 0};
        int nonYFreq[3] = {0, 0, 0};

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                bool isY = false;

                if (i <= center) {
                    if (j == i || j == n - 1 - i) {
                        isY = true;
                    }
                } else {
                    if (j == center) {
                        isY = true;
                    }
                }

                if (isY) {
                    ++yCount;
                    ++yFreq[grid[i][j]];
                } else {
                    ++nonYCount;
                    ++nonYFreq[grid[i][j]];
                }
            }
        }

        int answer = INT_MAX;
        for (int yVal = 0; yVal < 3; ++yVal) {
            for (int nonYVal = 0; nonYVal < 3; ++nonYVal) {
                if (yVal == nonYVal) {
                    continue;
                }

                int changes = (yCount - yFreq[yVal])
                            + (nonYCount - nonYFreq[nonYVal]);
                answer = min(answer, changes);
            }
        }

        return answer;
    }
};

The split at i <= center is the key coordinate decision. In the upper half, the Y consists of the two diagonals, including the center where they meet. In the lower half, only the center column belongs to the Y. The two conditions are mutually exclusive by row, so each cell is counted exactly once and no separate visited array is needed.

Common mistakescoordinate boundaries and the different-value condition