Surface Area of 3D Shapes

Problem

You are given an n x n grid where you have placed some 1 x 1 x 1 cubes. Each value v = grid[i][j] represents a tower of v cubes placed on top of cell (i, j).

After placing these cubes, you have decided to glue any directly adjacent cubes to each other, forming several irregular 3D shapes.

Return the total surface area of the resulting shapes.

Note: The bottom face of each shape counts toward its surface area.

Examples

Example 1

\Huge \begin{array}{|c|c|}\hline 1 & 2 \\\ \hline 3 & 4 \\\ \hline \end{array}

Input: grid = [[1,2],[3,4]]
Output: 34

Example 2

\Huge \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\\ \hline 1 & 0 & 1 \\\ \hline 1 & 1 & 1 \\\ \hline \end{array}

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 3

\Huge \begin{array}{|c|c|c|} \hline 2 & 2 & 2 \\\ \hline 2 & 1 & 2 \\\ \hline 2 & 2 & 2 \\\ \hline \end{array}

Input: grid = [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Constraints

n == grid.length == grid[i].length
1 <= n <= 50
0 <= grid[i][j] <= 50

Solution

Method 1 - Cell-wise Contribution with Neighbor Subtraction

Intuition

Each cube has 6 faces, but adjacent cubes share faces. For each cell, we subtract shared faces with the cell above and to the left. The total is the sum for all cells.

Approach

For each cell, if it contains cubes, it contributes 6 faces per cube, but each shared face with an adjacent cube (up, down, left, right) removes 2 faces from the total. We sum the contributions for all cells.

Complexity

⏰ Time complexity: O(n^2) – We visit each cell of the n x n grid once and perform O(1) work per cell.
🧺 Space complexity: O(1) – Only a few integer accumulators are used.

Code

C++

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int n = grid.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2;
                    if (i > 0) ans -= min(grid[i][j], grid[i-1][j]) * 2;
                    if (j > 0) ans -= min(grid[i][j], grid[i][j-1]) * 2;
                }
            }
        }
        return ans;
    }
};

Go

package solution

func min(a, b int) int {
    if a < b { return a }
    return b
}

func surfaceArea(grid [][]int) int {
    n := len(grid)
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 {
                ans += grid[i][j]*6 - (grid[i][j]-1)*2
                if i > 0 {
                    ans -= min(grid[i][j], grid[i-1][j]) * 2
                }
                if j > 0 {
                    ans -= min(grid[i][j], grid[i][j-1]) * 2
                }
            }
        }
    }
    return ans
}

Java

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

Kotlin

class Solution {
    fun surfaceArea(grid: Array<IntArray>): Int {
        val n = grid.size
        var ans = 0
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (grid[i][j] > 0) {
                    ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2
                    if (i > 0) ans -= minOf(grid[i][j], grid[i-1][j]) * 2
                    if (j > 0) ans -= minOf(grid[i][j], grid[i][j-1]) * 2
                }
            }
        }
        return ans
    }
}

Python

class Solution:
    def surfaceArea(self, grid: list[list[int]]) -> int:
        n = len(grid)
        ans = 0
        for i in range(n):
            for j in range(n):
                if grid[i][j] > 0:
                    ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2
                    if i > 0:
                        ans -= min(grid[i][j], grid[i-1][j]) * 2
                    if j > 0:
                        ans -= min(grid[i][j], grid[i][j-1]) * 2
        return ans

Rust

impl Solution {
    pub fn surface_area(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut ans = 0;
        for i in 0..n {
            for j in 0..n {
                if grid[i][j] > 0 {
                    ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2;
                    if i > 0 {
                        ans -= grid[i][j].min(grid[i-1][j]) * 2;
                    }
                    if j > 0 {
                        ans -= grid[i][j].min(grid[i][j-1]) * 2;
                    }
                }
            }
        }
        ans
    }
}

Typescript

function surfaceArea(grid: number[][]): number {
    const n = grid.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] > 0) {
                ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2;
                if (i > 0) ans -= Math.min(grid[i][j], grid[i-1][j]) * 2;
                if (j > 0) ans -= Math.min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return ans;
}