Create projection-area-of-3d-shapes.py

kamyu104 · web-flow · commit 88a8fe0e7b6a · 2018-08-08T18:55:32.000+08:00
diff --git a/Python/projection-area-of-3d-shapes.py b/Python/projection-area-of-3d-shapes.py
@@ -0,0 +1,65 @@
+# Time:  O(n^2)
+# Space: O(1)
+
+# On a N * N grid, we place some 1 * 1 * 1 cubes
+# that are axis-aligned with the x, y, and z axes.
+#
+# Each value v = grid[i][j] represents a tower of
+# v cubes placed on top of grid cell (i, j).
+#
+# Now we view the projection of these cubes onto
+# the xy, yz, and zx planes.
+#
+# A projection is like a shadow, that maps our
+# 3 dimensional figure to a 2 dimensional plane. 
+#
+# Here, we are viewing the "shadow" when looking at the cubes
+# from the top, the front, and the side.
+#
+# Return the total area of all three projections.
+#
+# Example 1:
+#
+# Input: [[2]]
+# Output: 5
+# Example 2:
+#
+# Input: [[1,2],[3,4]]
+# Output: 17
+# Explanation: 
+# Here are the three projections ("shadows") of
+# the shape made with each axis-aligned plane.
+#
+# Example 3:
+#
+# Input: [[1,0],[0,2]]
+# Output: 8
+# Example 4:
+#
+# Input: [[1,1,1],[1,0,1],[1,1,1]]
+# Output: 14
+# Example 5:
+#
+# Input: [[2,2,2],[2,1,2],[2,2,2]]
+# Output: 21
+#
+# Note:
+# - 1 <= grid.length = grid[0].length <= 50
+# - 0 <= grid[i][j] <= 50
+
+class Solution(object):
+    def projectionArea(self, grid):
+        """
+        :type grid: List[List[int]]
+        :rtype: int
+        """
+        result = 0
+        for i in xrange(len(grid)):
+            max_row, max_col = 0, 0
+            for j in xrange(len(grid)):
+                if grid[i][j]:
+                    result += 1
+                max_row = max(max_row, grid[i][j])
+                max_col = max(max_col, grid[j][i])
+            result += max_row + max_col
+        return result
