algoadvance

You are given an n x n grid where you have some 3D shapes placed on it. The height of these shapes is given by integers in the grid array. Each cell of the grid has a non-negative integer which represents the height of the 3D shape at that cell.

You need to find the total surface area of these 3D shapes.

The surface area of 3D shapes is calculated as follows:

Each unit cube in the 3D shape contributes 6 to the total surface area (considering all six faces). However, if there are adjacent cubes, the touching faces between them should not be counted as they are not exposed to the outside.

Example:

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

Clarifying Questions

1. Dimensions and Values: What are the constraints on the dimensions of the grid and the possible values within the grid?
   • Constraints: The grid size (n) is between 1 and 50. The height values (grid[i][j]) vary between 0 and 50.
2. Edge Cases:
   • What if the grid is filled with zeros?
     • The surface area should be 0.
   • What if the grid is of size 1x1?
     • The surface area will be 6 * grid[0][0].

Strategy

1. Initial Surface Area Calculation:
   • For each height h in the grid, initially count h * 6 as the surface area because each height contributes that many unit cubes.
2. Adjusting for Adjacent Cubes:
   • Subtract areas for faces that are not exposed because they are between adjacent cubes.
   • Iterate over the grid and subtract the area of the touching faces.
     • For the vertical direction: subtract min(h1, h2) * 2 for each vertical pair of cubes.
     • For the horizontal direction: subtract min(h1, h2) * 2 for each horizontal pair of cubes.

Code

Here is a Python function to calculate the surface area of 3D shapes given the grid of heights.

def surfaceArea(grid):
    n = len(grid)
    area = 0
      
    # Initial Surface Area contribution from all cubes
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                area += (grid[i][j] * 6) - (grid[i][j] - 1) * 2

    # Subtract areas of touching faces in horizontal and vertical directions
    for i in range(n):
        for j in range(n):
            if i < n - 1:
                area -= 2 * min(grid[i][j], grid[i + 1][j])
            if j < n - 1:
                area -= 2 * min(grid[i][j], grid[i][j + 1])

    return area

# Example Usage
grid = [[1,2],[3,4]]
print(surfaceArea(grid))  # Output: 34

Time Complexity

• Time Complexity: O(n^2), where n is the size of the grid. This is because we have to iterate over each cell in the n x n grid and perform constant time operations.
• Space Complexity: O(1), because we are using a fixed amount of extra space regardless of the size of the input grid.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?