# Minimum Operations to Write the Letter Y on a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-write-the-letter-y-on-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-write-the-letter-y-on-a-grid
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Zeta](https://scaleengineer.com/companies/zeta), [ZipRecruiter](https://scaleengineer.com/companies/ziprecruiter)
---
## Problem
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.glich.co/dsa/minimum-operations-to-write-the-letter-y-on-a-grid/image0.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.glich.co/dsa/minimum-operations-to-write-the-letter-y-on-a-grid/image1.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.

# Approaches
## Brute-Force Simulation for Each Case
This approach directly simulates the process for every possible valid final configuration. A valid configuration requires all 'Y' cells to be one value (`y_val`) and all 'non-Y' cells to be another, different value (`non_y_val`). Since there are 3 possible values (0, 1, 2), there are 3 * 2 = 6 such valid configurations. The algorithm iterates through each of these 6 possibilities, calculates the number of operations (cell changes) needed to achieve that state by scanning the entire grid, and keeps track of the minimum operations found.
**Time:** O(k * n^2), where k is the number of possible value pairs (6). This simplifies to O(n^2). The grid is traversed for each of the 6 valid target configurations. · **Space:** O(1), as we only use a few variables to store the counts and minimums, requiring constant extra space.
**Pros:** Simple to understand and implement.; Directly follows the problem definition without complex data structures.
**Cons:** Inefficient due to redundant computations. The entire grid is scanned multiple times (once for each of the 6 valid configurations).
### Explanation
The core idea is to test every valid target pattern and find the one that requires the fewest changes. The possible target patterns are defined by a pair of distinct values `(y_val, non_y_val)`, where `y_val` is the target value for cells in the 'Y' shape, and `non_y_val` is for cells outside the 'Y'. The algorithm iterates through all 6 pairs: (0,1), (0,2), (1,0), (1,2), (2,0), (2,1). For each pair, it traverses the entire `n x n` grid. For each cell `(r, c)`, it first determines if the cell belongs to the 'Y' shape. If it's a 'Y' cell, it checks if its current value `grid[r][c]` is different from `y_val`. If so, it counts as one operation. If it's a 'non-Y' cell, it checks if its value is different from `non_y_val`. If so, it counts as one operation. The total operations for the current pair are summed up, and the minimum count across all 6 pairs is the final answer.

```java
class Solution {
    public int minimumOperations(int[][] grid) {
        int n = grid.length;
        int minOps = Integer.MAX_VALUE;

        for (int yVal = 0; yVal <= 2; yVal++) {
            for (int nonYVal = 0; nonYVal <= 2; nonYVal++) {
                if (yVal == nonYVal) {
                    continue;
                }

                int currentOps = 0;
                for (int r = 0; r < n; r++) {
                    for (int c = 0; c < n; c++) {
                        if (isYCell(r, c, n)) {
                            if (grid[r][c] != yVal) {
                                currentOps++;
                            }
                        } else {
                            if (grid[r][c] != nonYVal) {
                                currentOps++;
                            }
                        }
                    }
                }
                minOps = Math.min(minOps, currentOps);
            }
        }
        return minOps;
    }

    private boolean isYCell(int r, int c, int n) {
        int center = n / 2;
        if ((r == c && r <= center) || 
            (r + c == n - 1 && r <= center) || 
            (c == center && r >= center)) {
            return true;
        }
        return false;
    }
}
```
### Algorithm
- Initialize `min_operations` to a very large value.
- Get the grid size `n`.
- Iterate through all possible values for `y_val` from 0 to 2.
- Inside this loop, iterate through all possible values for `non_y_val` from 0 to 2.
- If `y_val` is the same as `non_y_val`, skip this combination as it's invalid.
- Initialize `current_operations = 0` for the current `(y_val, non_y_val)` pair.
- Iterate through each cell `(r, c)` of the grid.
- For each cell, determine if it belongs to the 'Y' shape using a helper function.
- If it's a 'Y' cell and its value `grid[r][c]` is not equal to `y_val`, increment `current_operations`.
- If it's a 'non-Y' cell and its value `grid[r][c]` is not equal to `non_y_val`, increment `current_operations`.
- After iterating through the entire grid, compare `current_operations` with `min_operations` and update `min_operations` if a smaller value is found.
- After checking all 6 valid `(y_val, non_y_val)` pairs, return `min_operations`.

## Optimized Approach with Pre-computation
This approach improves upon the brute-force method by avoiding redundant work. Instead of iterating through the grid for each of the 6 possible target configurations, we first iterate through the grid just once to gather all necessary information. We count the frequencies of the values (0, 1, 2) separately for the cells that form the 'Y' and for the cells that do not. With these pre-computed counts, we can calculate the cost for each of the 6 target configurations in constant time, making the overall solution much faster.
**Time:** O(n^2). The initial pass to populate the frequency counts takes O(n^2). The subsequent loop to check the 6 configurations takes constant time, O(1). The total complexity is dominated by the single grid traversal. · **Space:** O(1). We use two arrays of size 3 for frequency counts, which is constant space and does not depend on the size of the grid.
**Pros:** Highly efficient as it traverses the grid only once.; Clear separation of concerns: data gathering and calculation.; Optimal time complexity for the given constraints.
**Cons:** Requires a small amount of extra space for the frequency count arrays, though it is constant space.
### Explanation
The key insight is that the cost to change a region to a single value depends only on the total number of cells in that region and the count of the target value already present. We create two frequency arrays, `yCounts` and `nonYCounts`, both of size 3, to store the counts of values 0, 1, and 2 for 'Y' cells and 'non-Y' cells, respectively. We traverse the `n x n` grid a single time. For each cell `(r, c)`, we determine if it belongs to the 'Y'. If it's a 'Y' cell, we increment `yCounts[grid[r][c]]`. Otherwise, we increment `nonYCounts[grid[r][c]]`. After this single pass, we have all the data we need. Then, we iterate through the 6 possible `(y_val, non_y_val)` pairs. For each pair, the cost is calculated efficiently as `(totalYCells - yCounts[y_val]) + (totalNonYCells - nonYCounts[non_y_val])`. This calculation is O(1), and we find the minimum cost among the 6 pairs.

```java
class Solution {
    public int minimumOperations(int[][] grid) {
        int n = grid.length;
        int[] yCounts = new int[3];
        int[] nonYCounts = new int[3];

        // Step 1: Count frequencies in Y and non-Y regions in a single pass
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (isYCell(r, c, n)) {
                    yCounts[grid[r][c]]++;
                } else {
                    nonYCounts[grid[r][c]]++;
                }
            }
        }

        int totalYCells = yCounts[0] + yCounts[1] + yCounts[2];
        int totalNonYCells = n * n - totalYCells;
        int minOps = Integer.MAX_VALUE;

        // Step 2: Calculate minimum operations for all 6 valid configurations using counts
        for (int yVal = 0; yVal <= 2; yVal++) {
            for (int nonYVal = 0; nonYVal <= 2; nonYVal++) {
                if (yVal == nonYVal) {
                    continue;
                }

                // Operations to make Y cells have yVal
                int opsY = totalYCells - yCounts[yVal];
                
                // Operations to make non-Y cells have nonYVal
                int opsNonY = totalNonYCells - nonYCounts[nonYVal];
                
                minOps = Math.min(minOps, opsY + opsNonY);
            }
        }

        return minOps;
    }

    private boolean isYCell(int r, int c, int n) {
        int center = n / 2;
        if ((r == c && r <= center) || 
            (r + c == n - 1 && r <= center) || 
            (c == center && r >= center)) {
            return true;
        }
        return false;
    }
}
```
### Algorithm
- Get the grid size `n`.
- Initialize two frequency arrays: `yCounts = [0, 0, 0]` and `nonYCounts = [0, 0, 0]`.
- Traverse the `n x n` grid a single time. For each cell `(r, c)`:
  - Determine if it belongs to the 'Y' shape.
  - If it's a 'Y' cell, increment `yCounts[grid[r][c]]`.
  - Otherwise, increment `nonYCounts[grid[r][c]]`.
- After the traversal, calculate the total number of 'Y' cells: `totalYCells = yCounts[0] + yCounts[1] + yCounts[2]`.
- Calculate the total number of 'non-Y' cells: `totalNonYCells = n * n - totalYCells`.
- Initialize `min_operations` to a very large value.
- Iterate through all possible values for `y_val` from 0 to 2.
- Inside this loop, iterate through all possible values for `non_y_val` from 0 to 2.
- If `y_val` is the same as `non_y_val`, skip.
- Calculate the cost for the current pair `(y_val, non_y_val)` using the pre-computed counts:
  - `costY = totalYCells - yCounts[y_val]`
  - `costNonY = totalNonYCells - nonYCounts[non_y_val]`
  - `current_operations = costY + costNonY`
- Update `min_operations = min(min_operations, current_operations)`.
- Return `min_operations`.

# Solutions
### Java

```java
class Solution {
public
  int minimumOperationsToWriteY(int[][] grid) {
    int n = grid.length;
    int[] cnt1 = new int[3];
    int[] cnt2 = new int[3];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        boolean a = i == j && i <= n / 2;
        boolean b = i + j == n - 1 && i <= n / 2;
        boolean c = j == n / 2 && i >= n / 2;
        if (a || b || c) {
          ++cnt1[grid[i][j]];
        } else {
          ++cnt2[grid[i][j]];
        }
      }
    }
    int ans = n * n;
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        if (i != j) {
          ans = Math.min(ans, n * n - cnt1[i] - cnt2[j]);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperationsToWriteY(vector<vector<int>> &grid) {
    int n = grid.size();
    int cnt1[3]{};
    int cnt2[3]{};
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        bool a = i == j && i <= n / 2;
        bool b = i + j == n - 1 && i <= n / 2;
        bool c = j == n / 2 && i >= n / 2;
        if (a || b || c) {
          ++cnt1[grid[i][j]];
        } else {
          ++cnt2[grid[i][j]];
        }
      }
    }
    int ans = n * n;
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        if (i != j) {
          ans = min(ans, n * n - cnt1[i] - cnt2[j]);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int: n = len(grid) cnt1 = Counter() cnt2 = Counter() for i, row in enumerate(grid): for j, x in enumerate(row): a = i == j and i <= n // 2 b = i + j == n - 1 and i <= n // 2 c = j == n // 2 and i >= n // 2 if a or b or c: cnt1[x] += 1 else: cnt2[x] += 1 return min(n * n - cnt1[i] - cnt2[j] for i in range(3) for j in range(3) if i != j)

```