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 Letter Y is written on the grid if and only if:
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].length0 <= grid[i][j] <= 2n is odd.Problem Overview: You’re given an n x n grid where each cell contains a value (typically 0, 1, or 2). The goal is to transform the grid so that cells forming the letter Y contain one value and all other cells contain a different value. Each change counts as one operation. The task is to compute the minimum number of operations required.
Approach 1: Grid Traversal with Cell Count (O(n^2) time, O(1) space)
Traverse the entire grid and classify each cell as either part of the Y shape or outside it. The Y consists of the two diagonals in the upper half of the matrix that meet at the center, plus the vertical line going downward from the center. While iterating, maintain frequency counts for values inside the Y and outside the Y. Since the grid values are limited (e.g., 0–2), you can track counts using small arrays. After traversal, try every pair of distinct values (yValue, otherValue) and compute how many cells must change to match the rule. This method relies on straightforward matrix traversal and counting, making it reliable and easy to implement in Python or C++.
Approach 2: Direct Y Pattern Analysis (O(n^2) time, O(1) space)
Instead of detecting the Y during traversal, compute its structure directly using index rules. A cell belongs to the Y if it lies on the left diagonal or right diagonal above the center, or on the center column below the midpoint. With these conditions, iterate once through the grid and update frequency counts for Y and non-Y cells. Then evaluate all valid combinations of values for the two regions to find the minimum recoloring cost. This approach emphasizes pattern recognition in a array grid and keeps the logic compact, which is why many Java and JavaScript implementations prefer it.
Recommended for interviews: Grid Traversal with Cell Count. It shows you can reason about geometric patterns inside a matrix while maintaining frequency counts efficiently. Interviewers expect the O(n^2) traversal with constant auxiliary space because every cell must be inspected at least once. The direct pattern approach is essentially the same complexity but demonstrates stronger clarity in recognizing index-based patterns.
This approach involves traversing the grid and identifying cells that belong to the Y pattern and those that do not. We count values in both groups and choose the most common value for each group to minimize the number of changes. By calculating the cost to change each cell to the most frequent value in its group, we can determine the minimum operations needed.
In this Python implementation, we calculate the center of the grid and determine the coordinates that form the Y-shape. We maintain two counters to track occurrences of each value in Y and non-Y cells. By identifying the most frequent value in each group, we calculate the required changes to unify each group.
Time Complexity: O(n^2) - We traverse each cell in the grid once.
Space Complexity: O(n) - Additional space to store unique cell coordinates and value counts.
This approach focuses on leveraging the direct pattern of the letter Y. We analyze the diagonals and center column interactions separately, determine their frequency, and adjust values to conform to the defined pattern with minimum edits. The goal is to ensure that the value of the Y is different from the remaining grid cells and optimize accordingly.
This Java implementation uses arrays to count values in Y and non-Y cells and identifies the most frequent value for each category. It minimizes the operations required to write the Y pattern efficiently, adjusting different cell values as needed.
Java
JavaScript
Time Complexity: O(n^2) - Each grid element is inspected once.
Space Complexity: O(1) - Uses constant space for fixed-size counting arrays.
We use two arrays of length 3, cnt1 and cnt2, to record the counts of cell values that belong to Y and do not belong to Y, respectively. Then we enumerate i and j, which represent the values of cells that belong to Y and do not belong to Y, respectively, to calculate the minimum number of operations.
The time complexity is O(n^2), where n is the size of the matrix. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Grid Traversal with Cell Count | Time Complexity: O(n^2) - We traverse each cell in the grid once. |
| Direct Y Pattern Analysis | Time Complexity: O(n^2) - Each grid element is inspected once. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Grid Traversal with Cell Count | O(n^2) | O(1) | General case; easiest to reason about by scanning the grid and counting values inside vs outside the Y |
| Direct Y Pattern Analysis | O(n^2) | O(1) | When you want a concise solution using index rules to identify Y cells during traversal |
3071. Minimum Operations to Write the Letter Y on a Grid | Arrays | Matrix • Aryan Mittal • 3,202 views views
Watch 9 more video solutions →Practice Minimum Operations to Write the Letter Y on a Grid with our built-in code editor and test cases.
Practice on FleetCode