diff options
-rw-r--r-- | min_operations_write_y_grid.c | 60 | ||||
-rw-r--r-- | min_operations_write_y_grid.py | 52 |
2 files changed, 112 insertions, 0 deletions
diff --git a/min_operations_write_y_grid.c b/min_operations_write_y_grid.c new file mode 100644 index 0000000..96f082e --- /dev/null +++ b/min_operations_write_y_grid.c @@ -0,0 +1,60 @@ +// 3071. Minimum Operations to Write the Letter Y on a Grid +#include "leetcode.h" + +/* + * 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 nd + * ending at the center cell of the grid, or the vertical line starting at the + * center cell and ending at the bottom border of the grid. 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 cell to 0, 1, or 2. + */ + +int minimumOperationsToWriteY(int **grid, int gridSize, int *gridColSize) { + int hash_y[4], hash_all[4]; + memset(hash_y, 0, sizeof(hash_y)); + memset(hash_all, 0, sizeof(hash_all)); + int half_length = gridSize / 2; + for (int i = 0; i < gridSize; i++) + for (int j = 0; j < *gridColSize; j++) + hash_all[grid[i][j]]++; + hash_all[3] = gridSize * (*gridColSize); + hash_y[grid[half_length][half_length]]++; + hash_y[3]++; + for (int i = 0; i < half_length; i++) { + hash_y[grid[i][i]]++; + hash_y[grid[i][gridSize - i - 1]]++; + hash_y[grid[half_length + i + 1][half_length]]++; + hash_y[3] += 3; + } + for (int i = 0; i < 4; i++) + hash_all[i] -= hash_y[i]; + int min_ops = INT_MAX, curr_ops; + for (int i = 0; i < 3; i++) { + curr_ops = hash_y[3] - hash_y[i] + hash_all[i]; + for (int j = 0; j < 3; j++) + if (i != j) + min_ops = fmin(min_ops, curr_ops); + } + return min_ops; +} + +int main() { + int g1i[3][3] = {{1, 2, 2}, {1, 1, 0}, {0, 1, 0}}; + int g2i[5][5] = {{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}}; + struct two_d_arr g1, g2; + two_d_arr_init(&g1, 3, 3, g1i); + two_d_arr_init(&g2, 5, 2, g2i); + printf("%d\n", minimumOperationsToWriteY(g1.arr, g1.row_size, + g1.col_size)); // expect: 3 + printf("%d\n", minimumOperationsToWriteY(g2.arr, g2.row_size, + g2.col_size)); // expect: 12 + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} diff --git a/min_operations_write_y_grid.py b/min_operations_write_y_grid.py new file mode 100644 index 0000000..229ba22 --- /dev/null +++ b/min_operations_write_y_grid.py @@ -0,0 +1,52 @@ +# 3071. Minimum Operations to Write the Letter Y on a Grid +from collections import Counter +from itertools import chain + +""" +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 nd +ending at the center cell of the grid, or the vertical line starting at the +center cell and ending at the bottom border of the grid. 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 cell to 0, 1, or 2. +""" + + +class Solution(object): + def minimumOperationsToWriteY(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + n1 = len(grid) + n2 = n1 // 2 + y = ((grid[i][i], grid[n1 - i - 1][n2], grid[i][n1 - i - 1]) for i in range(n2)) + cnt1 = Counter(chain(*grid)) + cnt1[grid[n2][n2]] += 1 + cnt2 = Counter(chain(*grid)) - cnt1 + return n1 * n1 - max( + cnt1[0] + cnt2[1], + cnt1[1] + cnt2[0], + cnt1[0] + cnt2[2], + cnt1[2] + cnt2[0], + cnt1[1] + cnt2[2], + cnt1[2] + cnt2[1], + ) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumOperationsToWriteY(grid=[[1, 2, 2], [1, 1, 0], [0, 1, 0]])) + print( + obj.minimumOperationsToWriteY( + 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], + ] + ) + ) |