Sponsored
Sponsored
In this approach, we calculate each plane's projection separately, then sum them up for the total projection area. For the XY-plane projection, we count every cell with a positive value. For the YZ-plane, we determine the maximum value in each row (representing the view from the side). For the ZX-plane, we find the maximum value in each column (representing the view from the front).
Time Complexity: O(n^2) since we traverse each grid element once.
Space Complexity: O(1) since we use no additional space proportional to the input size.
1#include <stdio.h>
2
3int projectionArea(int** grid, int gridSize, int* gridColSize) {
4 int xy = 0, yz = 0, zx = 0;
5 for (int i = 0; i < gridSize; i++) {
6 int yz_max = 0;
7 for (int j = 0; j < gridColSize[i]; j++) {
8 if (grid[i][j] > 0) xy++;
9 if (grid[i][j] > yz_max) yz_max = grid[i][j];
10 if (j == 0 || grid[i][j] > zx[j]) zx[j] = grid[i][j];
11 }
12 yz += yz_max;
13 }
14 for (int i = 0; i < gridSize; i++) {
15 zx += zx[i];
16 }
17 return xy + yz + zx;
18}
19
20int main() {
21 int grid[2][2] = {{1,2}, {3,4}};
22 int* gridPtrs[2] = {grid[0], grid[1]};
23 int result = projectionArea(gridPtrs, 2, (int[]){2,2});
24 printf("%d\n", result);
25 return 0;
26}This C implementation uses nested loops to traverse the grid and calculate projection areas separately for each plane, accumulating the resulting areas for the total projection.
This approach improves upon the earlier method by precomputing the maximum values in each row and column before calculating the projections. By storing these values in separate arrays, it helps avoid repeatedly calculating max values within nested loops for each axis projection.
Time Complexity: O(n^2) to fill the grid, row, and column arrays.
Space Complexity: O(n) to store column maximums.
1 public int ProjectionArea(int[][] grid) {
int n = grid.Length;
int[] maxRow = new int[n];
int[] maxCol = new int[n];
int xy = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] > 0) xy++;
maxRow[i] = Math.Max(maxRow[i], grid[i][j]);
maxCol[j] = Math.Max(maxCol[j], grid[i][j]);
}
}
int yz = 0, zx = 0;
for(int i = 0; i < n; i++) {
yz += maxRow[i];
zx += maxCol[i];
}
return xy + yz + zx;
}
public static void Main() {
var sol = new Solution();
int[][] grid = { new int[]{ 1, 2 }, new int[]{ 3, 4 } };
int result = sol.ProjectionArea(grid);
}
}C# approach using extra arrays to track max values per row and column, resulting in an optimized way to get the projection areas without recomputation of these maximum values multiple times.