Surface Area of 3D Shapes

1. Determine the dimensions of the 3D space required. This will be N x N x H, where N is the side length of the input grid and H is the maximum height of any tower.
2. Create a 3D boolean array, let's call it shape[N][N][H], to represent the space. Initialize all its values to false.
3. Populate the shape array. For each cell (i, j) in the input grid with value v, set shape[i][j][k] to true for all k from 0 to v-1.
4. Initialize a counter surfaceArea to 0.
5. Iterate through every position (i, j, k) in the shape array.
6. If shape[i][j][k] is true (meaning a cube exists at this position), check its six neighbors (up, down, left, right, front, back).
7. For each of the six directions, if the neighboring position is outside the bounds of the shape array or if the neighbor is false (meaning it's air), it represents an exposed face. Increment surfaceArea by 1.
8. After checking all positions, the value of surfaceArea is the result.

The algorithm begins by creating a 3D boolean grid that is large enough to contain the entire shape. The dimensions will be n x n x max_height. We then iterate through the input grid to populate our 3D shape grid, marking the locations of all the 1x1x1 cubes.

Once the 3D model is built, we calculate the surface area by examining each individual cube. We iterate from (0,0,0) to (n-1, n-1, max_height-1). If we find a cube at (i, j, k), we look at its six neighbors. A face is part of the total surface area if it's not adjacent to another cube. This occurs when a neighbor is outside the grid boundaries or when the neighboring cell in our 3D model is marked as empty. By summing up all such exposed faces, we get the total surface area.

1class Solution {2    public int surfaceArea(int[][] grid) {3        int n = grid.length;4        int maxH = 0;5        for (int i = 0; i < n; i++) {6            for (int j = 0; j < n; j++) {7                maxH = Math.max(maxH, grid[i][j]);8            }9        }10        if (maxH == 0) return 0;11 12        boolean[][][] shape = new boolean[n][n][maxH];13        for (int i = 0; i < n; i++) {14            for (int j = 0; j < n; j++) {15                for (int k = 0; k < grid[i][j]; k++) {16                    shape[i][j][k] = true;17                }18            }19        }20 21        int surfaceArea = 0;22        int[] dr = {0, 0, 0, 0, 1, -1};23        int[] dc = {0, 0, 1, -1, 0, 0};24        int[] dh = {1, -1, 0, 0, 0, 0};25 26        for (int i = 0; i < n; i++) {27            for (int j = 0; j < n; j++) {28                for (int k = 0; k < maxH; k++) {29                    if (shape[i][j][k]) {30                        for (int d = 0; d < 6; d++) {31                            int ni = i + dr[d];32                            int nj = j + dc[d];33                            int nk = k + dh[d];34 35                            if (ni < 0 || ni >= n || nj < 0 || nj >= n || nk < 0 || nk >= maxH || !shape[ni][nj][nk]) {36                                surfaceArea++;37                            }38                        }39                    }40                }41            }42        }43        return surfaceArea;44    }45}

1. Initialize totalArea = 0.
2. Iterate through each cell (i, j) of the n x n grid.
3. For each cell, get the height v = grid[i][j].
4. Top and Bottom Faces: If v > 0, it means there's a tower, so add 2 to totalArea for its top and bottom faces.
5. Side Faces (Front/Back): Calculate the exposed vertical area between the current tower at (i, j) and the one above it at (i-1, j). This is the absolute difference in their heights. Add abs(v - grid[i-1][j]) to totalArea. If i is 0, the tower is at the edge, so the entire front face is exposed; add v.
6. Side Faces (Left/Right): Similarly, calculate the exposed vertical area between the current tower at (i, j) and the one to its left at (i, j-1). Add abs(v - grid[i][j-1]) to totalArea. If j is 0, add v.
7. The main loop only considers overlaps with up and left neighbors. After the loop, the faces on the rightmost and bottommost boundaries of the grid are not yet counted.
8. Add the areas of the rightmost faces: iterate through each row i and add grid[i][n-1] to totalArea.
9. Add the areas of the bottommost faces: iterate through each column j and add grid[n-1][j] to totalArea.
10. Return totalArea.

We can iterate through the grid and for each tower, calculate the area of its exposed faces. The total area is the sum of:

1. The top and bottom faces of all towers.
2. The side faces on the perimeter of the entire 3D shape.
3. The side faces in the 'valleys' between adjacent towers of different heights.

This can be calculated in a single pass. For each cell (i, j) with height v, we add contributions from its top/bottom, front/back, and left/right faces. We handle boundaries by considering the height of a non-existent tower outside the grid as 0.

1class Solution {2    public int surfaceArea(int[][] grid) {3        int n = grid.length;4        int totalArea = 0;5 6        for (int i = 0; i < n; i++) {7            for (int j = 0; j < n; j++) {8                int v = grid[i][j];9                if (v > 0) {10                    // Top and bottom faces11                    totalArea += 2;12                }13 14                // Exposed faces between current and upper cell15                int up = (i > 0) ? grid[i - 1][j] : 0;16                totalArea += Math.abs(v - up);17 18                // Exposed faces between current and left cell19                int left = (j > 0) ? grid[i][j - 1] : 0;20                totalArea += Math.abs(v - left);21            }22        }23 24        // Add the rightmost and bottommost faces which were not covered25        for (int i = 0; i < n; i++) {26            totalArea += grid[i][n - 1]; // Rightmost column faces27            totalArea += grid[n - 1][i]; // Bottommost row faces28        }29 30        return totalArea;31    }32}

1. Initialize surfaceArea = 0.
2. Iterate through each cell (i, j) of the n x n grid.
3. Let v = grid[i][j] be the height of the tower at the current cell.
4. If v > 0, there is a tower. First, add the total surface area of this tower as if it were isolated. An isolated tower of v cubes has a surface area of 4 * v (for the sides) + 2 (for the top and bottom). So, surfaceArea += (4 * v + 2).
5. Now, subtract the area of the faces that are hidden because of adjacent towers. Since we are iterating from top-left to bottom-right, we only need to check for overlaps with the towers that have already been processed: the one above (i-1, j) and the one to the left (i, j-1).
6. Vertical Overlap: If i > 0, there is a tower above. The two towers at (i, j) and (i-1, j) hide a portion of their sides from each other. The area of this shared face is min(v, grid[i-1][j]). Since this face is hidden for both towers, we subtract 2 * min(v, grid[i-1][j]) from the total area.
7. Horizontal Overlap: If j > 0, there is a tower to the left. Similarly, the shared area is min(v, grid[i][j-1]). We subtract 2 * min(v, grid[i][j-1]) from the total area.
8. After iterating through all cells, surfaceArea will hold the correct total.

We iterate through each cell of the grid. For each cell (i, j) containing a tower of height v = grid[i][j], we start by adding the full surface area of that tower as if it stood alone (4*v + 2). Then, we account for the fact that it's adjacent to other towers. As we process the grid in a standard row-by-row, column-by-column fashion, the tower at (i, j) can only be adjacent to previously processed towers at (i-1, j) (above) and (i, j-1) (to the left).

For each of these adjacencies, a certain area is covered up. The area of the shared face between two towers of height v1 and v2 is min(v1, v2). Since this face is covered for both towers, the total reduction in surface area is 2 * min(v1, v2). By subtracting these overlapping areas as we go, we maintain a running total that correctly reflects the surface area of the shape formed by all towers processed so far. This results in a very concise and efficient single-loop solution.

1class Solution {2    public int surfaceArea(int[][] grid) {3        int n = grid.length;4        int surfaceArea = 0;5 6        for (int i = 0; i < n; i++) {7            for (int j = 0; j < n; j++) {8                int v = grid[i][j];9 10                if (v > 0) {11                    // Add surface area of an isolated tower of height v12                    surfaceArea += (v * 4) + 2;13 14                    // Subtract shared face with the tower above15                    if (i > 0) {16                        surfaceArea -= Math.min(v, grid[i - 1][j]) * 2;17                    }18 19                    // Subtract shared face with the tower to the left20                    if (j > 0) {21                        surfaceArea -= Math.min(v, grid[i][j - 1]) * 2;22                    }23                }24            }25        }26        return surfaceArea;27    }28}