Minimum Operations to Write the Letter Y on a Grid
Source: leetcode
Difficulty: Medium
Tags: array, hash-table, matrix, counting

You are given a **0\-indexed** `n x n` grid where `n` is odd, and `grid[r][c]` is `0`, `1`, or `2`.


We say that a cell belongs to the Letter **Y** if it belongs to one of the following:


- The diagonal starting at the top\-left cell and ending at the center cell of the grid.
- The diagonal starting at the top\-right cell and ending at the center cell of the grid.
- The vertical line starting at the center cell and ending at the bottom border of the grid.


The Letter **Y** is written on the grid if and only if:


- All values at cells belonging to the Y are equal.
- All values at cells not belonging to the Y are equal.
- The values at cells belonging to the Y are different from the values at cells not belonging to the Y.


Return *the **minimum** number of operations needed to write the letter Y on the grid given that in one operation you can change the value at any cell to* `0`*,* `1`*,* *or* `2`*.*


 


**Example 1:**


![](https://assets.leetcode.com/uploads/2024/01/22/y2.png)

```

Input: grid = [[1,2,2],[1,1,0],[0,1,0]]
Output: 3
Explanation: We can write Y on the grid by applying the changes highlighted in blue in the image above. After the operations, all cells that belong to Y, denoted in bold, have the same value of 1 while those that do not belong to Y are equal to 0.
It can be shown that 3 is the minimum number of operations needed to write Y on the grid.

```

**Example 2:**


![](https://assets.leetcode.com/uploads/2024/01/22/y3.png)

```

Input: grid = [[0,1,0,1,0],[2,1,0,1,2],[2,2,2,0,1],[2,2,2,2,2],[2,1,2,2,2]]
Output: 12
Explanation: We can write Y on the grid by applying the changes highlighted in blue in the image above. After the operations, all cells that belong to Y, denoted in bold, have the same value of 0 while those that do not belong to Y are equal to 2. 
It can be shown that 12 is the minimum number of operations needed to write Y on the grid.
```

 


**Constraints:**


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




C++ solution:
class Solution {
public:
    int minimumOperationsToWriteY(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL), cout.tie(NULL);

        vector<int> y(3, 0), rest(3, 0);
        int n = grid.size(), mid = n/2;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(((i==j || i+j==n-1) && i<mid) || (j==mid && i>=mid)){
                    y[grid[i][j]]++;
                }else{
                    rest[grid[i][j]]++;
                }
            }
        }

        int yCells = mid+n, restCells = n*n-yCells;
        
        int y0 = (yCells-y[0])+(restCells-max(rest[1], rest[2]));
        int y1 = (yCells-y[1])+(restCells-max(rest[0], rest[2]));
        int y2 = (yCells-y[2])+(restCells-max(rest[0], rest[1]));

        return min({y0, y1, y2});
    }
};

Go solution:
func minimumOperationsToWriteY(grid [][]int) int {
    n := len(grid)
	m := n / 2

	inY := make([]int, 3)
	outY := make([]int, 3)

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if (i == j && i <= m) {
                inY[grid[i][j]]++
            } else if (i + j == n - 1 && i <= m) {
                inY[grid[i][j]]++
            } else if (j == m && i >= m) {
                inY[grid[i][j]]++
            } else {
                outY[grid[i][j]]++
            }
		}
	}

	totalInY := inY[0] + inY[1] + inY[2]
    totalOutY := n * n - totalInY

	res := math.MaxInt

	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if i == j {
				continue
			}

			tmp1 := totalInY - inY[i]
			tmp2 := totalOutY - outY[j]
			tmp := tmp1 + tmp2

			res = min(res, tmp)
		}
	}

	return res
}

Java solution:
class Solution {
    void fill(int[][] vis, int[][] v) {
        int n = v.length;
        int i = 0, j = 0;
        while (i <= n / 2) {
            vis[i][j] = 1;
            i++;
            j++;
        }
        i = 0;
        j = n - 1;
        while (i < n / 2) {
            vis[i][j] = 1;
            i++;
            j--;
        }
        i = n / 2 + 1;
        j = n / 2;
        while (i < n) {
            vis[i][j] = 1;
            i++;
        }
    }

    public int minimumOperationsToWriteY(int[][] v) {
        int n = v.length;
        int[][] vis = new int[n][n];
        fill(vis, v);
        int[] v1 = new int[3];
        int[] v2 = new int[3];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 1) {
                    if (v[i][j] == 0)
                        v1[0]++;
                    else if (v[i][j] == 1)
                        v1[1]++;
                    else
                        v1[2]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 0) {
                    if (v[i][j] == 0)
                        v2[0]++;
                    else if (v[i][j] == 1)
                        v2[1]++;
                    else
                        v2[2]++;
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= 2; i++) {
            int costY = v1[0] + v1[1] + v1[2] - v1[i];
            int costRem = Integer.MAX_VALUE;
            for (int j = 0; j <= 2; j++) {
                if (i == j)
                    continue;
                int t = v2[0] + v2[1] + v2[2] - v2[j];
                costRem = Math.min(costRem, t);
            }
            ans = Math.min(ans, costY + costRem);
        }
        return ans;
    }
}

JavaScript solution:
var minimumOperationsToWriteY = function(grid) {
  let countY = Array(3).fill(0);
  let countOutside = Array(3).fill(0);
  let n = grid.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (isPartOfY(i, j, n)) {
        countY[grid[i][j]]++;
      } else {
        countOutside[grid[i][j]]++;
      }
    }
  }
  let ans = Infinity;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (i === j) continue;
      let costY = countY[0] + countY[1] + countY[2] - countY[i];
      let costOutsideY = countOutside[0] + countOutside[1] + countOutside[2] - countOutside[j];
      ans = Math.min(ans, costY + costOutsideY);
    }
  }
  return ans;
};

function isPartOfY(row, col, n) {
  let isLeftPart = row <= Math.floor(n / 2) && row === col;
  let isRightPart = row <= Math.floor(n / 2) && row + col === n - 1;
  let isMiddlePart = row >= Math.floor(n / 2) && col === Math.floor(n / 2);
  return isLeftPart || isRightPart || isMiddlePart;
}

Python solution:
class Solution:
    def minimumOperationsToWriteY(self, g: List[List[int]]) -> int:
        n=len(g)
        n2=n//2
        y=((g[i][i],g[i][n-i-1],
            g[n-i-1][n2]) for i in range(n2))
        c=Counter(chain(*y))
        c[g[n2][n2]]+=1
        x=Counter(chain(*g))-c
        return n*n-max(
            c[0]+x[1],c[1]+x[0],
            c[1]+x[2],c[2]+x[1],
            c[0]+x[2],c[2]+x[0]
        )

Ruby solution:
def minimum_operations_to_write_y(grid)
    n = grid.length
    mid = n / 2
    y_val = []

    (0...n).each do |i|
        (0...n).each do |j|
            if (i == j && i <= mid && j <= mid) || (i + j == n - 1 && j > mid && i < mid) || (j == mid && i > mid)
                y_val << grid[i][j]
            end
        end
    end
    
    count = Hash.new(0)
    count1 = Hash.new(0)
    
    y_val.each { |elem| count[elem] += 1 }
    
    grid.each { |row| row.each { |elem| count1[elem] += 1 } }

    count.each_key { |key| count1[key] -= count[key] }

    ans = []
    
    [0, 1, 2].permutation(2).each do |x, y|
        ans << (count.values.sum - count[x]) + (count1.values.sum - count1[y])
    end
    
    ans.min
end