Jobs

Interviews

Discussions

Number of Islands

Medium

1 view

Topics:

ArraysGraphs

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

Number of Islands

Medium

1 view

Topics:

ArraysGraphs

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

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 dimensions of the grid, and what is the maximum possible size of the grid (e.g., maximum number of rows and columns)?
Can the grid be empty (0 rows or 0 columns)? What should I return in that case?
Besides '1' and '0', can the grid contain any other characters?
Is the input grid guaranteed to be rectangular (i.e., all rows have the same number of columns)?
Should I modify the input grid in place, or is it acceptable to create a copy?

Brute Force Solution

Approach

Imagine you have a map of land and water, and you want to find out how many separate islands there are. The brute force approach is like going over every single piece of land on the map to see if it's part of an island that you haven't already counted.

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

Start at the very first spot on the map.
If that spot is land, explore every direction around that spot to see how far the island stretches.
As you explore, mark all the connected land pieces as visited, so you don't count them again.
Once you've explored the entire island connected to that first spot, you've found one island! Increase your island count.
Now, move on to the next spot on the map that hasn't been visited yet.
Repeat the exploring and marking process until you've checked every single spot on the entire map.
The final island count represents the total number of distinct islands on the map.

Code Implementation

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

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    number_of_islands = 0
    visited = set()

    def explore_island(row, column):
        if (row < 0 or row >= number_of_rows or \
            column < 0 or column >= number_of_columns or \
            grid[row][column] == '0' or (row, column) in visited):
            return

        visited.add((row, column))

        # Explore all 4 directions
        explore_island(row + 1, column)
        explore_island(row - 1, column)
        explore_island(row, column + 1)
        explore_island(row, column - 1)

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            # Start exploration if land is found
            if grid[row][column] == '1' and (row, column) not in visited:

                explore_island(row, column)

                # Count a new island
                number_of_islands += 1

    return number_of_islands

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(M * N) – The algorithm iterates through each cell of the grid, which has dimensions M rows and N columns. For each land cell encountered, a depth-first search (DFS) or breadth-first search (BFS) is performed to explore the entire island connected to that cell. In the worst-case scenario, the entire grid is filled with land, and the DFS/BFS will visit each cell once. Therefore, the time complexity is proportional to the total number of cells in the grid, which is M * N.

Space Complexity

O(M*N) – The space complexity is determined by the space used for the visited markings during island exploration. In the worst-case scenario, the entire grid could be land, and the algorithm might need to visit all M*N cells, storing their visited status implicitly within the call stack or explicitly using an auxiliary data structure of size M*N. If a recursive depth-first search (DFS) is used, the call stack could grow up to M*N in size. Therefore, the space complexity is O(M*N), where M is the number of rows and N is the number of columns in the grid.

Optimal Solution

Approach

The problem asks us to count separate landmasses on a map. The key idea is to treat the map like a graph and explore connected pieces of land, marking them as visited to avoid recounting them.

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

Imagine you're walking across the map, square by square.
If you find a piece of land (marked as '1'), you've found a new island.
Now, explore all the connected pieces of land around that starting piece, like exploring all the rooms in a house.
As you explore, change all the connected land pieces to water (or some other marker) so you don't count them again as a separate island. This is crucial to efficiency!
Repeat the process, moving square by square until you've checked the whole map.
Each time you found a new piece of land before exploring it, increment your island count.
The final count is the total number of separate islands.

Code Implementation

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

    rows = len(grid)
    cols = len(grid[0])
    island_count = 0

    def explore_island(row, col):
        # Check boundaries and if the cell is land
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        # Mark the current cell as visited by turning it into water
        grid[row][col] = '0'

        # Recursively explore adjacent land cells
        explore_island(row + 1, col)

        explore_island(row - 1, col)

        explore_island(row, col + 1)

        explore_island(row, col - 1)

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1':
                # Found a new island
                island_count += 1

                # Explore and mark the entire island
                explore_island(row, col)

    return island_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(M * N) – The algorithm iterates through each cell of the M x N grid to find islands. When land ('1') is found, a depth-first search (DFS) or breadth-first search (BFS) is initiated to explore and mark the connected land as visited (changing it to '0'). In the worst case, the entire grid is land, and the DFS/BFS will visit every cell once. Therefore, the time complexity is proportional to the total number of cells in the grid, which is M * N. This yields a time complexity of O(M * N).

Space Complexity

O(min(M, N)) – The dominant space usage stems from the recursive calls made during the island exploration (step 3). In the worst-case scenario, where the entire map is land ('1's), the recursive calls could potentially explore the map's height (M) or width (N) depending on the implementation. This results in a recursion depth proportional to min(M,N) when doing either breadth-first search (BFS) or depth-first search (DFS). Therefore, the space complexity for the call stack is O(min(M,N)) in the worst case, where M and N are the dimensions of the grid. Any other variables have constant space usage.

Edge Cases

Case	How to Handle
Null or empty grid input	Return 0 if the grid is null or has zero rows/columns, indicating no islands exist.
Grid with only one cell	Check if the single cell is '1'; if so, return 1, otherwise return 0.
Grid with all '0's (all water)	Return 0, as there are no islands.
Grid with all '1's (one large island)	Return 1, as all land is connected.
Grid with non-rectangular dimensions	Ensure the algorithm correctly handles rows of varying lengths or throws an error if non-rectangularity is not allowed.
Integer overflow during recursion if the island is very large	Use iterative DFS or BFS to avoid potential stack overflow issues with very large islands and manage memory explicitly.
Very large grid (performance considerations)	Employ an efficient algorithm like iterative Depth-First Search (DFS) or Breadth-First Search (BFS) with in-place modification (marking visited cells) to optimize space complexity.
Grid contains characters other than '0' and '1'	Validate that only '0' and '1' characters are present, and either throw an error or treat other characters as water '0'.

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 dimensions of the grid, and what is the maximum possible size of the grid (e.g., maximum number of rows and columns)?
Can the grid be empty (0 rows or 0 columns)? What should I return in that case?
Besides '1' and '0', can the grid contain any other characters?
Is the input grid guaranteed to be rectangular (i.e., all rows have the same number of columns)?
Should I modify the input grid in place, or is it acceptable to create a copy?

Brute Force Solution

Approach

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

Start at the very first spot on the map.
If that spot is land, explore every direction around that spot to see how far the island stretches.
As you explore, mark all the connected land pieces as visited, so you don't count them again.
Once you've explored the entire island connected to that first spot, you've found one island! Increase your island count.
Now, move on to the next spot on the map that hasn't been visited yet.
Repeat the exploring and marking process until you've checked every single spot on the entire map.
The final island count represents the total number of distinct islands on the map.

Code Implementation

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

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    number_of_islands = 0
    visited = set()

    def explore_island(row, column):
        if (row < 0 or row >= number_of_rows or \
            column < 0 or column >= number_of_columns or \
            grid[row][column] == '0' or (row, column) in visited):
            return

        visited.add((row, column))

        # Explore all 4 directions
        explore_island(row + 1, column)
        explore_island(row - 1, column)
        explore_island(row, column + 1)
        explore_island(row, column - 1)

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            # Start exploration if land is found
            if grid[row][column] == '1' and (row, column) not in visited:

                explore_island(row, column)

                # Count a new island
                number_of_islands += 1

    return number_of_islands

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The problem asks us to count separate landmasses on a map. The key idea is to treat the map like a graph and explore connected pieces of land, marking them as visited to avoid recounting them.

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

Imagine you're walking across the map, square by square.
If you find a piece of land (marked as '1'), you've found a new island.
Now, explore all the connected pieces of land around that starting piece, like exploring all the rooms in a house.
As you explore, change all the connected land pieces to water (or some other marker) so you don't count them again as a separate island. This is crucial to efficiency!
Repeat the process, moving square by square until you've checked the whole map.
Each time you found a new piece of land before exploring it, increment your island count.
The final count is the total number of separate islands.

Code Implementation

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

    rows = len(grid)
    cols = len(grid[0])
    island_count = 0

    def explore_island(row, col):
        # Check boundaries and if the cell is land
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        # Mark the current cell as visited by turning it into water
        grid[row][col] = '0'

        # Recursively explore adjacent land cells
        explore_island(row + 1, col)

        explore_island(row - 1, col)

        explore_island(row, col + 1)

        explore_island(row, col - 1)

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1':
                # Found a new island
                island_count += 1

                # Explore and mark the entire island
                explore_island(row, col)

    return island_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid input	Return 0 if the grid is null or has zero rows/columns, indicating no islands exist.
Grid with only one cell	Check if the single cell is '1'; if so, return 1, otherwise return 0.
Grid with all '0's (all water)	Return 0, as there are no islands.
Grid with all '1's (one large island)	Return 1, as all land is connected.
Grid with non-rectangular dimensions	Ensure the algorithm correctly handles rows of varying lengths or throws an error if non-rectangularity is not allowed.
Integer overflow during recursion if the island is very large	Use iterative DFS or BFS to avoid potential stack overflow issues with very large islands and manage memory explicitly.
Very large grid (performance considerations)	Employ an efficient algorithm like iterative Depth-First Search (DFS) or Breadth-First Search (BFS) with in-place modification (marking visited cells) to optimize space complexity.
Grid contains characters other than '0' and '1'	Validate that only '0' and '1' characters are present, and either throw an error or treat other characters as water '0'.