Jobs

Interviews

Discussions

Number of Islands

Medium

PayPal

0 views

Topics:

GraphsArraysRecursion

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

PayPal

0 views

Topics:

GraphsArraysRecursion

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 size I should expect?
Can the grid be empty or null?
Besides '1' and '0', are there any other possible characters in the grid?
Is it possible for an island to be disconnected, such as a '1' surrounded by '0's, with another '1' adjacent to those '0's, but not directly adjacent to the original '1'?
Could the grid be rectangular (different number of rows and columns), or is it always guaranteed to be square?

Brute Force Solution

Approach

We can think of the problem as finding connected groups of land on a map. The brute force method simply looks at every single piece of the map and, if it's land, tries to identify the entire island it belongs to.

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

Go through each square of the map one by one, starting from the top left.
If a square is land, mark it as part of an island and then explore all the surrounding squares.
For each surrounding square that is also land, mark it as part of the same island and then explore *its* surrounding squares.
Keep going until you've marked all the connected land squares as part of the same island. This means you've found one entire island.
Continue going through the remaining squares on the map. If you find more unmarked land, repeat the process to find another island.
When you've checked every square on the map, count how many separate islands you've found. That's your answer.

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

    def explore_island(row, column):
        # Check boundaries and if it's land
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           grid[row][column] == '0':
            return

        # Mark the current land as visited
        grid[row][column] = '0'


        # Recursively explore all adjacent land
        explore_island(row + 1, column)

        explore_island(row - 1, column)

        explore_island(row, column + 1)

        explore_island(row, column - 1)

    # Iterate through each cell in the grid
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            # If we find land, start exploring the island
            if grid[row][column] == '1':

                # Increment island count
                number_of_islands += 1

                # Explore the entire island
                explore_island(row, column)

    return number_of_islands

Big(O) Analysis

Time Complexity

O(M * N) – The algorithm iterates through each cell of the M x N grid once. For each land cell encountered, a Depth-First Search (DFS) or Breadth-First Search (BFS) is performed to explore the entire island. In the worst case, the entire grid is filled with land ('1's), and the DFS/BFS will visit each cell once. Therefore, the time complexity is proportional to the number of cells in the grid, which is M * N. Hence, the time complexity is O(M * N).

Space Complexity

O(M * N) – The dominant space complexity arises from the potential use of a recursive call stack or a queue data structure, both of which are employed during the exploration of each island using Depth-First Search (DFS) or Breadth-First Search (BFS). In the worst-case scenario, the entire grid is filled with land ('1'), meaning a single island covers the whole map. Therefore, the recursion depth or the queue's size could grow up to the total number of cells in the grid, which is represented by M * N, where M is the number of rows and N is the number of columns in the grid. While the algorithm modifies the input grid in place, marking visited cells, this modification does not contribute to auxiliary space complexity.

Optimal Solution

Approach

We need to find the number of separate landmasses in a map represented by ones and zeros. The key is to explore each landmass only once and mark it as visited, so we don't count it again. We can achieve this using a technique that spreads out from a starting point to find all connected land.

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

Go through the map, one spot at a time, looking for land (represented by the number one).
If you find a piece of land, increase the island count by one, because this is a new island.
Once you've counted the island, explore all the connected land around it to mark it as visited.
To explore, check the spots to the left, right, above, and below the current land spot.
If the neighboring spot is also land, mark it as visited and continue exploring its neighbors in the same way. This makes sure you get the entire island.
Keep doing this until you've explored all the land connected to the initial land spot.
Continue scanning the map and repeat the process whenever you find another unvisited piece of land. This way, each island is counted only once.

Code Implementation

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

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    island_count = 0

    def explore_island(row, column):
        # Check boundaries and if the cell is land.
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           grid[row][column] == '0':
            return

        # Mark the current cell as visited.
        grid[row] = grid[row][:column] + '0' + grid[row][column+1:]

        # Recursively explore adjacent land.
        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 island count when land is found
            if grid[row][column] == '1':
                island_count += 1

                # Explore the entire island and mark it visited.
                explore_island(row, column)

    return island_count

Big(O) Analysis

Time Complexity

O(M * N) – The algorithm iterates through each cell of the M x N grid. When a '1' (land) is encountered, a depth-first search (DFS) or breadth-first search (BFS) is initiated to explore the connected component. In the worst-case scenario, the entire grid is filled with '1's, meaning every cell is visited during the DFS/BFS. Therefore, the time complexity is proportional to the number of cells in the grid, which is M * N. Thus, the time complexity simplifies to O(M * N).

Space Complexity

O(M * N) – The space complexity is determined by the auxiliary space used during the exploration of the grid. In the worst-case scenario, where the entire grid is filled with land ('1'), the recursive calls or the queue used in a breadth-first search (BFS) could potentially visit all cells. This means the recursion stack or the queue could grow proportionally to the total number of cells in the grid, which is M * N, where M is the number of rows and N is the number of columns. Therefore, the auxiliary space complexity is O(M * N).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or has zero rows or columns, as there can be no islands.
Grid with all water ('0')	The algorithm should correctly identify that there are zero islands and return 0.
Grid with all land ('1')	The algorithm should correctly identify that there is one island and return 1.
Grid with a single '1' surrounded by '0's	The algorithm should correctly identify this as one island.
Large grid with many islands	The algorithm's time and space complexity should be considered to ensure it scales efficiently without exceeding memory limits.
Grid where islands are connected diagonally	The problem specifies horizontal and vertical connections only, so the algorithm must not consider diagonal connections.
Grid with islands touching the grid boundaries	The algorithm should not treat boundaries differently; islands touching edges are still valid islands.
Integer overflow when calculating grid dimensions	Use appropriate data types (e.g., long) if the grid dimensions could potentially lead to integer overflow.

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 size I should expect?
Can the grid be empty or null?
Besides '1' and '0', are there any other possible characters in the grid?
Is it possible for an island to be disconnected, such as a '1' surrounded by '0's, with another '1' adjacent to those '0's, but not directly adjacent to the original '1'?
Could the grid be rectangular (different number of rows and columns), or is it always guaranteed to be square?

Brute Force Solution

Approach

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

Go through each square of the map one by one, starting from the top left.
If a square is land, mark it as part of an island and then explore all the surrounding squares.
For each surrounding square that is also land, mark it as part of the same island and then explore *its* surrounding squares.
Keep going until you've marked all the connected land squares as part of the same island. This means you've found one entire island.
Continue going through the remaining squares on the map. If you find more unmarked land, repeat the process to find another island.
When you've checked every square on the map, count how many separate islands you've found. That's your answer.

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

    def explore_island(row, column):
        # Check boundaries and if it's land
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           grid[row][column] == '0':
            return

        # Mark the current land as visited
        grid[row][column] = '0'


        # Recursively explore all adjacent land
        explore_island(row + 1, column)

        explore_island(row - 1, column)

        explore_island(row, column + 1)

        explore_island(row, column - 1)

    # Iterate through each cell in the grid
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            # If we find land, start exploring the island
            if grid[row][column] == '1':

                # Increment island count
                number_of_islands += 1

                # Explore the entire island
                explore_island(row, column)

    return number_of_islands

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the map, one spot at a time, looking for land (represented by the number one).
If you find a piece of land, increase the island count by one, because this is a new island.
Once you've counted the island, explore all the connected land around it to mark it as visited.
To explore, check the spots to the left, right, above, and below the current land spot.
If the neighboring spot is also land, mark it as visited and continue exploring its neighbors in the same way. This makes sure you get the entire island.
Keep doing this until you've explored all the land connected to the initial land spot.
Continue scanning the map and repeat the process whenever you find another unvisited piece of land. This way, each island is counted only once.

Code Implementation

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

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    island_count = 0

    def explore_island(row, column):
        # Check boundaries and if the cell is land.
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           grid[row][column] == '0':
            return

        # Mark the current cell as visited.
        grid[row] = grid[row][:column] + '0' + grid[row][column+1:]

        # Recursively explore adjacent land.
        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 island count when land is found
            if grid[row][column] == '1':
                island_count += 1

                # Explore the entire island and mark it visited.
                explore_island(row, column)

    return island_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or has zero rows or columns, as there can be no islands.
Grid with all water ('0')	The algorithm should correctly identify that there are zero islands and return 0.
Grid with all land ('1')	The algorithm should correctly identify that there is one island and return 1.
Grid with a single '1' surrounded by '0's	The algorithm should correctly identify this as one island.
Large grid with many islands	The algorithm's time and space complexity should be considered to ensure it scales efficiently without exceeding memory limits.
Grid where islands are connected diagonally	The problem specifies horizontal and vertical connections only, so the algorithm must not consider diagonal connections.
Grid with islands touching the grid boundaries	The algorithm should not treat boundaries differently; islands touching edges are still valid islands.
Integer overflow when calculating grid dimensions	Use appropriate data types (e.g., long) if the grid dimensions could potentially lead to integer overflow.