Jobs

Interviews

Discussions

Surface Area of 3D Shapes

Easy

Asked by:

22 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Surface Area of 3D Shapes

Easy

Asked by:

22 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid? What are the maximum dimensions I should expect?
Are the integer values in the grid non-negative? Is zero a possible value?
Is the input grid guaranteed to be a valid rectangular shape (i.e., all rows have the same number of columns)?
Could you clarify how to handle the boundary of the 3D shape? Are we assuming the shape is enclosed in a tight-fitting box, or is there an infinitely extended surface?
If the input grid is empty (no cubes), what value should I return?

Brute Force Solution

Approach

Imagine each cube in the 3D shape is separate. The brute force strategy calculates the surface area of each cube individually and then subtracts the overlapping faces where cubes are touching.

Here's how the algorithm would work step-by-step:

For every cube, start by assuming it's totally isolated and calculate its total surface area (six faces).
Then, look at each cube and see which of its faces are touching other cubes.
Whenever two cubes share a face, we count that as a reduction in the overall surface area, because that face is no longer exposed to the outside.
Specifically, for each shared face, reduce the total surface area by two (one for each cube sharing that face).
Finally, sum up the surface area of all the cubes after taking into account the reductions from the shared faces.

Code Implementation

def surface_area_3d_brute_force(grid):
    total_surface_area = 0
    number_rows = len(grid)
    number_columns = len(grid[0]) if number_rows > 0 else 0

    for row in range(number_rows):
        for column in range(number_columns):
            cube_height = grid[row][column]

            if cube_height > 0:
                # Each cube initially contributes 6 faces to the total surface area
                total_surface_area += 6 * cube_height

                # Subtract overlapping faces with neighboring cubes

                # Check for overlap with the cube above
                if row > 0:
                    neighbor_height = grid[row - 1][column]
                    total_surface_area -= 2 * min(cube_height, neighbor_height)

                # Check for overlap with the cube to the left
                if column > 0:
                    neighbor_height = grid[row][column - 1]
                    total_surface_area -= 2 * min(cube_height, neighbor_height)

    return total_surface_area

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of cubes and m the maximum height of the grid. We iterate through each of the n cubes. For each cube, we check its neighbors in three dimensions. The height of the grid influences the number of neighbors we need to check. In the worst-case, each cube will need to consider at most m neighbors. Therefore, the total time complexity is O(n*m), representing the product of the number of cubes and the maximum grid height during neighbor comparisons.

Space Complexity

O(1) – The algorithm calculates the surface area by iterating through the input grid and performing arithmetic operations. No auxiliary data structures that scale with the input grid's size are used. Therefore, the space complexity is constant, independent of the input size N (the number of cubes in the 3D shape).

Optimal Solution

Approach

The key to efficiently calculating the surface area of a 3D shape built from cubes is to avoid double-counting areas where cubes touch. Instead of calculating the surface area of each cube individually, we account for how much area is blocked by adjacent cubes.

Here's how the algorithm would work step-by-step:

Imagine each cube has a surface area of 6. Find the total surface area if the cubes were not connected.
Check each cube to see if it has a neighbor on any of its six sides.
Whenever two cubes are neighbors, subtract 2 from the total surface area. This is because the two touching faces are no longer exposed.
Repeat this process for all adjacent cubes.
The final result will be the total surface area, adjusted for the hidden faces.

Code Implementation

def surfaceArea(grid): 
    grid_length = len(grid)
    grid_width = len(grid[0])
    total_surface_area = 0

    for row_index in range(grid_length): 
        for column_index in range(grid_width):
            if grid[row_index][column_index] > 0:
                # Start by assuming each cube contributes its full surface area.
                total_surface_area += 6 * grid[row_index][column_index]

                # Now, subtract the areas of the touching faces.
                # Check for neighbors to the left.
                if row_index > 0:
                    total_surface_area -= 2 * min(grid[row_index][column_index], grid[row_index - 1][column_index])

                # Check for neighbors below.
                if column_index > 0:
                    total_surface_area -= 2 * min(grid[row_index][column_index], grid[row_index][column_index - 1])

    return total_surface_area

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of rows and m be the number of columns in the grid. The algorithm iterates through each cell in the grid to calculate the surface area. For each cell, it checks its neighbors (up to 4 neighbors: left, right, up, down). The grid traversal takes O(n*m) time, and the neighbor check takes constant time for each cell. Therefore, the overall time complexity is determined by the grid traversal, resulting in O(n*m).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that operates directly on the input grid. It does not mention creating any auxiliary data structures like lists, maps, or sets. The algorithm primarily involves checking neighboring cubes and updating a surface area counter. Since the amount of extra memory used does not depend on the input size, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty grid input	Return 0 immediately as there's no shape to calculate surface area for.
Grid with zero dimensions (e.g., grid[0].length == 0)	Return 0 since there is nothing to compute surface area on.
Grid with very large dimensions potentially leading to integer overflow in surface area calculation	Use a long data type to store the surface area to prevent integer overflow.
Cells with extremely large values potentially leading to integer overflow in surface area calculation	Use long to store height values from grid to prevent overflow during computation.
All cells have a value of 0	Return 0 as no cubes exist.
Grid contains only one cube (all other cells are 0)	The surface area will be 6 minus the shared faces which will be properly calculated.
Two adjacent cells have very different heights, maximizing exposed surface area	The surface area difference will be correctly calculated due to the absolute difference in heights.
Grid is a single row or single column	The algorithm handles this case correctly by calculating the exposed faces within the single row or column.

Null or empty grid input

How to Handle:

Return 0 immediately as there's no shape to calculate surface area for.

Grid with zero dimensions (e.g., grid[0].length == 0)

How to Handle:

Return 0 since there is nothing to compute surface area on.

Grid with very large dimensions potentially leading to integer overflow in surface area calculation

How to Handle:

Use a long data type to store the surface area to prevent integer overflow.

Cells with extremely large values potentially leading to integer overflow in surface area calculation

How to Handle:

Use long to store height values from grid to prevent overflow during computation.

All cells have a value of 0

How to Handle:

Return 0 as no cubes exist.

Grid contains only one cube (all other cells are 0)

How to Handle:

The surface area will be 6 minus the shared faces which will be properly calculated.

Two adjacent cells have very different heights, maximizing exposed surface area

How to Handle:

The surface area difference will be correctly calculated due to the absolute difference in heights.

Grid is a single row or single column

How to Handle:

The algorithm handles this case correctly by calculating the exposed faces within the single row or column.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid? What are the maximum dimensions I should expect?
Are the integer values in the grid non-negative? Is zero a possible value?
Is the input grid guaranteed to be a valid rectangular shape (i.e., all rows have the same number of columns)?
Could you clarify how to handle the boundary of the 3D shape? Are we assuming the shape is enclosed in a tight-fitting box, or is there an infinitely extended surface?
If the input grid is empty (no cubes), what value should I return?

Brute Force Solution

Approach

Imagine each cube in the 3D shape is separate. The brute force strategy calculates the surface area of each cube individually and then subtracts the overlapping faces where cubes are touching.

Here's how the algorithm would work step-by-step:

For every cube, start by assuming it's totally isolated and calculate its total surface area (six faces).
Then, look at each cube and see which of its faces are touching other cubes.
Whenever two cubes share a face, we count that as a reduction in the overall surface area, because that face is no longer exposed to the outside.
Specifically, for each shared face, reduce the total surface area by two (one for each cube sharing that face).
Finally, sum up the surface area of all the cubes after taking into account the reductions from the shared faces.

Code Implementation

def surface_area_3d_brute_force(grid):
    total_surface_area = 0
    number_rows = len(grid)
    number_columns = len(grid[0]) if number_rows > 0 else 0

    for row in range(number_rows):
        for column in range(number_columns):
            cube_height = grid[row][column]

            if cube_height > 0:
                # Each cube initially contributes 6 faces to the total surface area
                total_surface_area += 6 * cube_height

                # Subtract overlapping faces with neighboring cubes

                # Check for overlap with the cube above
                if row > 0:
                    neighbor_height = grid[row - 1][column]
                    total_surface_area -= 2 * min(cube_height, neighbor_height)

                # Check for overlap with the cube to the left
                if column > 0:
                    neighbor_height = grid[row][column - 1]
                    total_surface_area -= 2 * min(cube_height, neighbor_height)

    return total_surface_area

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each cube has a surface area of 6. Find the total surface area if the cubes were not connected.
Check each cube to see if it has a neighbor on any of its six sides.
Whenever two cubes are neighbors, subtract 2 from the total surface area. This is because the two touching faces are no longer exposed.
Repeat this process for all adjacent cubes.
The final result will be the total surface area, adjusted for the hidden faces.

Code Implementation

def surfaceArea(grid): 
    grid_length = len(grid)
    grid_width = len(grid[0])
    total_surface_area = 0

    for row_index in range(grid_length): 
        for column_index in range(grid_width):
            if grid[row_index][column_index] > 0:
                # Start by assuming each cube contributes its full surface area.
                total_surface_area += 6 * grid[row_index][column_index]

                # Now, subtract the areas of the touching faces.
                # Check for neighbors to the left.
                if row_index > 0:
                    total_surface_area -= 2 * min(grid[row_index][column_index], grid[row_index - 1][column_index])

                # Check for neighbors below.
                if column_index > 0:
                    total_surface_area -= 2 * min(grid[row_index][column_index], grid[row_index][column_index - 1])

    return total_surface_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid input	Return 0 immediately as there's no shape to calculate surface area for.
Grid with zero dimensions (e.g., grid[0].length == 0)	Return 0 since there is nothing to compute surface area on.
Grid with very large dimensions potentially leading to integer overflow in surface area calculation	Use a long data type to store the surface area to prevent integer overflow.
Cells with extremely large values potentially leading to integer overflow in surface area calculation	Use long to store height values from grid to prevent overflow during computation.
All cells have a value of 0	Return 0 as no cubes exist.
Grid contains only one cube (all other cells are 0)	The surface area will be 6 minus the shared faces which will be properly calculated.
Two adjacent cells have very different heights, maximizing exposed surface area	The surface area difference will be correctly calculated due to the absolute difference in heights.
Grid is a single row or single column	The algorithm handles this case correctly by calculating the exposed faces within the single row or column.

Null or empty grid input

How to Handle:

Return 0 immediately as there's no shape to calculate surface area for.

Grid with zero dimensions (e.g., grid[0].length == 0)

How to Handle:

Return 0 since there is nothing to compute surface area on.

Grid with very large dimensions potentially leading to integer overflow in surface area calculation

How to Handle:

Use a long data type to store the surface area to prevent integer overflow.

Cells with extremely large values potentially leading to integer overflow in surface area calculation

How to Handle:

Use long to store height values from grid to prevent overflow during computation.

All cells have a value of 0

How to Handle:

Return 0 as no cubes exist.

Grid contains only one cube (all other cells are 0)

How to Handle:

The surface area will be 6 minus the shared faces which will be properly calculated.

Two adjacent cells have very different heights, maximizing exposed surface area

How to Handle:

The surface area difference will be correctly calculated due to the absolute difference in heights.

Grid is a single row or single column

How to Handle:

The algorithm handles this case correctly by calculating the exposed faces within the single row or column.