algoadvance

Leetcode 892. Surface Area of 3D Shapes

Problem Statement

You are given an n x n grid where we have n vertical stacks of cubes. Each cell (i, j) in the grid represents a vertical stack of cubes that has grid[i][j] cubes.

Return the total surface area of the resulting shapes formed by these stacks.

Clarifying Questions

  1. Input Constraints:
    • What is the range of the dimensions of the grid (n x n)?
      • Typically, 1 <= n <= 50.
    • What is the range of values for each cell in the grid (grid[i][j])?
      • Typically, 0 <= grid[i][j] <= 50.
  2. Surface Area Definition:
    • How is the surface area calculated?
      • The surface area is calculated as the sum of all exposed faces of all cubes in the grid.
  3. Adjacent Cubes Consideration:
    • Are adjacent cubes considered to reduce the surface area?
      • Yes, faces between adjacent cubes are not counted towards the surface area.

Code

Here is a Java solution to compute the total surface area:

public class SurfaceArea3DShapes {
    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int totalSurfaceArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    // Add surface area of the stack itself
                    totalSurfaceArea += 2 + grid[i][j] * 4;
                    
                    // Subtract surfaces where adjacent cubes touch
                    if (i > 0) {
                        totalSurfaceArea -= Math.min(grid[i][j], grid[i - 1][j]) * 2;
                    }
                    if (j > 0) {
                        totalSurfaceArea -= Math.min(grid[i][j], grid[i][j - 1]) * 2;
                    }
                }
            }
        }

        return totalSurfaceArea;
    }

    public static void main(String[] args) {
        SurfaceArea3DShapes sa = new SurfaceArea3DShapes();
        int[][] grid = {
            {2, 2, 2},
            {2, 1, 2},
            {2, 2, 2}
        };
        System.out.println(sa.surfaceArea(grid)); // Expected surface area
    }
}

Strategy

  1. Initial Surface Area Calculation:
    • For each stack of cubes, the initial surface area is calculated as 2 + grid[i][j] * 4 (since each cube contributes 4 side faces and the top and bottom faces add 2 more).
  2. Adjust for Touching Adjacent Cubes:
    • For adjacent stacks in the grid, subtract the surface areas where they touch. This is done by checking neighbors:
      • If there is a stack above (grid[i-1][j]), subtract the touching surface area.
      • If there is a stack to the left (grid[i][j-1]), subtract the touching surface area.

Time Complexity

This approach ensures that you efficiently compute the surface area considering all edge cases and constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI