aboutsummaryrefslogtreecommitdiff
path: root/min_operations_write_y_grid.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-05 20:41:11 -0700
committerJack Sangdahl <[email protected]>2024-11-05 20:41:11 -0700
commitc1d7914c37d9d8d2371324284a48e20d48d58c92 (patch)
treea9da6d583c60e01a3ef650e1d221fe88576ddb6f /min_operations_write_y_grid.c
parent5954ff6233f867fe746bd049f023dab44f7f5d4c (diff)
downloadleetcode-c1d7914c37d9d8d2371324284a48e20d48d58c92.tar.gz
leetcode-c1d7914c37d9d8d2371324284a48e20d48d58c92.zip
3071. minimum operations to write the letter y on grid
Diffstat (limited to 'min_operations_write_y_grid.c')
-rw-r--r--min_operations_write_y_grid.c60
1 files changed, 60 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);
+}