Minimum Operations to Write the Letter Y on a Grid
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
min_operationsto a very large value. - Get the grid size
n. - Iterate through all possible values for
y_valfrom 0 to 2. - Inside this loop, iterate through all possible values for
non_y_valfrom 0 to 2. - If
y_valis the same asnon_y_val, skip this combination as it's invalid. - Initialize
current_operations = 0for 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 toy_val, incrementcurrent_operations. - If it's a 'non-Y' cell and its value
grid[r][c]is not equal tonon_y_val, incrementcurrent_operations. - After iterating through the entire grid, compare
current_operationswithmin_operationsand updatemin_operationsif a smaller value is found. - After checking all 6 valid
(y_val, non_y_val)pairs, returnmin_operations.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.