We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Surface Area of 3D Shapes

Number: 928

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an n x n grid where grid[i][j] represents a tower of 1 x 1 x 1 cubes stacked on the cell (i, j), compute the total surface area of the resulting 3D shapes after gluing together adjacent cubes. Note that the bottom of each shape contributes to the surface area.

Key Insights

  • Each non-zero cell contributes top and bottom surfaces (2 faces).
  • For every side (up, down, left, right), the contribution is the difference between the current cell's height and its neighbor's height, only if the current cell is taller.
  • If a neighbor doesn't exist (i.e., the cell is at the boundary), treat neighbor height as 0.
  • Iterate over all cells and sum up contributions from top, bottom, and all four sides.

Space and Time Complexity

Time Complexity: O(n²) since we traverse each cell once. Space Complexity: O(1) extra space (not counting input storage).

Solution

The approach involves iterating through the entire grid. For each cell, if its value is v > 0, add 2 to the surface area accounting for the top and bottom surfaces. Then, for each of the four sides (up, down, left, and right), compare the current cell's height v with the adjacent cell's height (or 0 for boundaries). The contribution from that side is max(v - neighbor, 0). This allows us to correctly account for overlapped surfaces when cubes are adjacent. The overall total is the sum of contributions from each cell across the grid.

Code Solutions

# Python implementation with thorough comments

def surfaceArea(grid):
    n = len(grid)  # grid is n x n
    total_area = 0
    # Iterate over each cell in the grid
    for i in range(n):
        for j in range(n):
            height = grid[i][j]
            if height > 0:
                # Each cell has a top and bottom surface if there is at least one cube
                total_area += 2
            # Check all four adjacent directions
            # Up direction:
            up = grid[i - 1][j] if i > 0 else 0
            total_area += max(height - up, 0)
            # Down direction:
            down = grid[i + 1][j] if i < n - 1 else 0
            total_area += max(height - down, 0)
            # Left direction:
            left = grid[i][j - 1] if j > 0 else 0
            total_area += max(height - left, 0)
            # Right direction:
            right = grid[i][j + 1] if j < n - 1 else 0
            total_area += max(height - right, 0)
    return total_area

# Example usage:
print(surfaceArea([[1,2],[3,4]]))  # Expected output: 34
← Back to All Questions