Problem Description

You have an n x n grid where each cell contains a stack of unit cubes (1×1×1 in size). The value grid[i][j] tells you how many cubes are stacked vertically at position (i, j).

After placing all the cubes, any cubes that touch each other (share a face) are glued together to form one or more 3D shapes. Your task is to calculate the total surface area of all the resulting shapes combined.

Key points to understand:

• Each cell (i, j) in the grid contains grid[i][j] cubes stacked on top of each other
• If grid[i][j] = 3, it means there are 3 cubes stacked vertically at that position
• Adjacent stacks (horizontally or vertically neighboring in the grid) are glued together where they touch
• The bottom face of each shape (touching the ground) counts as part of the surface area
• You need to find the total exposed surface area after all the gluing

For example, if you have two adjacent cells with heights 3 and 2, they share a common face where they touch. The shared area (which would be 2×1 = 2 unit squares) is not counted in the final surface area since it's internal to the glued shape.

The solution calculates the surface area by:

1. Starting with the surface area of each individual tower (2 for top/bottom + 4×height for the sides)
2. Subtracting the areas where adjacent towers touch and are glued together (2× the minimum height of adjacent towers)

Intuition

To find the total surface area, let's think about what happens when we place cubes on the grid.

First, consider a single tower of height v at position (i, j). If this tower stood alone, its surface area would be:

• Top face: 1 unit square
• Bottom face: 1 unit square
• Four side faces: v unit squares each

This gives us 2 + 4v total surface area for an isolated tower.

Now, what happens when towers are adjacent? When two towers touch, they share a common interface that gets glued together. This shared area is no longer part of the external surface - it becomes internal to the combined shape.

The key insight is that when two adjacent towers of heights h1 and h2 touch, they share exactly min(h1, h2) unit squares on their touching faces. Why? Because the shorter tower determines how much contact area exists. For example, if one tower has height 5 and its neighbor has height 3, only the bottom 3 levels actually touch each other.

Since both towers lose this shared area from their surface (one tower loses it from its right face, the other from its left face, for instance), we need to subtract 2 × min(h1, h2) from the total surface area.

This leads to our approach:

1. Start by assuming all towers are isolated: add 2 + 4v for each non-empty tower
2. For each tower, check if it has a neighbor to the left or above (we only check these two directions to avoid double-counting)
3. If there's a neighbor, subtract the shared surface area: 2 × min(current_height, neighbor_height)

By processing each tower and subtracting only the overlapping areas with previously processed neighbors (left and up), we avoid counting any shared interface twice and arrive at the correct total surface area.

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward grid traversal approach where we examine each cell and calculate its contribution to the total surface area.

We iterate through the grid using enumeration to get both indices and values:

for i, row in enumerate(grid):
    for j, v in enumerate(row):

For each cell at position (i, j) with height v:

1. Check if the cell has cubes: If v > 0, we have a tower to process.

2. Add the isolated tower's surface area: We add 2 + v * 4 to our answer. This represents:

   • 2: top and bottom faces (each contributing 1 unit square)
   • v * 4: four vertical sides, each with area v

3. Subtract shared surfaces with the neighbor above: If i > 0 (not in the first row), we check the cell directly above at (i-1, j). The shared surface area between these two towers is min(v, grid[i-1][j]) on each touching face. Since both towers lose this area, we subtract min(v, grid[i-1][j]) * 2.

4. Subtract shared surfaces with the neighbor to the left: If j > 0 (not in the first column), we check the cell to the left at (i, j-1). Similarly, we subtract min(v, grid[i][j-1]) * 2 for the shared interface.

The algorithm only checks neighbors in two directions (up and left) rather than all four directions. This is a clever optimization that prevents double-counting - when we process a cell, we only account for shared surfaces with cells we've already processed. The cells below and to the right will handle their shared surfaces with the current cell when they are processed later.

The time complexity is O(n²) where n is the grid dimension, as we visit each cell once. The space complexity is O(1) as we only use a constant amount of extra space beyond the input.

Example Walkthrough

Let's walk through a small 2×2 grid example to illustrate the solution approach:

grid = [[1, 2],
        [3, 4]]

This represents:

• Position (0,0): 1 cube
• Position (0,1): 2 cubes stacked
• Position (1,0): 3 cubes stacked
• Position (1,1): 4 cubes stacked

Step 1: Process cell (0,0) with height 1

• Add isolated tower surface: 2 + 1*4 = 6
• Check neighbor above (i=0, so no neighbor above)
• Check neighbor to left (j=0, so no neighbor to left)
• Running total: 6

Step 2: Process cell (0,1) with height 2

• Add isolated tower surface: 2 + 2*4 = 10
• Check neighbor above (i=0, so no neighbor above)
• Check neighbor to left at (0,0): height 1
  • Shared surface: min(2, 1) * 2 = 2
  • Subtract 2 from total
• Running total: 6 + 10 - 2 = 14

Step 3: Process cell (1,0) with height 3

• Add isolated tower surface: 2 + 3*4 = 14
• Check neighbor above at (0,0): height 1
  • Shared surface: min(3, 1) * 2 = 2
  • Subtract 2 from total
• Check neighbor to left (j=0, so no neighbor to left)
• Running total: 14 + 14 - 2 = 26

Step 4: Process cell (1,1) with height 4

• Add isolated tower surface: 2 + 4*4 = 18
• Check neighbor above at (0,1): height 2
  • Shared surface: min(4, 2) * 2 = 4
  • Subtract 4 from total
• Check neighbor to left at (1,0): height 3
  • Shared surface: min(4, 3) * 2 = 6
  • Subtract 6 from total
• Running total: 26 + 18 - 4 - 6 = 34

Final Answer: 34

The key insight demonstrated here is that we only check "backwards" (up and left) to avoid double-counting shared surfaces. When tower (1,1) touches tower (1,0), we subtract their shared area once. We don't need tower (1,0) to also subtract this same shared area when checking its right neighbor, as that would double-count the reduction.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n is the dimension of the grid (assuming a square grid), or more precisely O(m × n) where m is the number of rows and n is the number of columns in the grid.

The algorithm uses two nested loops to iterate through each cell in the grid exactly once. For each cell (i, j):

• It performs constant time operations: checking if the value exists, adding surface area contributions (2 + v * 4), and subtracting shared surfaces with adjacent cells
• The comparisons with previous cells (grid[i-1][j] and grid[i][j-1]) are O(1) operations

Therefore, the total time complexity is O(m × n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variable ans to store the running total of surface area
• Loop variables i, j, and v
• No additional data structures are created

The space complexity is constant regardless of the input size, making it O(1).

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

Common Pitfalls

1. Double-Counting Shared Surfaces

The Pitfall: A natural instinct is to check all four neighbors (up, down, left, right) for each cell and subtract the shared surfaces. This leads to double-counting because each shared surface would be subtracted twice - once from each of the two adjacent cells.

Incorrect Approach:

# WRONG: This double-counts shared surfaces
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] > 0:
            total += 2 + grid[i][j] * 4
            # Checking all 4 directions causes double-counting
            for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]):
                    total -= min(grid[i][j], grid[ni][nj]) * 2

The Solution: Only check neighbors in two directions (typically up and left, or down and right). This ensures each shared surface is counted exactly once. The provided solution correctly uses this approach by only checking cells at (i-1, j) and (i, j-1).

2. Forgetting to Multiply by 2 When Subtracting Shared Areas

The Pitfall: When two towers share a surface, both towers lose that surface area. It's easy to forget that we need to subtract the shared area twice (once for each tower).

Incorrect Approach:

# WRONG: Only subtracting once
if row_idx > 0:
    overlap_above = min(height, grid[row_idx - 1][col_idx])
    total_surface_area -= overlap_above  # Should be overlap_above * 2

The Solution: Always multiply the minimum height by 2 when subtracting shared surfaces, as shown in the correct implementation: total_surface_area -= overlap_above * 2

3. Incorrect Base Surface Area Calculation

The Pitfall: Miscalculating the surface area of an isolated tower. Common mistakes include:

• Forgetting the top and bottom faces
• Using incorrect formula for side faces
• Counting each cube individually instead of treating the stack as a single rectangular prism

Incorrect Approaches:

# WRONG: Forgetting top and bottom
total_surface_area += height * 4  

# WRONG: Treating each cube separately (overcomplicated)
total_surface_area += height * 6 - (height - 1) * 2  

The Solution: For a tower of height h, the surface area is 2 + 4h:

• 2 for top and bottom faces (1×1 each)
• 4h for the four vertical sides (each has area h×1)