#892

Easy

LeetCode Problem Workspace

Surface Area of 3D Shapes

Solve the Surface Area of 3D Shapes problem using array manipulation and mathematical formulas to calculate surface area in a grid of cubes.

array math geometry matrix

Problem Statement

You are given an n x n grid representing towers of cubes. Each cell contains an integer v, which represents the height of a tower at that position. The towers of cubes are placed on top of the cells, and adjacent towers are considered to be glued together. Your task is to calculate the total surface area of all the resulting 3D shapes formed by these towers.

Each cube in the grid has a surface area of 6. The area of the sides that are adjacent to other cubes is not visible, so you need to account for the hidden sides. The goal is to compute the total surface area by taking into account the heights and adjacent cubes in the grid.

Examples

Example 1

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

Output: 34

Example details omitted.

Example 2

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

Output: 32

Example details omitted.

Example 3

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

Output: 46

Example details omitted.

Constraints

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

Solution Approach

Understanding the Basic Structure

Each cell in the grid corresponds to a stack of cubes, and the surface area of the individual stack is 6 times the height. However, adjacent cubes will hide some of the surface area, so we need to subtract the areas that are shared between adjacent towers.

Calculating Exposed Sides

For each tower, consider its exposure to the top, bottom, and four sides. The exposure will vary depending on the relative height of the adjacent towers. Loop through the grid and calculate the exposed surface for each tower by comparing its height with adjacent cells.

Optimizing the Calculation

Instead of recalculating shared sides multiple times, use the difference in heights between adjacent cells to adjust the surface area. This will allow for efficient traversal and minimize redundant calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how the grid is traversed. A straightforward solution involves looping through all cells, making it O(n^2). Space complexity can be O(1) if the result is computed without extra space beyond input, or O(n^2) if additional structures are needed.

What Interviewers Usually Probe

Look for understanding of how adjacency affects surface area calculations.
Evaluate if the candidate considers optimizations for repeated calculations.
Check if the solution correctly handles edge cases like adjacent towers of equal or differing heights.

Common Pitfalls or Variants

Common pitfalls

Failing to account for hidden sides between adjacent cubes.
Overcomplicating the solution when a direct traversal of the grid is sufficient.
Not handling edge cases like empty or minimal grids (e.g., n = 1 or towers with height 0).

Follow-up variants

Consider cases where some cells contain zero cubes.
What happens when the grid contains large numbers or is very sparse?
Can this problem be generalized to irregular 3D shapes?

FAQ

How do I calculate the surface area of cubes in this problem?

Each cube contributes 6 units to the surface area, but you must subtract the area covered by adjacent cubes based on their relative height.

What is the optimal approach for solving the Surface Area of 3D Shapes problem?

Traverse the grid, calculating the exposed surface for each cube while accounting for adjacent cubes. Use efficient comparisons to minimize redundant calculations.

What are the key pitfalls in solving the Surface Area of 3D Shapes problem?

Common pitfalls include overlooking hidden sides, unnecessary complexity in the approach, and not considering edge cases like minimal or zero-height towers.

How does adjacency affect the surface area calculation in this problem?

Adjacent cubes reduce the visible surface area by covering shared sides. The difference in height between adjacent cubes determines how much surface is hidden.

Can I solve this problem with a brute-force approach?

While a brute-force approach is possible, it may not be efficient. Optimizing the calculation of exposed surfaces by considering height differences between adjacent cubes can improve performance.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v:
                    ans += 2 + v * 4
                    if i:
                        ans -= min(v, grid[i - 1][j]) * 2
                    if j:
                        ans -= min(v, grid[i][j - 1]) * 2
        return ans

Continue Practicing

#883 projection area of 3d shapes #1030 matrix cells in distance order #939 minimum area rectangle