{x}
blog image

Surface Area of 3D Shapes

You are given an n x n grid where you have placed some 1 x 1 x 1 cubes. Each value v = grid[i][j] represents a tower of v cubes placed on top of cell (i, j).

After placing these cubes, you have decided to glue any directly adjacent cubes to each other, forming several irregular 3D shapes.

Return the total surface area of the resulting shapes.

Note: The bottom face of each shape counts toward its surface area.

 

Example 1:

Input: grid = [[1,2],[3,4]]
Output: 34

Example 2:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 3:

Input: grid = [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

 

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] <= 50

Solution Explanation:

The problem asks to calculate the total surface area of a 3D shape formed by stacking 1x1x1 cubes on a grid. The solution leverages the observation that we can efficiently compute the surface area by considering each cube individually and subtracting the areas where cubes are adjacent.

Approach:

  1. Initialization: We initialize the total surface area ans to 0.

  2. Iterating Through Cubes: The code iterates through each cell (i, j) of the grid and the corresponding cube height v = grid[i][j].

  3. Individual Cube Area: If a cell contains a cube (v > 0), we add the surface area of that individual cube. A single 1x1x1 cube has 6 faces, so its surface area is 6. However, we initially calculate 2 + v * 4. The 2 accounts for the top and bottom faces, while v * 4 accounts for the four sides.

  4. Subtracting Overlapping Areas: We subtract the areas where adjacent cubes overlap. This is done for the cube to the left (j > 0) and the cube above (i > 0). min(v, grid[i-1][j]) * 2 calculates the overlapping area with the cube above (multiplied by 2 because there's an overlap on two sides), and similarly for the cube to the left.

  5. Return Total Area: Finally, the function returns the total surface area ans.

Time and Space Complexity Analysis:

  • Time Complexity: O(N^2), where N is the size of the grid (N x N). This is because the code iterates through each cell of the grid once.

  • Space Complexity: O(1). The solution uses a constant amount of extra space, regardless of the input size. It only uses a few variables to store the intermediate results.

Code Explanation (Python):

The Python code directly implements the algorithm described above. The nested loops iterate over each cell. The conditional statement (if v:) ensures we only calculate the surface area for cells with cubes. The min() function efficiently handles the overlap calculations, preventing double-counting of shared surfaces.

Code Explanation (Other Languages):

The Java, C++, and Go codes follow the same logic and algorithmic steps as the Python code. The only differences are in syntax and specific library functions used (e.g., Math.min() in Java). The core idea of iterating, calculating individual cube area, subtracting overlaps, and accumulating the total remains consistent across all languages.