Link to the question: https://leetcode.com/problems/number-of-islands/
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
My logic is to simply do dfs from every node and keep track of the connected components. Am getting Time Limit Exceeded (TLE) for the 46th test case, can someone help me optimize this code?
class Solution(object):
def numIslands(self, grid):
def in_grid(x, y):
return 0 <= x < len(grid) and 0 <= y < len(grid[0])
def neighbours(node):
p, q = node
dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]
return [(x, y) for x, y in [(p + i, q + j) for i, j in dir] if in_grid(x, y)]
def dfs(node):
visited.append(node)
for v in neighbours(node):
if grid[v[0]][v[1]]== "1" and v not in visited:
dfs(v)
components = 0
visited = []
for i in range(len(grid)):
for j in range(len(grid[0])):
node = (i, j)
if grid[i][j] == "1" and node not in visited:
components += 1
dfs(node)
return components
I think your approach is correct. However you are using visited as a list which takes O(n) to search a value. So its overall time complexity is O(N^2). I would suggest to use set rather than list which is a hash table.
There is just two parts to revise:
visited = [] -> visited = set()visited.append(node) ->visited.add(node)I confirmed that it is accepted. Now node not in visited takes O(1) so the overall time complexity is O(N).
% Like most of other LeetCode problems, the problem statement does not give any information about input data. But as your code is TLE so we can assume that we cannot solve it with time complexity O(n^2).