3071. Minimum Operations to Write the Letter Y on a Grid LeetCode Solution
In this guide, you will get 3071. Minimum Operations to Write the Letter Y on a Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Write the Letter Y on a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Operations to Write the Letter Y on a Grid solution in C++
- Minimum Operations to Write the Letter Y on a Grid solution in Java
- Minimum Operations to Write the Letter Y on a Grid solution in Python
- Additional Resources
Problem Statement of Minimum Operations to Write the Letter Y on a Grid
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 <= 49
n == grid.length == grid[i].length
0 <= grid[i][j] <= 2
n is odd.
Complexity Analysis
- Time Complexity: O(n^2)
- Space Complexity: O(1)
3071. Minimum Operations to Write the Letter Y on a Grid LeetCode Solution in C++
class Solution {
public:
int minimumOperationsToWriteY(vector<vector<int>>& grid) {
return min({getOperations(grid, 0, 1), getOperations(grid, 0, 2),
getOperations(grid, 1, 0), getOperations(grid, 1, 2),
getOperations(grid, 2, 0), getOperations(grid, 2, 1)});
}
private:
// Returns the number of operations to turn Y into a and non-Y into b.
int getOperations(const vector<vector<int>>& grid, int a, int b) {
const int n = grid.size();
const int mid = n / 2;
int operations = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
// For the 'Y' pattern, before the midpoint, check the diagonal and
// anti-diagonal. After the midpoint, check the middle column.
if ((i < mid && (i == j || i + j == n - 1)) || (i >= mid && j == mid)) {
if (grid[i][j] != a)
++operations;
} else if (grid[i][j] != b) {
++operations;
}
return operations;
};
};
/* code provided by PROGIEZ */3071. Minimum Operations to Write the Letter Y on a Grid LeetCode Solution in Java
class Solution {
public int minimumOperationsToWriteY(int[][] grid) {
return Math.min(Math.min(Math.min(getOperations(grid, 0, 1), getOperations(grid, 0, 2)),
Math.min(getOperations(grid, 1, 0), getOperations(grid, 1, 2))),
Math.min(getOperations(grid, 2, 0), getOperations(grid, 2, 1)));
}
// Returns the number of operations to turn Y into a and non-Y into b.
private int getOperations(int[][] grid, int a, int b) {
final int n = grid.length;
final int mid = n / 2;
int operations = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// For the 'Y' pattern, before the midpoint, check the diagonal and
// anti-diagonal. After the midpoint, check the middle column.
if ((i < mid && (i == j || i + j == n - 1)) || (i >= mid && j == mid)) {
if (grid[i][j] != a)
++operations;
} else if (grid[i][j] != b) {
++operations;
}
return operations;
}
}
// code provided by PROGIEZ3071. Minimum Operations to Write the Letter Y on a Grid LeetCode Solution in Python
class Solution:
def minimumOperationsToWriteY(self, grid: list[list[int]]) -> int:
n = len(grid)
mid = n // 2
def getOperations(a: int, b: int) -> int:
"""Returns the number of operations to turn Y into a and non-Y into b."""
operations = 0
for i, row in enumerate(grid):
for j, num in enumerate(row):
# For the 'Y' pattern, before the midpoint, check the diagonal and
# anti-diagonal. After the midpoint, check the middle column.
if (i < mid and (i == j or i + j == n - 1)) or i >= mid and j == mid:
if num != a:
operations += 1
elif num != b:
operations += 1
return operations
return min(getOperations(0, 1), getOperations(0, 2),
getOperations(1, 0), getOperations(1, 2),
getOperations(2, 0), getOperations(2, 1))
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.