3071-minimum-operations-to-write-the-letter-y-on-a-grid¶

Description¶

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:

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:

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.

Solution(Python)¶

class Solution:
    def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
        n = len(grid)
        y_cells_counter = Counter()
        non_y_cells_counter = Counter()
        for row_idx, row in enumerate(grid):
            for col_idx, cell_value in enumerate(row):

                is_left_diagnol = (row_idx == col_idx) and row_idx <= n//2 
                is_right_diagnol = (row_idx + col_idx == n-1) and row_idx <= n//2 
                is_center_stem = ( col_idx == n//2) and row_idx >= n//2 

                if is_left_diagnol or is_right_diagnol or is_center_stem:
                    y_cells_counter[cell_value] +=1
                else:
                    non_y_cells_counter[cell_value] +=1
        total_cells = n*n

        min_ops = min(
            total_cells -  y_cells_counter[y_color] -  non_y_cells_counter[non_y_color]
            for y_color in range(3)
            for non_y_color in range(3)
            if y_color != non_y_color
        )

        return min_ops