Pular para o conteúdo principal

Number of Islands

Given a 2D array of integers with ones representing land and zeroes representing water, return the number of islands in the grid.

Note: An island is one or more ones surrounded by water connected either vertically or horizontally.

Example(s)​

Example 1:

Input:
11000
11010
11001

Output: 3
Explanation:
Islands:
1. Top-left: connected 1s at (0,0), (0,1), (1,0), (1,1), (2,0)
2. Middle: single 1 at (1,3)
3. Bottom-right: connected 1s at (2,3), (2,4)

Example 2:

Input:
00100
00010
00001
00001
00010

Output: 4
Explanation:
Islands:
1. Single 1 at (0,2)
2. Single 1 at (1,3)
3. Connected 1s at (2,4), (3,4)
4. Single 1 at (4,3)

Example 3:

Input:
11110
11010
11000
00000

Output: 1
Explanation:
All 1s are connected, forming one large island.

Solution​

The solution uses DFS/BFS to find connected components:

  1. Traverse grid: Visit each cell
  2. Find islands: When we find a 1 (land), it's a new island
  3. Mark visited: Use DFS/BFS to mark all connected 1s as visited
  4. Count islands: Count the number of times we find a new island

JavaScript Solution - DFS

/**
* Count number of islands
* @param {number[][]} grid - 2D array (1=land, 0=water)
* @return {number} - Number of islands
*/
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;

const rows = grid.length;
const cols = grid[0].length;
let islandCount = 0;

/**
 * DFS to mark all connected land as visited
 * @param {number} row - Current row
 * @param {number} col - Current column
 */
function dfs(row, col) {
  // Check bounds and if cell is land
  if (
    row < 0 || row >= rows ||
    col < 0 || col >= cols ||
    grid[row][col] === 0
  ) {
    return;
  }
  
  // Mark as visited (set to 0)
  grid[row][col] = 0;
  
  // Explore 4 directions (horizontally and vertically)
  dfs(row - 1, col); // up
  dfs(row + 1, col); // down
  dfs(row, col - 1); // left
  dfs(row, col + 1); // right
}

// Traverse all cells
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (grid[i][j] === 1) {
      // Found a new island
      islandCount++;
      dfs(i, j); // Mark all connected land as visited
    }
  }
}

return islandCount;
}

// Test cases
const grid1 = [
[1, 1, 0, 0, 0],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 1]
];
console.log('Example 1:', numIslands(grid1)); 
// 3

const grid2 = [
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0]
];
console.log('Example 2:', numIslands(grid2)); 
// 4
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (BFS)​

Here's a BFS version:

/**
 * BFS approach
 */
function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;
  
  const rows = grid.length;
  const cols = grid[0].length;
  let islandCount = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  function bfs(startRow, startCol) {
    const queue = [[startRow, startCol]];
    grid[startRow][startCol] = 0; // Mark as visited
    
    while (queue.length > 0) {
      const [row, col] = queue.shift();
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          grid[newRow][newCol] === 1
        ) {
          grid[newRow][newCol] = 0; // Mark as visited
          queue.push([newRow, newCol]);
        }
      }
    }
  }
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        islandCount++;
        bfs(i, j);
      }
    }
  }
  
  return islandCount;
}

Complexity​

  • Time Complexity: O(m × n) - Where m and n are the dimensions of the grid. We visit each cell at most once.
  • Space Complexity:
    • DFS: O(m × n) - For the recursion stack in worst case
    • BFS: O(min(m, n)) - For the queue in worst case (diagonal island)

Approach​

The solution uses DFS/BFS to find connected components:

  1. Traverse grid:

    • Visit each cell in the grid
    • When we find a 1 (land), it's a new island

  2. Mark connected land:

    • Use DFS/BFS to explore all connected 1s
    • Mark them as visited (set to 0)

  3. Count islands:

    • Each time we find an unvisited 1, increment count
    • This counts the number of connected components

  4. Return count:

    • Return the total number of islands

Key Insights​

  • Connected components: Islands are connected components of 1s
  • 4-directional: Only check up, down, left, right (not diagonals)
  • Mark as visited: Set to 0 to avoid revisiting
  • DFS/BFS: Both work to find connected components
  • O(m×n) time: Must visit all cells

Step-by-Step Example​

Let's trace through Example 1:

Grid:
11000
11010
11001

Traverse cells:
  (0,0): 1 → new island! count = 1
    DFS from (0,0):
      Mark (0,0) = 0
      Check (0,1): 1 → DFS
      Check (1,0): 1 → DFS
      Check (1,1): 1 → DFS
      Check (2,0): 1 → DFS
      All connected 1s marked as 0
  
  Grid after first island:
  00000
  00010
  00001
  
  (0,1): 0 → skip
  (0,2): 0 → skip
  ...
  (1,3): 1 → new island! count = 2
    DFS from (1,3):
      Mark (1,3) = 0
      No connected 1s
  
  (2,3): 1 → new island! count = 3
    DFS from (2,3):
      Mark (2,3) = 0
      Check (2,4): 1 → DFS
      Mark (2,4) = 0
  
  Result: 3 islands

Visual Representation​

Example 1:
11000
11010
11001

Island 1 (top-left):
1 1 0 0 0
1 1 0 0 0
1 0 0 0 0
Connected horizontally/vertically

Island 2 (middle):
0 0 0 1 0
Single cell

Island 3 (bottom-right):
0 0 0 0 1
0 0 0 0 1
Connected vertically

Total: 3 islands

Edge Cases​

  • Empty grid: Return 0
  • All water: Return 0
  • All land: Return 1 (one large island)
  • Single cell: Works correctly
  • No islands: Return 0
  • Diagonal 1s: Not connected (only horizontal/vertical)

Important Notes​

  • 4-directional: Only horizontal and vertical connections (not diagonal)
  • Connected components: All connected 1s form one island
  • Mark as visited: Set to 0 to avoid revisiting
  • DFS/BFS: Both work, DFS is simpler
  • O(m×n) time: Must visit all cells

Why DFS/BFS Works​

Connected components:

  • An island is a connected component of 1s
  • DFS/BFS naturally finds all connected nodes
  • Marking as visited ensures we don't count the same island twice
  • Each unvisited 1 represents a new island
  • Max Area of Island: Find largest island
  • Number of Closed Islands: Different constraint
  • Island Perimeter: Different problem
  • Surrounded Regions: Different problem

Takeaways​

  • DFS/BFS finds connected components
  • 4-directional means up, down, left, right (not diagonals)
  • Mark as visited prevents double counting
  • O(m×n) time is optimal (must visit all cells)
  • Connected components = number of islands