Watch 10 video solutions for Minimum Operations to Write the Letter Y on a Grid, a medium level problem involving Array, Hash Table, Matrix. This walkthrough by Aryan Mittal has 3,202 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |