aboutsummaryrefslogtreecommitdiff
path: root/max_increase_city_skyline.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-11 10:53:54 -0600
committerJack Sangdahl <[email protected]>2024-10-11 10:53:54 -0600
commit38020b428286de57d2ace617e4c5e8845bfa2be9 (patch)
tree92d747f16204ec789f98ca97a29981d779bb3024 /max_increase_city_skyline.c
parent0c21b6ec40d59bedd0dccb8b6049f3b3fe7f344a (diff)
downloadleetcode-38020b428286de57d2ace617e4c5e8845bfa2be9.tar.gz
leetcode-38020b428286de57d2ace617e4c5e8845bfa2be9.zip
807. max increase to keep city skyline
Diffstat (limited to 'max_increase_city_skyline.c')
-rw-r--r--max_increase_city_skyline.c56
1 files changed, 56 insertions, 0 deletions
diff --git a/max_increase_city_skyline.c b/max_increase_city_skyline.c
new file mode 100644
index 0000000..3c9ab23
--- /dev/null
+++ b/max_increase_city_skyline.c
@@ -0,0 +1,56 @@
+// 807. Max Increase to Keep City Skyline
+#include "leetcode.h"
+
+/*
+ * there is a city composed of 'n * n' blocks where each block contains a single
+ * building shaped like a vertical square prism. you are given 0 idxed 'n * n'
+ * integer matrix 'grid' where 'grid[r][c]' represents the height of the
+ * building located in the block at row 'r' and column 'c'. a city's skiline is
+ * the outer contour formed by all the building =hen viewing the side of the
+ * city from a distance. the skyline from a distance. the skyline from each
+ * cardinal direction, north, east, south, and west may be different. we are
+ * allowed to increase the height of any number of buildings by any amount. the
+ * height of a 0-height building can also be increased. however, increasing the
+ * height of a building should not affect the city's skyline from any cardinal
+ * direction. return the maximum total sum that the height of the buildings can
+ * be increased by without changing the city's skyline from any cardinal
+ * direction
+ */
+
+int max_row(int **grid, int size, int idx) {
+ int max = INT_MIN;
+ for (int i = 0; i < size; i++)
+ if (grid[idx][i] > max)
+ max = grid[idx][i];
+ return max;
+}
+
+int max_col(int **grid, int size, int idx) {
+ int max = INT_MIN;
+ for (int i = 0; i < size; i++)
+ if (grid[i][idx] > max)
+ max = grid[i][idx];
+ return max;
+}
+
+int maxIncreaseKeepingSkyline(int **grid, int gridSize, int *gridColSize) {
+ int sum = 0;
+ int row_idx, col_idx, row_max, col_max;
+ for (row_idx = 0; row_idx < gridSize; row_idx++)
+ for (col_idx = 0; col_idx < gridColSize[row_idx]; col_idx++) {
+ row_max = max_row(grid, gridColSize[row_idx], row_idx);
+ col_max = max_col(grid, gridSize, col_idx);
+ sum += row_max > col_max ? col_max - grid[row_idx][col_idx]
+ : row_max - grid[row_idx][col_idx];
+ }
+ return sum;
+}
+
+int main() {
+ int g1[4][4] = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}},
+ g2[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, gcs1 = 4, gcs2 = 3;
+ printf("%d\n", maxIncreaseKeepingSkyline((int **)g1, ARRAY_SIZE(g1),
+ &gcs1)); // expect: 35
+ printf("%d\n", maxIncreaseKeepingSkyline((int **)g2, ARRAY_SIZE(g2),
+ &gcs2)); // expect: 0
+}