aboutsummaryrefslogtreecommitdiff
path: root/making_large_island.py
diff options
context:
space:
mode:
Diffstat (limited to 'making_large_island.py')
-rw-r--r--making_large_island.py51
1 files changed, 51 insertions, 0 deletions
diff --git a/making_large_island.py b/making_large_island.py
new file mode 100644
index 0000000..24e0845
--- /dev/null
+++ b/making_large_island.py
@@ -0,0 +1,51 @@
+# 827. Making A Large Island
+
+"""
+you are given an 'm x n' binary matrix 'grid'. you are allowed to change at
+most one 0 to be 1. return size of the largest island in 'grid' after
+applying this operation. an island is a 4-directionally connected group of
+1's.
+"""
+
+
+class Solution(object):
+ def largestIsland(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ n = len(grid)
+
+ def move(x, y):
+ for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
+ if 0 <= x + i < n and 0 <= y + j < n:
+ yield x + i, y + j
+
+ def dfs(x, y, idx):
+ res = 0
+ grid[x][y] = idx
+ for i, j in move(x, y):
+ if grid[i][j] == 1:
+ res += dfs(i, j, idx)
+ return res + 1
+
+ idx, areas = 2, {0: 0}
+ for x in range(n):
+ for y in range(n):
+ if grid[x][y] == 1:
+ areas[idx] = dfs(x, y, idx)
+ idx += 1
+ ans = max(areas.values())
+ for x in range(n):
+ for y in range(n):
+ if grid[x][y] == 0:
+ valid = set(grid[i][j] for i, j in move(x, y))
+ ans = max(ans, sum(areas[idx] for idx in valid) + 1)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.largestIsland(grid=[[1, 0], [0, 1]]))
+ print(obj.largestIsland(grid=[[1, 1], [1, 0]]))
+ print(obj.largestIsland(grid=[[1, 1], [1, 1]]))