Minimum Operations to Write the Letter Y on a Grid - Solution & Explanation
Problem Statement
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 <= 49n == grid.length == grid[i].length0 <= grid[i][j] <= 2nis odd.
Approach Overview
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 1: Grid Traversal with Cell Count
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.
Complexity
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.
Approach 2: Direct Y Pattern Analysis
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.
Code
Java
JavaScript
Complexity
Time Complexity: O(n^2) - Each grid element is inspected once.
Space Complexity: O(1) - Uses constant space for fixed-size counting arrays.
Approach 3: Counting
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3071. Minimum Operations to Write the Letter Y on a Grid | Arrays | Matrix • Aryan Mittal • 3,305 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Minimum Operations to Write the Letter Y on a Grid easy or hard?
Minimum Operations to Write the Letter Y on a Grid Python/Java solution
How to solve Minimum Operations to Write the Letter Y on a Grid in O(n^2)?
What is the best approach for Minimum Operations to Write the Letter Y on a Grid?
Is Minimum Operations to Write the Letter Y on a Grid asked at Google/Amazon/Meta?
What data structure is used in Minimum Operations to Write the Letter Y on a Grid?
What is the time complexity of Minimum Operations to Write the Letter Y on a Grid?
Ready to solve this problem?
Practice Minimum Operations to Write the Letter Y on a Grid with our built-in code editor and test cases.
Practice on FleetCode