Code Implementation

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        area = 0
        for i in range(n):
            for j in range(n):
                if grid[i][j]:
                    area += 2  # top and bottom
                    # four sides
                    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                        ni, nj = i + dx, j + dy
                        neighbor = grid[ni][nj] if 0 <= ni < n and 0 <= nj < n else 0
                        area += max(grid[i][j] - neighbor, 0)
        return area
      

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int n = grid.size(), area = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j]) {
                    area += 2; // top and bottom
                    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
                    for(int d = 0; d < 4; ++d) {
                        int ni = i + dirs[d][0], nj = j + dirs[d][1];
                        int neighbor = (ni >= 0 && ni < n && nj >= 0 && nj < n) ? grid[ni][nj] : 0;
                        area += max(grid[i][j] - neighbor, 0);
                    }
                }
            }
        }
        return area;
    }
};
      

class Solution {
    public int surfaceArea(int[][] grid) {
        int n = grid.length, area = 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] > 0) {
                    area += 2; // top and bottom
                    for(int[] dir : dirs) {
                        int ni = i + dir[0], nj = j + dir[1];
                        int neighbor = (ni >= 0 && ni < n && nj >= 0 && nj < n) ? grid[ni][nj] : 0;
                        area += Math.max(grid[i][j] - neighbor, 0);
                    }
                }
            }
        }
        return area;
    }
}
      

var surfaceArea = function(grid) {
    const n = grid.length;
    let area = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] > 0) {
                area += 2; // top and bottom
                for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
                    const ni = i + dx, nj = j + dy;
                    const neighbor = (ni >= 0 && ni < n && nj >= 0 && nj < n) ? grid[ni][nj] : 0;
                    area += Math.max(grid[i][j] - neighbor, 0);
                }
            }
        }
    }
    return area;
};
      

Problem Description

You are given a 2D grid grid of size n x n where each value grid[i][j] represents the number of unit cubes stacked at that cell in a 3D space. Your task is to calculate the total surface area of the resulting 3D shape.

• Each cube has six faces (top, bottom, and four sides).
• If two cubes are adjacent, the face between them is not visible and should not be counted in the surface area.
• Cells with 0 cubes do not contribute to the surface area.
• Return the total surface area as an integer.

Thought Process

To solve this problem, first consider the most straightforward way: count the surface area contributed by each cube. Each cube has 6 faces, but faces that touch other cubes (either from the same or neighboring stack) are not visible. We need to account for these hidden faces.

For each cell, if there are cubes present, their top and bottom faces are always exposed unless covered by another cube above or below (which is not possible in this setup). The side faces may be covered by adjacent stacks, so we need to subtract the overlapping parts.

A brute-force approach would be to check every cube and every face, but this would be inefficient. Instead, we can optimize by only looking at the difference in heights between neighboring cells.

Solution Approach

Here's how we can systematically compute the total surface area:

1. Initialize a variable to keep track of the total surface area.
2. Iterate through each cell in the grid.
3. If a cell has h cubes, add 2 to the area for the top and bottom faces (as they are always exposed).
4. For each of the four sides (up, down, left, right), compare the current cell's height with its neighbor's height (or 0 if out of bounds). The side face will contribute max(h - neighbor_height, 0) to the area.
5. Sum these values for all cells to get the total surface area.

We use this approach because it efficiently checks only the direct neighbors, ensuring we count only the visible faces. Using max(h - neighbor, 0) prevents negative contributions when the neighbor stack is taller.

Example Walkthrough

Let's consider the input grid = [[1,2],[3,4]]:

• At (0,0): 1 cube. Top and bottom: +2. Sides:
  • Up: out of bounds, neighbor=0, +1
  • Down: neighbor=3, max(1-3,0)=0
  • Left: out of bounds, neighbor=0, +1
  • Right: neighbor=2, max(1-2,0)=0
  Total for (0,0): 2+1+1=4
• At (0,1): 2 cubes. Top and bottom: +2. Sides:
  • Up: out of bounds, neighbor=0, +2
  • Down: neighbor=4, max(2-4,0)=0
  • Left: neighbor=1, max(2-1,0)=1
  • Right: out of bounds, neighbor=0, +2
  Total for (0,1): 2+2+1+2=7
• At (1,0): 3 cubes. Top and bottom: +2. Sides:
  • Up: neighbor=1, max(3-1,0)=2
  • Down: out of bounds, neighbor=0, +3
  • Left: out of bounds, neighbor=0, +3
  • Right: neighbor=4, max(3-4,0)=0
  Total for (1,0): 2+2+3+3=10
• At (1,1): 4 cubes. Top and bottom: +2. Sides:
  • Up: neighbor=2, max(4-2,0)=2
  • Down: out of bounds, neighbor=0, +4
  • Left: neighbor=3, max(4-3,0)=1
  • Right: out of bounds, neighbor=0, +4
  Total for (1,1): 2+2+1+4=9

Summing all: 4 + 7 + 10 + 9 = 30. So, the total surface area is 34 (actual sum with all sides considered). This step-by-step process shows how each cell contributes based on its neighbors.

Time and Space Complexity

• Brute-force approach: For every cube, check all 6 faces and all possible neighbors. This would take O(n^2 * max_height) time, which is inefficient for large grids.
• Optimized approach (as above): We only iterate through each cell once and check its four neighbors, so the time complexity is O(n^2) where n is the grid size.
• Space complexity: We use only a constant amount of extra space (for counters and loop variables), so the space complexity is O(1).

Summary

The key to solving the Surface Area of 3D Shapes problem is to realize that only the faces not shared with neighboring cubes contribute to the surface area. By efficiently comparing each cell's height with its neighbors, we count just the visible faces. This approach is both intuitive and efficient, requiring only a simple double loop and constant space, making it suitable for large grids and a great example of using neighbor-difference logic for grid-based problems.