<p>You are given a <strong>0-indexed</strong> <code>n x n</code> grid where <code>n</code> is odd, and <code>grid[r][c]</code> is <code>0</code>, <code>1</code>, or <code>2</code>.</p>

<p>We say that a cell belongs to the Letter <strong>Y</strong> if it belongs to one of the following:</p>

<ul>
	<li>The diagonal starting at the top-left cell and ending at the center cell of the grid.</li>
	<li>The diagonal starting at the top-right cell and ending at the center cell of the grid.</li>
	<li>The vertical line starting at the center cell and ending at the bottom border of the grid.</li>
</ul>

<p>The Letter <strong>Y</strong> is written on the grid if and only if:</p>

<ul>
	<li>All values at cells belonging to the Y are equal.</li>
	<li>All values at cells not belonging to the Y are equal.</li>
	<li>The values at cells belonging to the Y are different from the values at cells not belonging to the Y.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> 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</em> <code>0</code><em>,</em> <code>1</code><em>,</em> <em>or</em> <code>2</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/01/22/y2.png" style="width: 461px; height: 121px;" />
<pre>
<strong>Input:</strong> grid = [[1,2,2],[1,1,0],[0,1,0]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/01/22/y3.png" style="width: 701px; height: 201px;" />
<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 12
<strong>Explanation:</strong> 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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= n &lt;= 49 </code></li>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 2</code></li>
	<li><code>n</code> is odd.</li>
</ul>

class Solution:
    def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
        # 00 0n-1 11 1n-2 3n-3
        n = len(grid)
        m = len(grid[0])

        freq = defaultdict(int)
        y_pos = defaultdict(int)
        count = 0
        for i in range(n):

            for j in range(m):
                if ((i,j)==(count,n-count-1) or (i,j)==(count,count)) and count<n//2:
                    y_pos[grid[i][j]]+=1
                else:
                    freq[grid[i][j]]+=1


            if count>=n//2:
                y_pos[grid[i][count]]+=1
                freq[grid[i][count]]-=1
            else:
                count+=1
        #for y-shape choose the one w highest freq in Y or 2nd highest
        #non y-shape choose the one w highest freq in non-Y 
                
        freq_ls = sorted(freq.items(),key = lambda x:-x[1])
        y_pos_ls = sorted(y_pos.items(),key = lambda x:-x[1])
        
        if len(y_pos_ls)==1 and len(freq_ls)==1:
            if y_pos_ls[0][0]==freq_ls[0][0]:
                return y_pos_ls[0][1]
            else:
                res = y_pos_ls[0][1] + freq_ls[0][1]
            return m*n - res

        if len(y_pos_ls)==1:
            
            if y_pos_ls[0][0]==freq_ls[0][0]:
                res = y_pos_ls[0][1] + freq_ls[1][1]
            else:
                res = y_pos_ls[0][1] + freq_ls[0][1]
            return m*n - res

        if len(freq_ls)==1:
            if y_pos_ls[0][0]==freq_ls[0][0]:
                res = y_pos_ls[1][1] + freq_ls[0][1]
            else:
                res = y_pos_ls[0][1] + freq_ls[0][1]
            return m*n-res

        non_y = freq_ls[0][0]
        y1 = y_pos_ls[0][0]
        y2 = y_pos_ls[1][0]

        if non_y==y1:
            if freq_ls[0][1]+y_pos_ls[1][1]>freq_ls[1][1]+y_pos_ls[0][1]:
                res = y_pos_ls[1][1] + freq_ls[0][1]
            else:
                res = freq_ls[1][1] + y_pos_ls[0][1]
        else:
            res = max(y_pos[y1] ,y_pos[y2]) + freq[non_y]

        return m*n - res
377