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

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/01/08/tmp-grid2.jpg)

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

Example 2

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/01/08/tmp-grid4.jpg)

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

Example 3

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/01/08/tmp-grid5.jpg)

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

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.

Code

C++
 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;
    }
};
Java
 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;
    }
}
Kotlin
 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
    }
}
Python
 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
Rust
 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
    }
}
TypeScript
 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;
}

Explanation

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.

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Complexity

  • ⏰ Time complexity: O(nnnxxxnnn)
  • 🧺 Space complexity: O(nnnxxx)