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].length1 <= n <= 500 <= grid[i][j] <= 50In #892 Surface Area of 3D Shapes, the grid represents stacks of unit cubes placed on a 2D matrix. The key idea is to calculate the total exposed surface area contributed by each stack. Every stack potentially contributes multiple faces, but some faces become hidden when cubes touch each other.
A practical approach is to iterate through the matrix using standard array traversal. For each cell, consider how many faces of the stack remain visible. Internal faces shared between vertically stacked cubes are not exposed, and adjacent cells in the grid may also hide faces when their stacks touch. By comparing a cell with its top, bottom, left, and right neighbors, you can determine how many faces remain visible.
This method works efficiently because each grid cell is processed once while checking a constant number of neighbors. The algorithm therefore scales linearly with the grid size and requires minimal additional memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Grid traversal with neighbor comparison | O(n × m) | O(1) |
Mario's Math Tutoring
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems similar to Surface Area of 3D Shapes can appear in coding interviews because they test grid traversal and spatial reasoning. While the exact question may not always appear, variations involving matrix processing and counting exposed surfaces are common in interview practice.
A 2D array (matrix) is the primary data structure used for this problem. It naturally represents the grid of cube stacks and allows easy access to neighboring cells. With simple index checks, you can compare adjacent heights and determine hidden surfaces.
The optimal approach is to traverse the grid and compute the visible faces contributed by each stack of cubes. While iterating, compare the current cell with its neighboring cells to subtract faces that are hidden due to adjacent stacks. This ensures each cell is processed once, giving an efficient linear solution.
Neighboring cells represent adjacent stacks of cubes that can hide each other's faces. By comparing heights between cells, you can determine which faces are internal and should not be counted in the surface area. This avoids double-counting shared faces.