200. Number of Islands Leetcode Solution

Number of Islands Leetcode Problem :

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return 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.

jump game leetcode

Number of Islands Leetcode Solution :

Constraints :

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is ‘0’ or ‘1’.

Example 1:

  • Input: grid = [
  • Output: 3

Intuition :

Essentially, you traverse the entire grid and keep track of which “1”‘s you’ve already visited. Each time you find a new unvisited “1”, you will run a recursive DFS search to expand and add all the coordinates of the visited “1”‘s to the visited set.

Approach :

In our DFS function, we will first add our current coordinates to the visited set. Next, we will branch out in all four directions, for each of these next coordinates in four directions, if they are:

  1. Within the range of the grid
  2. Equal to “1”
  3. Never visited before

We can run DFS on these next coordinates. Basically, every time you see an unvisited “1”, we will traverse through the entirety of the island and add all “1”‘s connected to the island to our visited set.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription