LeetCode Solutions Blog

Projection Area of 3D Shapes

Number: 919

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an n x n grid where each cell (i, j) contains a number representing the height of a tower of 1 x 1 x 1 cubes placed at that cell, determine the total area of the projections ("shadows") of these 3D shapes onto the xy, yz, and zx planes.

Key Insights

The projection onto the xy-plane is the top view; its area is the number of non-zero cells.
The projection onto the yz-plane (front view) is determined by the maximum value in each row.
The projection onto the zx-plane (side view) is determined by the maximum value in each column.
The total area is the sum of the areas of these three projections.

Space and Time Complexity

Time Complexity: O(n^2) – we iterate over all cells in the grid. Space Complexity: O(1) – aside from the input, only constant extra space is used.

Solution

The approach involves:

Iterating over the grid to count non-zero cells for the xy projection.
Simultaneously finding the maximum value in each row for the yz projection.
In a separate loop, computing the maximum value in each column for the zx projection.
Summing these three components gives the total projection area. Using simple loops ensures that the solution remains efficient with an O(n^2) time complexity. The key observation is that each projection can be computed independently based on the grid's properties.

Code Solutions

# Python solution with line-by-line comments

def projectionArea(grid):
    n = len(grid)  # Number of rows (and columns)
    top_view = 0   # For xy projection: count of non-zero cells
    front_view = 0 # For yz projection: sum of maximums of each row
    side_view = 0  # For zx projection: sum of maximums of each column
    
    # Calculate top view and front view
    for i in range(n):
        max_row = 0  # Initialize max of the current row
        for j in range(n):
            # Count non-zero cells for the top projection (xy-plane)
            if grid[i][j] > 0:
                top_view += 1
            # Update the maximum for the current row (yz-plane)
            max_row = max(max_row, grid[i][j])
        front_view += max_row
    
    # Calculate side view by finding the max in every column (zx-plane)
    for j in range(n):
        max_col = 0  # Initialize max of the current column
        for i in range(n):
            max_col = max(max_col, grid[i][j])
        side_view += max_col
    
    # Total projection area is the sum of all three views
    return top_view + front_view + side_view

# Example usage:
# grid = [[1,2],[3,4]]
# print(projectionArea(grid))  # Output: 17