Surface Area of 3D Shapes

easy array math geometry matrix

Problem

grid[i][j] is the height of a tower of unit cubes at cell (i, j). Return the total surface area of the resulting 3D shape.

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

Output34

Each tower contributes 4·h + 2 (sides + top + bottom). Subtract 2·min(neighbour) for each shared face.

grid (rows separated by ';')

def surfaceArea(grid):
    n = len(grid)
    total = 0
    for i in range(n):
        for j in range(n):
            h = grid[i][j]
            if h: total += 4 * h + 2
            if i: total -= 2 * min(h, grid[i - 1][j])
            if j: total -= 2 * min(h, grid[i][j - 1])
    return total

function surfaceArea(grid) {
  const n = grid.length;
  let total = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const h = grid[i][j];
      if (h) total += 4 * h + 2;
      if (i) total -= 2 * Math.min(h, grid[i - 1][j]);
      if (j) total -= 2 * Math.min(h, grid[i][j - 1]);
    }
  }
  return total;
}

class Solution {
    public int surfaceArea(int[][] grid) {
        int n = grid.length, total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int h = grid[i][j];
                if (h > 0) total += 4 * h + 2;
                if (i > 0) total -= 2 * Math.min(h, grid[i - 1][j]);
                if (j > 0) total -= 2 * Math.min(h, grid[i][j - 1]);
            }
        }
        return total;
    }
}

int surfaceArea(vector<vector<int>>& grid) {
    int n = (int)grid.size(), total = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int h = grid[i][j];
            if (h) total += 4 * h + 2;
            if (i) total -= 2 * min(h, grid[i - 1][j]);
            if (j) total -= 2 * min(h, grid[i][j - 1]);
        }
    return total;
}

Explanation

Each cell holds a tower of cubes of height h. Rather than tracing the whole 3D shape, we add up each tower's exposed faces and then subtract the faces that get hidden where towers touch.

A lone tower of height h shows 4*h side faces plus a top and a bottom, so 4*h + 2. We add that for every non-empty cell.

When two neighbouring towers stand side by side, they hide some faces against each other. The number of shared faces equals the shorter of the two heights, and each shared face hides one square on both towers, so we subtract 2 * min(h, neighbour). To avoid double counting we only look at the neighbour above (grid[i-1][j]) and to the left (grid[i][j-1]).

Example: in [[1,2],[3,4]], the cell with height 2 and its left neighbour height 1 share min(2,1)=1 face, removing 2 from the total. Doing this for every adjacency leaves the final surface area of 34.

It works because every internal face between two cubes is counted once and removed from both sides, leaving only the truly visible surface.

Time: O(n²) Space: O(1)