892. Surface Area of 3D Shapes
Problem Description
In this problem, we have a square n x n
grid representing an overhead view of a collection of 3D cubes where each grid cell (i, j)
contains v
cubes, indicated by the value v = grid[i][j]
. Each cube is of size 1 x 1 x 1
. After placing the cubes, we glue any cubes that are directly next to each other on the grid vertically or horizontally. Our task is to determine the total surface area of the joined 3D shapes created.
Each cube on its own has a surface area of 6 units, but when cubes are adjacent, they share walls and reduce the overall surface area. We must account for shared walls between adjacent cubes and also remember that there is an additional bottom surface for the shape formed by cubes at each grid cell.
Intuition
The intuition behind the solution is to do a two-fold computation:
- First, for each tower of cubes, calculate the surface area if it were isolated, i.e., not adjacent to any other cubes. This involves the surface area of the sides and top of the tower.
- Second, subtract the area of the surfaces shared between adjacent towers of cubes.
To break it down:
- We iterate over each cell in the grid:
- For a cell with
v
cubes (wherev > 0
), it has 4 sides, and each will have an area ofv
, plus the top and bottom, each having an area of1
. Hence the total surface area of an isolated tower is2 + v * 4
. - We then check if there is a neighboring tower to the left (west) and above (north):
- If there is a neighbor to the left, we find the minimum of
v
and the height of this neighboring tower. The shared wall's area is this minimum times two (since each shared face between two cubes is equal to 1 x 1 = 1, and we're subtracting from both towers). So we subtract this value from the total surface area. - If there is a neighbor above, perform the same calculation for the shared wall and subtract accordingly.
- If there is a neighbor to the left, we find the minimum of
- For a cell with
- Sum these adjusted surface area values to get the total surface area of the 3D shape.
This approach gives us the correct total surface area of the resulting irregular 3D shape after accounting for all internal and external surfaces.
Learn more about Math patterns.
Solution Approach
The provided solution to finding the total surface area of the resulting 3D shapes formed by gluing 1 x 1 x 1 cubes together in a grid follows an efficient step-by-step approach. Here is a detailed explanation:
-
Initialize a variable
ans
to hold the total surface area count, starting at 0. -
Loop through each cell in the grid with a nested for-loop, using
i
to index rows andj
to index columns:- For each cell at
(i, j)
with a valuev
:- If
v
is greater than 0 (indicating there are cubes),- Add the surface area of an isolated tower of
v
cubes toans
. This is done by adding2
(for the top and bottom of the tower) plus4 * v
for the four vertical sides of the tower.
- Add the surface area of an isolated tower of
- If
- For each cell at
-
Next comes the subtraction of shared walls to account for gluing:
- If the current tower has a neighbor to the left (at
(i, j - 1)
), the shared wall's area to subtract is twice the minimum height of these two towers:min(v, grid[i][j - 1]) * 2
. - If the current tower has a neighbor above (at
(i - 1, j)
), similarly, the shared wall's area is also twice the minimum height of these towers:min(v, grid[i - 1][j]) * 2
. - Subtract these shared wall areas from the
ans
.
- If the current tower has a neighbor to the left (at
-
We ensure the shared walls are only subtracted when there is actually a neighbor. We check that
i
orj
is not at the first row or column by conditionally executing the subtraction only ifi
orj
is greater than 0. -
Continue this process for all cells in the grid.
-
After the loops complete,
ans
contains the correct total surface area. This value is then returned.
In terms of data structures, the solution uses the given grid
directly and an accumulator for the surface area count. There is no need for additional data structures.
The algorithmic pattern demonstrated in this solution is straightforward iteration through grid elements, with conditionals within the nested loops to handle edge cases (literally the edges of the grid). The mathematics behind the area calculations is simple arithmetic involving addition, multiplication, and minimum values.
The result is a solution with time complexity O(n^2), where n
is the dimension of the grid, which is optimal since we must visit each cell at least once, and constant space complexity, as no additional space proportional to the input size is used.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach with an n x n
grid where n = 2
.
Consider the following grid configuration:
1grid = [ 2 [1, 2], 3 [3, 4] 4]
Step 1:
- Initialize
ans
to 0.
Step 2:
- Loop over each cell
(i, j)
ingrid
.
Step 3:
-
At
(0, 0)
, valuev
is1
. There are no neighbors above or to the left. Surface area added toans
is2 (top and bottom) + 4 * v = 2 + 4 * 1 = 6
. -
At
(0, 1)
, valuev
is 2. No neighbors above but there is one to the left. Surface area with sides is2 + 4 * v = 2 + 4 * 2 = 10
. It shares a wall with(0, 0)
, so we subtract the shared surface:min(2, 1) * 2 = 2
. The surface area contributed by this cell is10 - 2 = 8
.
Step 4:
-
At
(1, 0)
,v
is3
. There's a neighbor above but not to the left. Surface area with sides is2 + 4 * v = 2 + 4 * 3 = 14
. Shared wall with(0, 0)
must be subtracted:min(3, 1) * 2 = 2
. The contribution is14 - 2 = 12
. -
At
(1, 1)
,v
is4
. There are neighbors both above and to the left. Surface area with sides is2 + 4 * v = 2 + 4 * 4 = 18
. It shares walls with(0, 1)
and(1, 0)
. Subtractions aremin(4, 2) * 2 = 4
andmin(4, 3) * 2 = 6
. Contribution is18 - 4 - 6 = 8
.
Step 5:
- Sum the adjusted surface areas for each cell:
6 (from (0, 0)) + 8 (from (0, 1)) + 12 (from (1, 0)) + 8 (from (1, 1)) = 34
.
After the final calculation, ans
is 34
, so the total surface area for the shape formed by the cubes in this 2 x 2
grid is 34
units.
Solution Implementation
1class Solution:
2 def surfaceArea(self, grid: List[List[int]]) -> int:
3 # Initialize the surface area to 0
4 surface_area = 0
5
6 # Loop through each cell of the grid
7 for i, row in enumerate(grid):
8 for j, height in enumerate(row):
9 # If the height of the current voxel is not zero
10 if height:
11 # Add the surface area of the current voxel
12 # Each voxel contributes to 2 base/top faces and 4 side faces
13 surface_area += 2 + height * 4
14
15 # If we are not on the first row, subtract the overlapping area
16 # with the voxel directly behind (in the i-1 row)
17 if i:
18 surface_area -= min(height, grid[i - 1][j]) * 2
19
20 # If we are not in the first column, subtract the overlapping area
21 # with the voxel directly on the left (in the j-1 column)
22 if j:
23 surface_area -= min(height, grid[i][j - 1]) * 2
24
25 # Return the total calculated surface area
26 return surface_area
27```
28
29Please note that the `List` type hint assumes that you have imported `List` from `typing` module at the beginning of your script like this:
30```python
31from typing import List
32
1class Solution {
2
3 // Function to calculate the total surface area of 3D shapes
4 public int surfaceArea(int[][] grid) {
5 // Length of the grid (number of rows/columns in the grid)
6 int n = grid.length;
7 // Initialize surface area to 0
8 int totalSurfaceArea = 0;
9
10 // Iterate over each cell in the grid
11 for (int i = 0; i < n; ++i) {
12 for (int j = 0; j < n; ++j) {
13 // If the cell has at least one cube
14 if (grid[i][j] > 0) {
15 // Top and bottom surface area (2) + 4 sides for each cube in the cell
16 totalSurfaceArea += 2 + grid[i][j] * 4;
17
18 // Subtract the area of the sides that are shared with the adjacent cube on the left
19 if (i > 0) {
20 totalSurfaceArea -= Math.min(grid[i][j], grid[i - 1][j]) * 2;
21 }
22
23 // Subtract the area of the sides that are shared with the adjacent cube behind
24 if (j > 0) {
25 totalSurfaceArea -= Math.min(grid[i][j], grid[i][j - 1]) * 2;
26 }
27 }
28 }
29 }
30
31 // Return the total surface area
32 return totalSurfaceArea;
33 }
34}
35
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Calculate the total surface area of 3D shapes represented by a grid
7 int surfaceArea(std::vector<std::vector<int>>& grid) {
8 // Get the size of the grid (which is n x n)
9 int gridSize = grid.size();
10 // Initialize the answer to 0
11 int totalSurfaceArea = 0;
12
13 // Iterate through the grid
14 for (int i = 0; i < gridSize; ++i) {
15 for (int j = 0; j < gridSize; ++j) {
16 // If the current cell is non-zero (a block exists)
17 if (grid[i][j]) {
18 // Each block has a top and bottom face
19 totalSurfaceArea += 2;
20 // Each block also contributes 4 side faces
21 totalSurfaceArea += grid[i][j] * 4;
22 // If there is a block to the north, subtract the hidden area
23 if (i > 0) {
24 totalSurfaceArea -= std::min(grid[i][j], grid[i - 1][j]) * 2;
25 }
26 // If there is a block to the west, subtract the hidden area
27 if (j > 0) {
28 totalSurfaceArea -= std::min(grid[i][j], grid[i][j - 1]) * 2;
29 }
30 }
31 }
32 }
33
34 // Return the totalSurfaceArea calculated
35 return totalSurfaceArea;
36 }
37};
38
1function surfaceArea(grid: number[][]): number {
2 // Get the size of the grid (which is n x n)
3 const gridSize: number = grid.length;
4 // Initialize the total surface area to 0
5 let totalSurfaceArea: number = 0;
6
7 // Iterate through the grid
8 for (let i = 0; i < gridSize; i++) {
9 for (let j = 0; j < gridSize; j++) {
10 // If the current cell is non-zero (a block exists)
11 if (grid[i][j]) {
12 // Each block has a top and bottom face
13 totalSurfaceArea += 2;
14 // Each block also contributes 4 side faces
15 totalSurfaceArea += grid[i][j] * 4;
16 // If there is a block to the north, subtract the hidden area
17 if (i > 0) {
18 totalSurfaceArea -= Math.min(grid[i][j], grid[i - 1][j]) * 2;
19 }
20 // If there is a block to the west, subtract the hidden area
21 if (j > 0) {
22 totalSurfaceArea -= Math.min(grid[i][j], grid[i][j - 1]) * 2;
23 }
24 }
25 }
26 }
27
28 // Return the calculated total surface area
29 return totalSurfaceArea;
30}
31
Time and Space Complexity
Time Complexity
The given code iterates over each cell in the grid
, which has a size n * n
where n
is the length of a side of the grid
. We can assume that the grid is square-shaped since no other shape is indicated. For each cell, a constant amount of work is done: checking the cell value, adding the surface area of the top and bottom, and subtracting the areas that are shared with adjacent blocks (if any).
This leads to a time complexity of O(n^2)
, as it's necessary to visit each cell exactly once, and the amount of work per cell does not depend on the size of the grid.
Space Complexity
The space complexity of the code is O(1)
because no additional space proportional to the size of the input grid is being used. The solution uses a fixed amount of space, as all calculations are done in place, with a single integer ans
holding the accumulated surface area, aside from the input data structure itself.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.