algoadvance

Leetcode 883. Projection Area of 3D Shapes

Problem Statement

You are given an array of n n integers grid where grid[i][j] represents the height of a 3D shape located at position (i, j). We need to calculate the projection area of these 3D shapes onto the xy-plane, yz-plane, and zx-plane.

• The projection area on the xy-plane is simply the number of cells that contain a positive height.
• The projection area on the yz-plane is the sum of the maximum heights in each row.
• The projection area on the zx-plane is the sum of the maximum heights in each column.

Return the total projection area of the 3D shapes.

Example:

Example:
Input: grid = [[1,2],[3,4]]
Output: 17
Explanation: Here are the three projections ("shadows") of the shape made with each axis.

Clarifying Questions

• Q: Can grid values be negative?
  • A: No, grid values represent heights and are hence non-negative.
• Q: What are the bounds for the grid size?
  • A: Typically n ranges from 1 to 50.
• Q: Can the grid be non-square?
  • A: No, the grid is always n by n.

Strategy

To solve the problem, we need to calculate the projection areas on three planes:

1. xy-plane: This is simply the count of cells with non-zero heights.
2. yz-plane: For each row, take the maximum height and sum them up.
3. zx-plane: For each column, take the maximum height and sum them up.

Here is how to implement this in Java:

Code

public class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int xy = 0, yz = 0, zx = 0;

        for (int i = 0; i < n; i++) {
            int maxRow = 0;
            int maxCol = 0;
            for (int j = 0; j < n; j++) {
                // xy-plane projection: count if there's a tower at grid[i][j]
                if (grid[i][j] > 0) xy++;
                
                // yz-plane projection: max height in row i
                maxRow = Math.max(maxRow, grid[i][j]);
                
                // zx-plane projection: max height in column j
                maxCol = Math.max(maxCol, grid[j][i]);
            }
            yz += maxRow;
            zx += maxCol;
        }
        
        return xy + yz + zx;
    }
}

Time Complexity

• Time Complexity: O(n^2), where n is the length of the grid. Our nested loops each run for n iterations, leading to an overall O(n^2) complexity.
• Space Complexity: O(1), since we only use a few integer variables to keep track of our sums and max values.

This approach efficiently calculates the projection areas by iterating through the grid in a structured manner, ensuring we account for all three projections correctly.

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?