Problem Description

You have an n x n grid where each cell contains a value representing the height of a tower of unit cubes stacked at that position. Specifically, grid[i][j] tells you how many 1 x 1 x 1 cubes are stacked vertically at position (i, j).

Your task is to calculate the total area of all three orthogonal projections (shadows) of this 3D structure:

1. Top view (xy plane): Looking down from above, you see a shadow on the xy plane. Any position with at least one cube (value > 0) contributes 1 unit of area to this projection.

2. Front view (yz plane): Looking from the front along the x-axis, you see a shadow on the yz plane. For each row, the tallest tower in that row determines the height of the shadow. The total area is the sum of maximum values from each row.

3. Side view (zx plane): Looking from the side along the y-axis, you see a shadow on the zx plane. For each column, the tallest tower in that column determines the height of the shadow. The total area is the sum of maximum values from each column.

Return the sum of all three projection areas.

For example, if you have a grid [[1,2],[3,4]]:

• Top view area: 4 (all positions have cubes)
• Front view area: max(1,2) + max(3,4) = 2 + 4 = 6
• Side view area: max(1,3) + max(2,4) = 3 + 4 = 7
• Total: 4 + 6 + 7 = 17

Intuition

To understand how to solve this problem, let's think about what each projection actually represents:

When we look at a 3D structure from different angles, we're essentially "flattening" it onto a 2D plane. The key insight is that each projection captures different information about the structure:

1. Top view (xy plane): When looking down from above, we can't see the height of the cubes - we can only see whether a position is occupied or not. It's like looking at the footprint of a building from a satellite view. Each occupied cell contributes exactly 1 unit of area, regardless of how tall the tower is. So we just need to count how many cells have grid[i][j] > 0.

2. Front view (yz plane): When looking from the front, we see the silhouette of each row. The tallest tower in each row determines the height of that row's shadow. Think of it like looking at a city skyline from the front - for each row of buildings, only the tallest one contributes to the skyline. Therefore, we sum up max(row) for each row.

3. Side view (zx plane): Similarly, when looking from the side, we see the silhouette of each column. The tallest tower in each column determines the height of that column's shadow. We sum up max(column) for each column.

The beauty of this approach is that we can calculate each projection independently and then simply add them together. We don't need to actually construct a 3D model - we just need to extract the relevant information from the 2D grid that represents the heights.

This leads us to the solution: iterate through the grid once to count non-zero values for the xy projection, find the maximum of each row for the yz projection, and find the maximum of each column for the zx projection.

Learn more about Math patterns.

Solution Approach

The implementation follows directly from our understanding of the three projections:

1. Calculate xy plane projection (top view):

xy = sum(v > 0 for row in grid for v in row)

We iterate through every cell in the grid using a nested generator expression. For each value v, we check if it's greater than 0 (indicating at least one cube exists at that position). The sum() function counts how many True values we have, giving us the total footprint area.

2. Calculate yz plane projection (front view):

yz = sum(max(row) for row in grid)

For each row in the grid, we find the maximum value using max(row), which represents the tallest tower in that row. We sum all these maximum values to get the total area of the front projection.

3. Calculate zx plane projection (side view):

zx = sum(max(col) for col in zip(*grid))

This is the trickiest part. We use zip(*grid) to transpose the grid, effectively converting rows into columns. The * operator unpacks the grid rows, and zip() groups elements by their column index. For example, if grid = [[1,2],[3,4]], then zip(*grid) produces [(1,3), (2,4)], where each tuple represents a column. We then find the maximum value in each column and sum them up.

4. Return the total area:

return xy + yz + zx

Simply add all three projection areas together.

The time complexity is O(n²) where n is the grid dimension, as we need to examine each cell at least once. The space complexity is O(1) if we don't count the space used by the generator expressions and zip operation, or O(n) if we consider the temporary column structures created by zip(*grid).

Example Walkthrough

Let's walk through a concrete example with the grid [[2,1,0],[1,0,3],[0,2,1]]:

Grid visualization (heights):
2  1  0
1  0  3
0  2  1

Step 1: Calculate xy plane projection (top view)

Looking down from above, we check which positions have cubes (value > 0):

• Position (0,0): 2 > 0 ✓ contributes 1
• Position (0,1): 1 > 0 ✓ contributes 1
• Position (0,2): 0 = 0 ✗ contributes 0
• Position (1,0): 1 > 0 ✓ contributes 1
• Position (1,1): 0 = 0 ✗ contributes 0
• Position (1,2): 3 > 0 ✓ contributes 1
• Position (2,0): 0 = 0 ✗ contributes 0
• Position (2,1): 2 > 0 ✓ contributes 1
• Position (2,2): 1 > 0 ✓ contributes 1

Total xy projection = 6 (six positions have cubes)

Step 2: Calculate yz plane projection (front view)

Looking from the front, we find the maximum height in each row:

• Row 0: [2, 1, 0] → max = 2
• Row 1: [1, 0, 3] → max = 3
• Row 2: [0, 2, 1] → max = 2

Total yz projection = 2 + 3 + 2 = 7

Step 3: Calculate zx plane projection (side view)

Looking from the side, we find the maximum height in each column:

• Column 0: [2, 1, 0] → max = 2
• Column 1: [1, 0, 2] → max = 2
• Column 2: [0, 3, 1] → max = 3

Total zx projection = 2 + 2 + 3 = 7

Step 4: Sum all projections

Total area = xy + yz + zx = 6 + 7 + 7 = 20

The answer is 20.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the side length of the grid. This is because:

• The xy calculation iterates through all elements in the grid once: O(n²)
• The yz calculation finds the max of each row for n rows, with each max operation taking O(n) time: O(n²)
• The zx calculation uses zip(*grid) to transpose the grid (which takes O(n²) time) and then finds the max of each column for n columns: O(n²)
• Overall: O(n²) + O(n²) + O(n²) = O(n²)

The space complexity is O(n). While the reference answer states O(1), the use of zip(*grid) creates an iterator that generates tuples representing the columns of the grid. In Python 3, zip returns an iterator rather than a list, but when used with max(col) for col in zip(*grid), each column tuple must be materialized, requiring O(n) space for each column as it's processed. However, only one column is held in memory at a time during the generator expression evaluation, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Top View Projection

Pitfall: A common mistake is calculating the top view projection as sum(sum(row) for row in grid), which would sum all the values in the grid. This is incorrect because the top view only cares about whether a position has cubes or not, not how many cubes are stacked there.

Wrong approach:

xy_projection = sum(sum(row) for row in grid)  # WRONG: sums all heights

Correct approach:

xy_projection = sum(value > 0 for row in grid for value in row)  # Counts positions with cubes

2. Confusing Row vs Column Projections

Pitfall: Mixing up which projection corresponds to rows and which to columns. Remember:

• Front view (yz plane) looks along the x-axis → sees one profile per row → use row maximums
• Side view (zx plane) looks along the y-axis → sees one profile per column → use column maximums

Wrong approach:

yz_projection = sum(max(column) for column in zip(*grid))  # WRONG: using columns for yz
zx_projection = sum(max(row) for row in grid)  # WRONG: using rows for zx

Correct approach:

yz_projection = sum(max(row) for row in grid)  # Rows for front view
zx_projection = sum(max(column) for column in zip(*grid))  # Columns for side view

3. Handling Empty Rows or Columns

Pitfall: If the grid could contain empty rows (all zeros), calling max() on an empty sequence would raise a ValueError. While the problem typically guarantees non-empty grids, it's good practice to handle edge cases.

Safer approach:

yz_projection = sum(max(row) if row else 0 for row in grid)
zx_projection = sum(max(column) if column else 0 for column in zip(*grid))

4. Not Understanding the zip(*grid) Transpose

Pitfall: Some developers try to manually iterate through columns using nested loops, which is more error-prone and less readable.

Inefficient approach:

zx_projection = 0
for j in range(len(grid[0])):
    max_in_column = 0
    for i in range(len(grid)):
        max_in_column = max(max_in_column, grid[i][j])
    zx_projection += max_in_column

Better approach:

zx_projection = sum(max(column) for column in zip(*grid))

The zip(*grid) idiom is a Pythonic way to transpose a 2D list and makes the code cleaner and more maintainable.