title: Leetcode 200. Number of Islands TLE
body: <p>Link to the question: <a href="https://leetcode.com/problems/number-of-islands/" rel="nofollow noreferrer">https://leetcode.com/problems/number-of-islands/</a></p>
  
  <p>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.</p>
  
  <p>Example 1:</p>
  
  <p>Input:</p>
  
  <pre><code>11110
  11010
  11000
  00000
  </code></pre>
  
  <p>Output: 1</p>
  
  <p>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?</p>
  
  <p>class Solution(object):</p>
  
  <pre><code>def numIslands(self, grid):
  
      def in_grid(x, y):
          return 0 &lt;= x &lt; len(grid) and 0 &lt;= y &lt; 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
  </code></pre>