Domain 1EasyCORE

Surface Area of 3D Shapes

The problem requires calculating the total surface area of 3D shapes formed by stacking cubes on a grid. Each cell in the `n x n` grid contains a value representing the number of stacked cubes. The goal is to compute the surface area considering that adjacent cubes are glued together, and the bottom face of each shape counts toward its surface area.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

892. Surface Area of 3D Shapes

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 60.0%


Problem Breakdown

The problem requires calculating the total surface area of 3D shapes formed by stacking cubes on a grid. Each cell in the n x n grid contains a value representing the number of stacked cubes. The goal is to compute the surface area considering that adjacent cubes are glued together, and the bottom face of each shape counts toward its surface area.

Inputs:

  • A 2D list (grid) where each element represents the height of a stack of cubes.

Outputs:

  • An integer representing the total surface area of all shapes formed by the stacked cubes.

Implicit Constraints or Tricky Edge Cases:

  • If a cell contains 0, it means there are no cubes, and thus no contribution to the surface area.
  • The grid can be as large as 50x50, so an efficient solution is necessary to handle this size within reasonable time limits.
  • The problem considers both vertical and horizontal adjacency between cubes.

Intuition

A brute-force approach would involve checking each cube individually and calculating its contribution to the surface area based on its neighbors. However, this approach would be inefficient due to its high time complexity (O(n^3)) because it would require iterating over all possible pairs of adjacent cubes.

The key insight is to calculate the surface area for each cell independently and then adjust for any hidden surfaces caused by adjacency between cells. This reduces the problem’s complexity to O(n^2), which is more efficient given the constraints.

Approach

  1. Initialize Total Surface Area: Start with a total surface area of 0.
  2. Iterate Over Each Cell in the Grid:
    • For each cell (i, j), if it contains cubes (grid[i][j] > 0), calculate its initial surface area as 6 * grid[i][j] - 2 * (grid[i][j] - 1) because each cube has 6 faces but the top and bottom faces are hidden.
    • Adjust for Vertical Adjacency:
      • If there is a stack of cubes directly above (i > 0), subtract min(grid[i][j], grid[i-1][j]) * 2 from the surface area because these two faces are hidden between the stacks.
      • If there is a stack of cubes directly to the left (j > 0), subtract min(grid[i][j], grid[i][j-1]) * 2 from the surface area for similar reasons.
  3. Return Total Surface Area: After processing all cells, return the accumulated total surface area.

Complexity Analysis

  • Time Complexity: O(n^2) because we iterate over each cell in the grid once and perform constant-time operations for each cell.
  • Space Complexity: O(1) as we only use a few extra variables to keep track of the total surface area and loop indices.

Solution

def surfaceArea(grid):
    n = len(grid)
    total_surface_area = 0
    
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                # Initial surface area for a single stack of cubes
                initial_surface_area = 6 * grid[i][j] - 2 * (grid[i][j] - 1)
                
                # Subtract hidden surfaces due to vertical adjacency
                if i > 0:
                    total_surface_area -= min(grid[i][j], grid[i-1][j]) * 2
                if j > 0:
                    total_surface_area -= min(grid[i][j], grid[i][j-1]) * 2
                
                # Add to the total surface area
                total_surface_area += initial_surface_area
    
    return total_surface_area

Edge Cases Handled

  • Empty Grid: If the grid is empty (n == 0), the function will correctly return 0 as there are no cubes.
  • Single Cell with No Cubes: If a cell contains 0, it contributes nothing to the surface area, and the calculation skips that cell.
  • Large Grid Size: The solution efficiently handles grids up to 50x50 within acceptable time limits.