Teaching Kids Programming – Algorithms to Count Surface Area of 3D Shapes (Geometry and Math)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Algorithms to Count Surface Area of 3D Shapes (Geometry and Math)

For a vertical tower of N cubes, there are 4*N+2 surfaces e.g. 1 top, 1 bottom, and 4*N surfaces for each cube. We can add up all surfaces but have to minus the connected parts between neighbour towers. For each tower of cubes, we can check its north and west, and subtract the common parts. This can be done by computing the shorter tower times two.

For the cubes of the first row (top), and the first column (left-most), there are none connected parts of the left and upwards.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n, res = len(grid), 0
        for i in range(n):
            for j in range(n):
                if grid[i][j]: 
                    res += 2 + grid[i][j] * 4
                if i: # i > 0
                    res -= min(grid[i][j], grid[i - 1][j]) * 2
                if j: # j > 0 
                    res -= min(grid[i][j], grid[i][j - 1]) * 2
        return res

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n, res = len(grid), 0
        for i in range(n):
            for j in range(n):
                if grid[i][j]: 
                    res += 2 + grid[i][j] * 4
                if i: # i > 0
                    res -= min(grid[i][j], grid[i - 1][j]) * 2
                if j: # j > 0 
                    res -= min(grid[i][j], grid[i][j - 1]) * 2
        return res

Another algorithm is to add:

We can solve this problem by iterating over the grid and counting the total surface area of each cube in the grid.

For each cube, we count the surface area of the top and bottom faces, which is simply the area of the face if the height is non-zero. We also count the surface area of each side face, which is equal to the difference between the height of the current cube and the height of the adjacent cube in that direction. Note that we only count the surface area if the adjacent cube has a lower height than the current cube, since we only count the exposed surface area.

Finally, we add up all the surface areas of all the cubes to get the total surface area of the 3D shape.

Time Complexity:

The time complexity of this solution is O(n^2), where n is the length of the input grid. This is because we need to iterate over all n^2 cubes in the grid.

Space Complexity:

The space complexity of this solution is O(1), since we are not using any extra space in addition to the input grid.

Here is the Python code for the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        total_area = 0
 
        for i in range(n):
            for j in range(n):
                if grid[i][j] != 0:
                    # count top and bottom surface area
                    total_area += 2
                    
                    # count side surface area for adjacent cubes
                    if i == 0:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i-1][j])
                        
                    if i == n-1:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i+1][j])
                        
                    if j == 0:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i][j-1])
                        
                    if j == n-1:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i][j+1])
                            
        return total_area

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        total_area = 0

        for i in range(n):
            for j in range(n):
                if grid[i][j] != 0:
                    # count top and bottom surface area
                    total_area += 2
                    
                    # count side surface area for adjacent cubes
                    if i == 0:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i-1][j])
                        
                    if i == n-1:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i+1][j])
                        
                    if j == 0:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i][j-1])
                        
                    if j == n-1:
                        total_area += grid[i][j]
                    else:
                        total_area += max(0, grid[i][j] - grid[i][j+1])
                            
        return total_area

3D Shape Algorithms

• Teaching Kids Programming – Algorithms to Count Surface Area of 3D Shapes (Geometry and Math)
• How to Compute the Surface Area of 3D Shapes (Cubes Placed on Grid Cells)?
• How to Compute the Projection Area of 3D Shapes?

–EOF (The Ultimate Computing & Technology Blog) —