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} $$

1
2

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} $$

1
2

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} $$

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
}