algoadvance

Leetcode 892. Surface Area of 3D Shapes

Problem Statement

You are given an n x n grid where you have placed some 1 x 1 x 1 cubes. Each value grid[i][j] represents the number of cubes stacked at position (i, j).

You need to return the total surface area of the resulting shapes.

Clarifying Questions

1. Input constraints: What is the size range for n and the values within the grid?
   • Answer: Typically, 1 <= n <= 50 and 0 <= grid[i][j] <= 50.
2. Surface area considerations: Do we count the overlapping internal faces between stacked cubes?
   • Answer: Yes, we need to subtract the overlapping faces.

Strategy

• Calculate the surface area for each individual stack of cubes.
• The surface area of each stack can be drafted as follow:
  • Top and Bottom faces always contribute 2 units if there are cubes present.
  • Side faces: Calculate each face (left, right, front, back) individually by comparing the current cell with its neighbors and counting only the visible faces.
• Sum the surface areas of each stack to get the total surface area.
• Decrease overlapping areas between adjacent stacks.

Code

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int n = grid.size();
        int totalSurfaceArea = 0;
        
        // Directions array for side face coverage
        // Up, Down, Left, Right
        vector<pair<int, int>> directions = \{\{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Traverse each cell in the grid
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] > 0) {
                    // Top and bottom faces
                    totalSurfaceArea += 2; 
                    
                    // Side faces
                    for(const auto& dir : directions) {
                        int ni = i + dir.first;
                        int nj = j + dir.second;
                        int neighborHeight = 0;
                        
                        if(ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            neighborHeight = grid[ni][nj];
                        }
                        
                        // Add visible faces
                        totalSurfaceArea += max(grid[i][j] - neighborHeight, 0);
                    }
                }
            }
        }
        return totalSurfaceArea;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> grid = \{\{1,2},{3,4}};
    cout << solution.surfaceArea(grid) << endl;  // Output should be 34
    return 0;
}

Time Complexity

The time complexity of this solution is O(n^2) where n is the size of the grid. This is because each cell in the n x n grid is visited exactly once, and for each cell, we perform a constant amount of work to calculate the surface area.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?