Jobs

Interviews

Discussions

Number of Islands

#2 Most AskedMedium

Number of Islands #2 Most Asked

Medium

Waymo

27 views

Topics:

ArraysGraphsRecursion

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'.

Try coding it in LeetCode

Number of Islands

#2 Most AskedMedium

Number of Islands #2 Most Asked

Medium

Waymo

27 views

Topics:

ArraysGraphsRecursion

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'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible dimensions of the grid, and are there any constraints on the number of rows or columns?
Can the grid be empty, meaning it has zero rows or zero columns?
Is it guaranteed that the grid will only contain '1's and '0's, or could other characters be present?
Are the '1's and '0's always represented as strings, or could they be integers?
If the grid is extremely large, are there any specific memory or time complexity requirements I should aim for beyond the standard optimal solution?

Brute Force Solution

Approach

The 'Number of Islands' problem asks us to count distinct landmasses surrounded by water on a map. The brute force strategy involves systematically exploring every piece of land and water on the map to identify and count these islands.

Here's how the algorithm would work step-by-step:

Imagine you have a map with land and water. We need to count how many separate land areas there are.
Let's pick a spot on the map.
If this spot is land, we've found a potential start of an island. We then need to explore all connected land pieces that belong to this same island.
As we explore the connected land, we should mark these pieces so we don't count them again as part of a new island.
Once we've explored all the land connected to our starting spot, we've fully identified one island.
Now, we move to the next spot on the map.
If this new spot is land and we haven't marked it already, it means we've found a new, distinct island. We repeat the exploration and marking process.
If the spot is water or already marked land, we simply move on to the next spot.
We continue this process for every single spot on the map, counting each time we discover a new, unmarked piece of land that leads to exploring a brand new island.
The total count of times we found a new island is our answer.

Code Implementation

def number_of_islands_brute_force(grid):    if not grid:
        return 0

    rows = len(grid)
    columns = len(grid[0])
    number_of_islands = 0

    def explore_island(current_row, current_column):
        # Ensure we are within bounds and on land ('1') that hasn't been visited
        if (current_row < 0 or current_row >= rows or
            current_column < 0 or current_column >= columns or
            grid[current_row][current_column] == '0'):
            return

        # Mark the current land piece as visited by changing it to '0'
        grid[current_row][current_column] = '0'

        # Explore all adjacent land pieces recursively
        explore_island(current_row + 1, current_column)
        explore_island(current_row - 1, current_column)
        explore_island(current_row, current_column + 1)
        explore_island(current_row, current_column - 1)

    # Iterate through each cell of the grid
    for row_index in range(rows):
        for column_index in range(columns):
            # If we find an unvisited piece of land, it signifies the start of a new island
            if grid[row_index][column_index] == '1':
                number_of_islands += 1
                explore_island(row_index, column_index)

    return number_of_islands

Big(O) Analysis

Time Complexity

O(M*N) – Let M be the number of rows and N be the number of columns in the grid. The algorithm iterates through each cell of the grid once. When a land cell ('1') is encountered and it hasn't been visited yet, a traversal (like Depth First Search or Breadth First Search) is initiated. This traversal visits all connected land cells belonging to the same island. Crucially, each cell in the grid is visited at most a constant number of times (once during the initial scan and potentially again during a traversal, but never more than once as part of an island exploration). Therefore, the total number of operations is proportional to the total number of cells in the grid, which is M * N.

Space Complexity

O(m * n) – The primary auxiliary space utilized is for the recursion stack during the depth-first search (DFS) or breadth-first search (BFS) exploration of connected land. In the worst-case scenario, where the entire grid is a single island, the recursion depth (or queue size for BFS) can reach up to m * n, where m is the number of rows and n is the number of columns. Additionally, the grid itself is often modified in-place to mark visited land cells, which does not count as auxiliary space. Therefore, the dominant factor in auxiliary space complexity is the recursion stack, leading to O(m * n).

Optimal Solution

Approach

The core idea is to explore the map systematically, finding land and then 'sinking' it to avoid recounting. We'll use a process that's like dipping a paintbrush into the water and marking all connected land pieces we find.

Here's how the algorithm would work step-by-step:

Imagine you have a map with land (represented by '1') and water (represented by '0'). We want to count how many separate pieces of land there are.
We'll look at each spot on the map, one by one.
When we find a spot with land, we know we've discovered a new island. So, we'll increase our island count.
Now, the clever part: once we find a piece of land that's part of a new island, we need to make sure we don't count any of its connected land pieces again. So, we'll 'sink' this piece of land by changing it to water.
We then need to 'sink' all the other land pieces that are directly connected to this one, and any land pieces connected to those, and so on. Think of it like spreading out from the first land spot and turning all connected land into water.
We continue this process of finding land, counting it as a new island, and then sinking all its connected parts until we've checked every spot on the map.
By sinking the land as we find it, we guarantee that each separate island is counted only once, leading to the correct total.

Code Implementation

def number_of_islands(grid_map):
    if not grid_map:
        return 0

    rows_count = len(grid_map)
    columns_count = len(grid_map[0])
    number_of_islands_found = 0

    def sink_connected_land(row_index, column_index):
        # Base cases to stop recursion: out of bounds or already water
        if (row_index < 0 or row_index >= rows_count or
                column_index < 0 or column_index >= columns_count or
                grid_map[row_index][column_index] == '0'):
            return

        # Mark the current land piece as visited by changing it to water.
        grid_map[row_index][column_index] = '0'

        # Recursively explore adjacent land cells (up, down, left, right).
        sink_connected_land(row_index + 1, column_index)
        sink_connected_land(row_index - 1, column_index)
        sink_connected_land(row_index, column_index + 1)
        sink_connected_land(row_index, column_index - 1)

    # Iterate through each cell of the grid.
    for current_row_index in range(rows_count):
        for current_column_index in range(columns_count):
            # If we find a land cell ('1'), it signifies the start of a new island.
            if grid_map[current_row_index][current_column_index] == '1':
                number_of_islands_found += 1
                # Sink all connected land parts of this newly found island.
                sink_connected_land(current_row_index, current_column_index)

    return number_of_islands_found

Big(O) Analysis

Time Complexity

O(m * n) – Let m be the number of rows and n be the number of columns in the grid. The algorithm iterates through each cell of the grid once. When a land cell ('1') is found, a Depth First Search (DFS) or Breadth First Search (BFS) is initiated. This search visits each connected land cell exactly once, marking it as visited (or sinking it). In the worst case, every cell could be part of a single island or multiple islands. Since each cell is visited at most a constant number of times (once by the outer loop and at most once by a DFS/BFS traversal), the total time complexity is proportional to the total number of cells in the grid, which is m * n.

Space Complexity

O(M*N) – The primary contributor to auxiliary space complexity is the recursion stack when exploring connected land masses. In the worst-case scenario, where the entire grid is a single island, the recursion depth can be proportional to the total number of cells in the grid. If the grid has M rows and N columns, the recursion stack could grow up to O(M*N) in depth, representing the maximum number of function calls. Therefore, the auxiliary space complexity is dominated by this recursion stack and is O(M*N).

Edge Cases

Case	How to Handle
Empty grid or null grid input	The solution should return 0 islands if the grid is null or has zero rows/columns.
Grid with only water ('0's)	The algorithm will traverse the grid but find no '1's, correctly resulting in 0 islands.
Grid with only land ('1's)	The algorithm should identify and count this as a single large island.
A single row or single column grid	The logic should correctly identify islands that span the entire single dimension.
Grid with dimensions 1x1	A single '1' should be counted as one island, and a single '0' as zero islands.
Islands touching the boundary of the grid	The problem statement guarantees edges are surrounded by water, so this case is implicitly handled.
A very large grid potentially causing stack overflow with recursive DFS	An iterative DFS or BFS approach using a stack or queue respectively would mitigate this risk.
Grid contains characters other than '0' or '1'	The solution should ideally handle or gracefully reject such invalid inputs, or assume valid input as per problem constraints.

Empty grid or null grid input

How to Handle:

The solution should return 0 islands if the grid is null or has zero rows/columns.

Grid with only water ('0's)

How to Handle:

The algorithm will traverse the grid but find no '1's, correctly resulting in 0 islands.

Grid with only land ('1's)

How to Handle:

The algorithm should identify and count this as a single large island.

A single row or single column grid

How to Handle:

The logic should correctly identify islands that span the entire single dimension.

Grid with dimensions 1x1

How to Handle:

A single '1' should be counted as one island, and a single '0' as zero islands.

Islands touching the boundary of the grid

How to Handle:

The problem statement guarantees edges are surrounded by water, so this case is implicitly handled.

A very large grid potentially causing stack overflow with recursive DFS

How to Handle:

An iterative DFS or BFS approach using a stack or queue respectively would mitigate this risk.

Grid contains characters other than '0' or '1'

How to Handle:

The solution should ideally handle or gracefully reject such invalid inputs, or assume valid input as per problem constraints.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible dimensions of the grid, and are there any constraints on the number of rows or columns?
Can the grid be empty, meaning it has zero rows or zero columns?
Is it guaranteed that the grid will only contain '1's and '0's, or could other characters be present?
Are the '1's and '0's always represented as strings, or could they be integers?
If the grid is extremely large, are there any specific memory or time complexity requirements I should aim for beyond the standard optimal solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a map with land and water. We need to count how many separate land areas there are.
Let's pick a spot on the map.
If this spot is land, we've found a potential start of an island. We then need to explore all connected land pieces that belong to this same island.
As we explore the connected land, we should mark these pieces so we don't count them again as part of a new island.
Once we've explored all the land connected to our starting spot, we've fully identified one island.
Now, we move to the next spot on the map.
If this new spot is land and we haven't marked it already, it means we've found a new, distinct island. We repeat the exploration and marking process.
If the spot is water or already marked land, we simply move on to the next spot.
We continue this process for every single spot on the map, counting each time we discover a new, unmarked piece of land that leads to exploring a brand new island.
The total count of times we found a new island is our answer.

Code Implementation

def number_of_islands_brute_force(grid):    if not grid:
        return 0

    rows = len(grid)
    columns = len(grid[0])
    number_of_islands = 0

    def explore_island(current_row, current_column):
        # Ensure we are within bounds and on land ('1') that hasn't been visited
        if (current_row < 0 or current_row >= rows or
            current_column < 0 or current_column >= columns or
            grid[current_row][current_column] == '0'):
            return

        # Mark the current land piece as visited by changing it to '0'
        grid[current_row][current_column] = '0'

        # Explore all adjacent land pieces recursively
        explore_island(current_row + 1, current_column)
        explore_island(current_row - 1, current_column)
        explore_island(current_row, current_column + 1)
        explore_island(current_row, current_column - 1)

    # Iterate through each cell of the grid
    for row_index in range(rows):
        for column_index in range(columns):
            # If we find an unvisited piece of land, it signifies the start of a new island
            if grid[row_index][column_index] == '1':
                number_of_islands += 1
                explore_island(row_index, column_index)

    return number_of_islands

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a map with land (represented by '1') and water (represented by '0'). We want to count how many separate pieces of land there are.
We'll look at each spot on the map, one by one.
When we find a spot with land, we know we've discovered a new island. So, we'll increase our island count.
Now, the clever part: once we find a piece of land that's part of a new island, we need to make sure we don't count any of its connected land pieces again. So, we'll 'sink' this piece of land by changing it to water.
We then need to 'sink' all the other land pieces that are directly connected to this one, and any land pieces connected to those, and so on. Think of it like spreading out from the first land spot and turning all connected land into water.
We continue this process of finding land, counting it as a new island, and then sinking all its connected parts until we've checked every spot on the map.
By sinking the land as we find it, we guarantee that each separate island is counted only once, leading to the correct total.

Code Implementation

def number_of_islands(grid_map):
    if not grid_map:
        return 0

    rows_count = len(grid_map)
    columns_count = len(grid_map[0])
    number_of_islands_found = 0

    def sink_connected_land(row_index, column_index):
        # Base cases to stop recursion: out of bounds or already water
        if (row_index < 0 or row_index >= rows_count or
                column_index < 0 or column_index >= columns_count or
                grid_map[row_index][column_index] == '0'):
            return

        # Mark the current land piece as visited by changing it to water.
        grid_map[row_index][column_index] = '0'

        # Recursively explore adjacent land cells (up, down, left, right).
        sink_connected_land(row_index + 1, column_index)
        sink_connected_land(row_index - 1, column_index)
        sink_connected_land(row_index, column_index + 1)
        sink_connected_land(row_index, column_index - 1)

    # Iterate through each cell of the grid.
    for current_row_index in range(rows_count):
        for current_column_index in range(columns_count):
            # If we find a land cell ('1'), it signifies the start of a new island.
            if grid_map[current_row_index][current_column_index] == '1':
                number_of_islands_found += 1
                # Sink all connected land parts of this newly found island.
                sink_connected_land(current_row_index, current_column_index)

    return number_of_islands_found

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty grid or null grid input	The solution should return 0 islands if the grid is null or has zero rows/columns.
Grid with only water ('0's)	The algorithm will traverse the grid but find no '1's, correctly resulting in 0 islands.
Grid with only land ('1's)	The algorithm should identify and count this as a single large island.
A single row or single column grid	The logic should correctly identify islands that span the entire single dimension.
Grid with dimensions 1x1	A single '1' should be counted as one island, and a single '0' as zero islands.
Islands touching the boundary of the grid	The problem statement guarantees edges are surrounded by water, so this case is implicitly handled.
A very large grid potentially causing stack overflow with recursive DFS	An iterative DFS or BFS approach using a stack or queue respectively would mitigate this risk.
Grid contains characters other than '0' or '1'	The solution should ideally handle or gracefully reject such invalid inputs, or assume valid input as per problem constraints.

Empty grid or null grid input

How to Handle:

The solution should return 0 islands if the grid is null or has zero rows/columns.

Grid with only water ('0's)

How to Handle:

The algorithm will traverse the grid but find no '1's, correctly resulting in 0 islands.

Grid with only land ('1's)

How to Handle:

The algorithm should identify and count this as a single large island.

A single row or single column grid

How to Handle:

The logic should correctly identify islands that span the entire single dimension.

Grid with dimensions 1x1

How to Handle:

A single '1' should be counted as one island, and a single '0' as zero islands.

Islands touching the boundary of the grid

How to Handle:

The problem statement guarantees edges are surrounded by water, so this case is implicitly handled.

A very large grid potentially causing stack overflow with recursive DFS

How to Handle:

An iterative DFS or BFS approach using a stack or queue respectively would mitigate this risk.

Grid contains characters other than '0' or '1'

How to Handle:

The solution should ideally handle or gracefully reject such invalid inputs, or assume valid input as per problem constraints.

0/13 Waymo questions completed

0/13 completed