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

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

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.

 ```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])

GD Star Rating
a WordPress rating system

798 words
Last Post: Teaching Kids Programming – Geometry of Triangle Area and Side Law

Source: Internet

We are offering free coding tuts

X