Surface Area of 3D Shapes Python Solution

Tested Python solution for LeetCode 892 with 23 pytest cases. Generate a practice environment with lcpy.

LeetCode 892, Easy. Topics: Array, Math, Geometry, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 23 parametrized pytest cases, and a playground notebook:

lcpy gen -n 892   # by problem number
lcpy gen -s surface_area_of_3d_shapes   # by problem name

​

Problem

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.

​

Examples

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

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

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

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2) every cell inspected once with its four neighbours
    # Space: O(1)
    def surface_area(self, grid: list[list[int]]) -> int:
        size = len(grid)
        area = 0
        for row in range(size):
            for col in range(size):
                height = grid[row][col]
                if height == 0:
                    continue
                # Top and bottom faces are always exposed for a non-empty tower.
                area += 2
                # Four side faces per cube, minus what a neighbour hides.
                area += 4 * height
                for d_row, d_col in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    n_row, n_col = row + d_row, col + d_col
                    if 0 <= n_row < size and 0 <= n_col < size:
                        area -= min(height, grid[n_row][n_col])
        return area

​

Complexity

Time	Space
O(n^2) every cell inspected once with its four neighbours	O(1)

​

Tags