algoadvance

Leetcode 883. Projection Area of 3D Shapes

Problem Statement

In a 2D grid of size n x n, there are n x n 3D shapes. Each shape is represented by an integer value grid[i][j] where grid[i][j] indicates the height of the 3D shape at position (i, j).

The projection of these shapes onto the xy-plane, yz-plane, and zx-plane are outlines that form shadows. We need to calculate the total area of these projections.

• The projection on the xy-plane results in a grid where we count each occupied cell (i.e., each cell where the height is greater than 0).
• The projection on the yz-plane involves taking the maximum height in each column.
• The projection on the zx-plane involves taking the maximum height in each row.

Your task is to write a function that calculates the total area of these projections.

Clarifying Questions

1. What is the range of values in grid[i][j]?
2. Is it guaranteed that the grid is always n x n?
3. Can the height of the 3D shapes (grid[i][j]) be zero?

Code

Here is a function to solve the problem:

#include <vector>
#include <algorithm>

using namespace std;

int projectionArea(vector<vector<int>>& grid) {
    int n = grid.size();
    int xyArea = 0, yzArea = 0, zxArea = 0;

    // Iterate through each row and column
    for (int i = 0; i < n; ++i) {
        int maxRow = 0;
        int maxCol = 0;
        for (int j = 0; j < n; ++j) {
            // For xy projection, count all non-zero heights
            if (grid[i][j] > 0) {
                xyArea++;
            }
            // For zx projection, find the maximum height in the row
            maxRow = max(maxRow, grid[i][j]);
            // For yz projection, find the maximum height in the column
            maxCol = max(maxCol, grid[j][i]);
        }
        zxArea += maxRow;
        yzArea += maxCol;
    }

    return xyArea + yzArea + zxArea;
}

Strategy

1. XY Plane:
   • Iterate through each cell in the grid.
   • Count cells where the height is greater than 0 (each such cell contributes to the xy projection).
2. YZ Plane:
   • For each column, find the maximum height in that column.
   • Sum these maximum heights to get the yz projection area.
3. ZX Plane:
   • For each row, find the maximum height in that row.
   • Sum these maximum heights to get the zx projection area.

Finally, sum all three areas to get the total projection area.

Time Complexity

• The time complexity of this solution is (O(n^2)) since we need to iterate through an n x n grid to compute the areas of all three projections.
• This is efficient given the constraints and ensures that we capture all the necessary details from the 3D shapes on the grid.

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?