Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/892.html

892. Surface Area of 3D Shapes (Easy)

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

 

Example 1:

Input: [[2]]
Output: 10

Example 2:

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

Example 3:

Input: [[1,0],[0,2]]
Output: 16

Example 4:

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

Example 5:

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

 

Note:

  • 1 <= N <= 50
  • 0 <= grid[i][j] <= 50

Solution 1.

  • class Solution {
        public int surfaceArea(int[][] grid) {
            int area = 0;
            int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
            int rows = grid.length, columns = grid[0].length;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    int cell = grid[i][j];
                    int curArea = cell == 0 ? 0 : cell * 4 + 2;
                    for (int[] direction : directions) {
                        int newRow = i + direction[0], newColumn = j + direction[1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) {
                            int adjacent = grid[newRow][newColumn];
                            int overlapArea = Math.min(cell, adjacent);
                            curArea -= overlapArea;
                        }
                    }
                    area += curArea;
                }
            }
            return area;
        }
    }
    
    ############
    
    class Solution {
        public int surfaceArea(int[][] grid) {
            int n = grid.length;
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] > 0) {
                        ans += 2 + grid[i][j] * 4;
                        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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/surface-area-of-3d-shapes/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        int surfaceArea(vector<vector<int>>& grid) {
            int N = grid.size(), area = 0;
            for (int i = 0; i < N; ++i) {
                int prev = 0;
                for (int j = 0; j < N; ++j) {
                    if (grid[i][j]) area += 2;
                    area += abs(grid[i][j] - prev);
                    prev = grid[i][j];
                }
                area += prev;
            }
            for (int i = 0; i < N; ++i) {
                int prev = 0;
                for (int j = 0; j < N; ++j) {
                    area += abs(grid[j][i] - prev);
                    prev = grid[j][i];
                }
                area += prev;
            }
            return area;
        }
    };
    
  • class Solution:
        def surfaceArea(self, grid: List[List[int]]) -> int:
            ans = 0
            for i, row in enumerate(grid):
                for j, v in enumerate(row):
                    if v:
                        ans += 2 + v * 4
                        if i:
                            ans -= min(v, grid[i - 1][j]) * 2
                        if j:
                            ans -= min(v, grid[i][j - 1]) * 2
            return ans
    
    ############
    
    class Solution(object):
        def surfaceArea(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            area = 0
            n = len(grid)
            for i in range(n):
                for j in range(n):
                    if grid[i][j]: area += grid[i][j] * 4 + 2
                    if i: area -= min(grid[i][j], grid[i-1][j]) * 2
                    if j: area -= min(grid[i][j], grid[i][j-1]) * 2
            return area
    
  • func surfaceArea(grid [][]int) int {
    	ans := 0
    	for i, row := range grid {
    		for j, v := range row {
    			if v > 0 {
    				ans += 2 + v*4
    				if i > 0 {
    					ans -= min(v, grid[i-1][j]) * 2
    				}
    				if j > 0 {
    					ans -= min(v, grid[i][j-1]) * 2
    				}
    			}
    		}
    	}
    	return ans
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions