Scale Engineer

Number of Islands

Med
#0188Time: O(m × n) where m is the number of rows and n is the number of columns. Each cell is visited at most once.Space: O(m × n) in the worst case for the recursion stack (when the grid is filled with land cells)76 companies
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix
Companies
BarclaysByteDanceCiscoComcast

Prompt

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.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

The simplest approach is to use nested loops to iterate through each cell in the grid. When we find a land cell ('1'), we increment our island count and use a separate function to mark all connected land cells as visited to avoid counting them again.

Algorithm

  1. Initialize a counter for the number of islands to 0
  2. Iterate through each cell in the grid using nested loops
  3. When a land cell ('1') is found:
    • Increment the island counter
    • Use DFS to mark all connected land cells as visited by changing them to '0'
  4. Return the island counter

Walkthrough

In this approach, we iterate through each cell in the grid using nested loops. When we encounter a land cell ('1') that hasn't been visited yet, we increment our island count and perform a flood fill operation to mark all connected land cells as visited.

The flood fill can be implemented using either Depth-First Search (DFS) or Breadth-First Search (BFS). For simplicity, we'll use DFS in this implementation.

Here's the implementation:

public int numIslands(char[][] grid) {    if (grid == null || grid.length == 0) {        return 0;    }        int rows = grid.length;    int cols = grid[0].length;    int count = 0;        for (int i = 0; i < rows; i++) {        for (int j = 0; j < cols; j++) {            if (grid[i][j] == '1') {                count++;                dfs(grid, i, j);            }        }    }        return count;} private void dfs(char[][] grid, int row, int col) {    int rows = grid.length;    int cols = grid[0].length;        // Check if out of bounds or not land    if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1') {        return;    }        // Mark as visited by changing '1' to '0'    grid[row][col] = '0';        // Check all four directions    dfs(grid, row + 1, col);    dfs(grid, row - 1, col);    dfs(grid, row, col + 1);    dfs(grid, row, col - 1);}

This approach modifies the input grid to mark visited cells. If we're not allowed to modify the input, we would need to use an additional visited matrix.

Complexity

Time

O(m × n) where m is the number of rows and n is the number of columns. Each cell is visited at most once.

Space

O(m × n) in the worst case for the recursion stack (when the grid is filled with land cells)

Trade-offs

Pros

  • Simple and intuitive approach

  • Easy to implement

  • No additional space required (if we're allowed to modify the input grid)

Cons

  • Modifies the input grid

  • Recursive DFS might cause stack overflow for very large grids

  • Not the most efficient for sparse grids with few land cells

Solutions

using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { public int NumIslands ( char [][] grid ) { var queue = new Queue < Tuple < int , int >>(); var lenI = grid . Length ; var lenJ = lenI == 0 ? 0 : grid [ 0 ]. Length ; var paths = new int [,] { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 } }; var result = 0 ; for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( grid [ i ][ j ] == '1' ) { ++ result ; grid [ i ][ j ] = '0' ; queue . Enqueue ( Tuple . Create ( i , j )); while ( queue . Any ()) { var position = queue . Dequeue (); for ( var k = 0 ; k < 4 ; ++ k ) { var next = Tuple . Create ( position . Item1 + paths [ k , 0 ], position . Item2 + paths [ k , 1 ]); if ( next . Item1 >= 0 && next . Item1 < lenI && next . Item2 >= 0 && next . Item2 < lenJ && grid [ next . Item1 ][ next . Item2 ] == '1' ) { grid [ next . Item1 ][ next . Item2 ] = '0' ; queue . Enqueue ( next ); } } } } } } return result ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem