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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Surface Area of 3D Shapes

Difficulty: Easy

Problem Description

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.

Key Insights

  • Each cube has a total of 6 faces.
  • The surface area contributed by each cube can be reduced by the area of faces that are glued to adjacent cubes.
  • For each cell in the grid, the contribution to the surface area can be calculated based on the number of adjacent cubes in the four cardinal directions (up, down, left, right).
  • The bottom face of each tower also contributes to the surface area.

Space and Time Complexity

Time Complexity: O(n^2) - We iterate through each cell in the n x n grid. Space Complexity: O(1) - We use a constant amount of space for calculations.

Solution

To calculate the total surface area, we will:

  1. Initialize a variable to keep track of the total surface area.
  2. Loop through each cell in the grid.
  3. For each cell, if it has a certain height (value greater than 0), calculate the contribution to the surface area considering the number of faces exposed.
  4. For each cube in the tower, add faces for the top, bottom, and sides that are not adjacent to other cubes.
  5. Return the total surface area after processing all cells.

Code Solutions

def surfaceArea(grid):
    total_area = 0
    n = len(grid)
    
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                # Add top and bottom
                total_area += 2
                # Add sides
                total_area += grid[i][j] * 4
                
                # Subtract overlapping areas with adjacent cubes
                if i > 0:  # Up
                    total_area -= min(grid[i][j], grid[i-1][j])
                if i < n-1:  # Down
                    total_area -= min(grid[i][j], grid[i+1][j])
                if j > 0:  # Left
                    total_area -= min(grid[i][j], grid[i][j-1])
                if j < n-1:  # Right
                    total_area -= min(grid[i][j], grid[i][j+1])
                    
    return total_area
← Back to All Questions