Surface Area of 3D Shapes

Difficulty: Easy | Acceptance: 70.70% | Paid: No Topics: Array, Math, Geometry, Matrix

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 the cell (i, j).

Return the total surface area of the resulting shapes.

Examples

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

• Examples
• Constraints
• Contribution Method
• Total Area Minus Overlaps
• Voxel Counting (Brute Force)

Contribution Method

Intuition Instead of calculating the total area and subtracting overlaps, we can calculate the contribution of each cell to the surface area individually. Each cell contributes its top and bottom faces, plus the exposed parts of its four side faces based on the height difference with its neighbors.

Steps

• Initialize area to 0.
• Iterate through each cell (i, j) in the grid.
• Add 2 to area for the top and bottom faces of the current tower.
• Check the four adjacent neighbors (up, down, left, right).
• For each neighbor, if it exists, add max(0, current_height - neighbor_height) to area. If the neighbor is out of bounds, add the full current_height (since the side is fully exposed).

class Solution:
    def surfaceArea(self, grid: list[list[int]]) -> int:
        n = len(grid)
        area = 0
        for i in range(n):
            for j in range(n):
                if grid[i][j] > 0:
                    # Top and bottom
                    area += 2
                    # Check 4 neighbors
                    # Up
                    if i > 0:
                        area += max(0, grid[i][j] - grid[i-1][j])
                    else:
                        area += grid[i][j]
                    # Down
                    if i < n - 1:
                        area += max(0, grid[i][j] - grid[i+1][j])
                    else:
                        area += grid[i][j]
                    # Left
                    if j > 0:
                        area += max(0, grid[i][j] - grid[i][j-1])
                    else:
                        area += grid[i][j]
                    # Right
                    if j < n - 1:
                        area += max(0, grid[i][j] - grid[i][j+1])
                    else:
                        area += grid[i][j]
        return area

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Most efficient approach with a single pass.

Total Area Minus Overlaps

Intuition Calculate the surface area of every tower as if it were isolated (4 sides + top + bottom), then subtract the area where adjacent towers touch each other.

Steps

• Calculate the sum of surface areas of all individual towers: sum(4 * height + 2).
• Iterate through the grid to find overlaps between adjacent towers (right and down neighbors).
• For each adjacent pair, subtract 2 * min(height1, height2) from the total area.

class Solution:
    def surfaceArea(self, grid: list[list[int]]) -> int:
        n = len(grid)
        area = 0
        # Calculate total area of isolated towers
        for i in range(n):
            for j in range(n):
                if grid[i][j] > 0:
                    area += grid[i][j] * 4 + 2
        
        # Subtract overlaps
        for i in range(n):
            for j in range(n):
                # Check right neighbor
                if j + 1 < n:
                    area -= min(grid[i][j], grid[i][j+1]) * 2
                # Check down neighbor
                if i + 1 < n:
                    area -= min(grid[i][j], grid[i+1][j]) * 2
                    
        return area

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Conceptually simple, involves two passes over the grid.

Voxel Counting (Brute Force)

Intuition Treat the shape as a collection of 1x1x1 cubes. Iterate through every single cube in the 3D space and check if any of its 6 faces are exposed to air.

Steps

• Iterate through each cell (i, j) in the grid.
• Iterate through the height k of the tower at (i, j) from 0 to grid[i][j] - 1.
• For the cube at (i, j, k), check its 6 neighbors.
• If a neighbor is out of bounds or the height of the neighbor tower is less than or equal to k, the face is exposed. Increment the surface area.

class Solution:
    def surfaceArea(self, grid: list[list[int]]) -> int:
        n = len(grid)
        area = 0
        directions = [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]
        
        for i in range(n):
            for j in range(n):
                for k in range(grid[i][j]):
                    for dx, dy, dz in directions:
                        ni, nj, nk = i + dx, j + dy, k + dz
                        # Check if neighbor is valid and has a cube at this level
                        if not (0 <= ni < n and 0 <= nj < n and 0 <= nk < grid[ni][nj]):
                            area += 1
        return area

Complexity

• Time: O(n² * H) where H is the maximum height in the grid.
• Space: O(1)
• Notes: Easiest to conceptualize but less efficient than the mathematical approaches. Feasible given constraints (n <= 50, H <= 50).