Jobs

Interviews

Discussions

Making A Large Island

Hard

Snap

2 views

Topics:

ArraysDepth-First Search

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.

Making A Large Island

Hard

Snap

2 views

Topics:

ArraysDepth-First Search

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 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?
What values can the grid cells contain; are they restricted to 0 and 1, or could there be other values?
If the grid is already all 1s, what value should I return: the original area or the result of 'flipping' a 0?
If there are multiple '0' cells that would result in the same maximum island size when flipped to '1', does it matter which one I consider?
Is the input grid guaranteed to be rectangular?

Brute Force Solution

Approach

The problem asks to find the largest island you can make by changing one zero to a one in a grid of zeros and ones. The brute force approach tries flipping every single zero to a one, and then calculates the size of the island that results from each flip.

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

Go through each spot in the grid, one by one.
If you find a spot with a zero, temporarily change it to a one.
Now, calculate the size of the island that this 'one' belongs to. This involves finding all the connected ones around it.
Remember this island size.
Change the 'one' back to a zero, so you can try the next spot.
Once you've gone through every zero in the grid, look at all the island sizes you calculated.
The biggest island size you found is your answer.

Code Implementation

def making_a_large_island_brute_force(grid):
    max_island_size = 0
    grid_row_length = len(grid)
    grid_column_length = len(grid[0])

    def calculate_island_size(row, column, current_grid, visited):
        if row < 0 or row >= grid_row_length or column < 0 or column >= grid_column_length or \
           (row, column) in visited or current_grid[row][column] == 0:
            return 0

        visited.add((row, column))
        size = 1

        size += calculate_island_size(row + 1, column, current_grid, visited)
        size += calculate_island_size(row - 1, column, current_grid, visited)
        size += calculate_island_size(row, column + 1, current_grid, visited)
        size += calculate_island_size(row, column - 1, current_grid, visited)

        return size

    for row_index in range(grid_row_length):
        for column_index in range(grid_column_length):
            if grid[row_index][column_index] == 0:
                # Temporarily flip the zero to a one
                grid[row_index][column_index] = 1

                # Calculate the island size after the flip
                island_size = calculate_island_size(row_index, column_index, grid, set())
                
                # Update the max size if needed
                max_island_size = max(max_island_size, island_size)

                # Flip it back
                grid[row_index][column_index] = 0

    # If the grid only contained zeroes, return 1
    if max_island_size == 0:
        all_ones = True
        for row_index in range(grid_row_length):
            for column_index in range(grid_column_length):
                if grid[row_index][column_index] == 0:
                    all_ones = False
                    break
            if not all_ones:
                break
        if all_ones and grid_row_length > 0:
            return grid_row_length * grid_column_length
        else:
            return 1

    # Check if all cells are already 1s
    all_ones = True
    for row_index in range(grid_row_length):
        for column_index in range(grid_column_length):
            if grid[row_index][column_index] == 0:
                all_ones = False
                break
        if not all_ones:
            break

    if all_ones:
        # Grid is all ones, return its area
        return grid_row_length * grid_column_length

    return max_island_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^4) – The algorithm iterates through each cell in the n x n grid (outer loop), which takes O(n^2) time. For each zero found, it temporarily flips it to one and then calculates the island size using what would typically be a depth-first search (DFS) or breadth-first search (BFS). DFS/BFS in the worst case, can visit every cell in the grid, resulting in O(n^2) time. Therefore, the overall time complexity is O(n^2) * O(n^2) = O(n^4) where the outer n^2 comes from iterating through the grid, and the inner n^2 comes from the DFS or BFS used to compute the island size.

Space Complexity

O(N) – The brute force approach, as described, involves calculating the size of an island potentially for every zero in the grid. Calculating the island size typically uses Depth First Search (DFS) or Breadth First Search (BFS). These algorithms require marking visited cells to avoid infinite loops. This marking is typically done with an auxiliary data structure such as a boolean matrix of the same size as the input grid, where N is the total number of cells in the grid. The space used by the recursion stack in DFS could also reach a depth of N in the worst case. Thus the overall space complexity is O(N).

Optimal Solution

Approach

The goal is to find the largest connected area of land ('1's) you can create by changing a single patch of water ('0') to land. The optimal approach avoids re-calculating the size of connected land areas by pre-calculating and storing these sizes, then efficiently checking the neighbors of each water patch.

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

First, go through the entire map and identify each separate piece of land (connected '1's).
As you find each land area, calculate its size (number of '1's) and give it a unique label. Keep track of which label corresponds to which size.
Now, go through the map again, looking for water patches ('0's).
For each water patch, check its four neighbors (up, down, left, right).
If a neighbor is land, get its unique label and look up the size of that land area from your previously stored sizes. Remember to only count each land area once, even if multiple neighbors are part of the same area.
Add up the sizes of all the neighboring land areas, plus 1 (for the water patch you're turning into land).
Keep track of the largest total size you find when considering all water patches.
If there were no water patches, the initial largest land was the whole map. If we did find water patches, return the largest calculated size. This is the biggest island you can make.

Code Implementation

def making_a_large_island(grid):
    rows = len(grid)
    cols = len(grid[0])
    land_size_by_label = {}
    label = 2

    def get_land_size(row, col, current_label):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
            return 0
        grid[row][col] = current_label
        return 1 + get_land_size(row + 1, col, current_label) + \
               get_land_size(row - 1, col, current_label) + \
               get_land_size(row, col + 1, current_label) + \
               get_land_size(row, col - 1, current_label)

    # Assign a unique label to each land area and record its size
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                land_size = get_land_size(row, col, label)
                land_size_by_label[label] = land_size
                label += 1

    largest_island_size = 0

    # Iterate through water patches and check the neighboring land areas
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 0:
                neighboring_labels = set()
                size = 1  # Start with 1 for the water patch itself

                # Check the 4 neighbors (up, down, left, right)
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != 0:
                        neighbor_label = grid[new_row][new_col]
                        # Only add the land size if the label hasn't been seen yet
                        if neighbor_label not in neighboring_labels:
                            size += land_size_by_label[neighbor_label]
                            neighboring_labels.add(neighbor_label)
                largest_island_size = max(largest_island_size, size)

    # If no '0' was found, the whole grid was a single island
    if largest_island_size == 0:
        return rows * cols

    return largest_island_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through the entire grid twice, where n represents the number of cells in the grid (rows * cols). The first iteration labels and sizes the land masses. The second iteration examines each water cell and its neighbors, looking up the size of each neighboring landmass. Since neighbor lookup is constant time, the dominant factor is iterating through all cells, which scales linearly with n twice. Therefore, the total time complexity is O(n^2).

Space Complexity

O(N) – The algorithm uses auxiliary space to store the size of each connected land area using a label, where the label represents a unique land area. In the worst-case scenario, the entire grid is land, but disconnected, requiring storage for each cell's size. This means we could have up to N distinct land areas (where N is the total number of cells in the grid) and we store these sizes. Additionally, the labeling process requires a modified copy of the input grid, also of size N. Thus the total auxiliary space is proportional to N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0, as no island exists in an empty grid.
Grid with all 0s (no islands)	Return 0, because no island exists to potentially expand.
Grid with all 1s (one large island)	Return rows * cols, as flipping a 0 won't increase island size.
Grid with only one row or one column	The algorithm should still correctly identify and calculate the connected components and handle the boundary conditions for flipping a '0' to a '1'.
Grid dimensions are at maximum constraints	Ensure the solution uses appropriate data structures and algorithms (e.g., DFS/BFS with efficient memory management) to avoid exceeding memory limits.
Integer overflow when calculating island size	Use a data type that can accommodate large island sizes (e.g., long) for calculating the island size.
Multiple possible '0' flips resulting in the same maximum island size.	The solution should return the maximum possible size, regardless of how many locations result in that maximum.
Disjoint islands separated by multiple 0s	The algorithm must correctly consider neighboring islands separated by multiple 0s and identify the largest combined size after flipping one 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 size I should expect?
What values can the grid cells contain; are they restricted to 0 and 1, or could there be other values?
If the grid is already all 1s, what value should I return: the original area or the result of 'flipping' a 0?
If there are multiple '0' cells that would result in the same maximum island size when flipped to '1', does it matter which one I consider?
Is the input grid guaranteed to be rectangular?

Brute Force Solution

Approach

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

Go through each spot in the grid, one by one.
If you find a spot with a zero, temporarily change it to a one.
Now, calculate the size of the island that this 'one' belongs to. This involves finding all the connected ones around it.
Remember this island size.
Change the 'one' back to a zero, so you can try the next spot.
Once you've gone through every zero in the grid, look at all the island sizes you calculated.
The biggest island size you found is your answer.

Code Implementation

def making_a_large_island_brute_force(grid):
    max_island_size = 0
    grid_row_length = len(grid)
    grid_column_length = len(grid[0])

    def calculate_island_size(row, column, current_grid, visited):
        if row < 0 or row >= grid_row_length or column < 0 or column >= grid_column_length or \
           (row, column) in visited or current_grid[row][column] == 0:
            return 0

        visited.add((row, column))
        size = 1

        size += calculate_island_size(row + 1, column, current_grid, visited)
        size += calculate_island_size(row - 1, column, current_grid, visited)
        size += calculate_island_size(row, column + 1, current_grid, visited)
        size += calculate_island_size(row, column - 1, current_grid, visited)

        return size

    for row_index in range(grid_row_length):
        for column_index in range(grid_column_length):
            if grid[row_index][column_index] == 0:
                # Temporarily flip the zero to a one
                grid[row_index][column_index] = 1

                # Calculate the island size after the flip
                island_size = calculate_island_size(row_index, column_index, grid, set())
                
                # Update the max size if needed
                max_island_size = max(max_island_size, island_size)

                # Flip it back
                grid[row_index][column_index] = 0

    # If the grid only contained zeroes, return 1
    if max_island_size == 0:
        all_ones = True
        for row_index in range(grid_row_length):
            for column_index in range(grid_column_length):
                if grid[row_index][column_index] == 0:
                    all_ones = False
                    break
            if not all_ones:
                break
        if all_ones and grid_row_length > 0:
            return grid_row_length * grid_column_length
        else:
            return 1

    # Check if all cells are already 1s
    all_ones = True
    for row_index in range(grid_row_length):
        for column_index in range(grid_column_length):
            if grid[row_index][column_index] == 0:
                all_ones = False
                break
        if not all_ones:
            break

    if all_ones:
        # Grid is all ones, return its area
        return grid_row_length * grid_column_length

    return max_island_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, go through the entire map and identify each separate piece of land (connected '1's).
As you find each land area, calculate its size (number of '1's) and give it a unique label. Keep track of which label corresponds to which size.
Now, go through the map again, looking for water patches ('0's).
For each water patch, check its four neighbors (up, down, left, right).
If a neighbor is land, get its unique label and look up the size of that land area from your previously stored sizes. Remember to only count each land area once, even if multiple neighbors are part of the same area.
Add up the sizes of all the neighboring land areas, plus 1 (for the water patch you're turning into land).
Keep track of the largest total size you find when considering all water patches.
If there were no water patches, the initial largest land was the whole map. If we did find water patches, return the largest calculated size. This is the biggest island you can make.

Code Implementation

def making_a_large_island(grid):
    rows = len(grid)
    cols = len(grid[0])
    land_size_by_label = {}
    label = 2

    def get_land_size(row, col, current_label):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
            return 0
        grid[row][col] = current_label
        return 1 + get_land_size(row + 1, col, current_label) + \
               get_land_size(row - 1, col, current_label) + \
               get_land_size(row, col + 1, current_label) + \
               get_land_size(row, col - 1, current_label)

    # Assign a unique label to each land area and record its size
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                land_size = get_land_size(row, col, label)
                land_size_by_label[label] = land_size
                label += 1

    largest_island_size = 0

    # Iterate through water patches and check the neighboring land areas
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 0:
                neighboring_labels = set()
                size = 1  # Start with 1 for the water patch itself

                # Check the 4 neighbors (up, down, left, right)
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != 0:
                        neighbor_label = grid[new_row][new_col]
                        # Only add the land size if the label hasn't been seen yet
                        if neighbor_label not in neighboring_labels:
                            size += land_size_by_label[neighbor_label]
                            neighboring_labels.add(neighbor_label)
                largest_island_size = max(largest_island_size, size)

    # If no '0' was found, the whole grid was a single island
    if largest_island_size == 0:
        return rows * cols

    return largest_island_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0, as no island exists in an empty grid.
Grid with all 0s (no islands)	Return 0, because no island exists to potentially expand.
Grid with all 1s (one large island)	Return rows * cols, as flipping a 0 won't increase island size.
Grid with only one row or one column	The algorithm should still correctly identify and calculate the connected components and handle the boundary conditions for flipping a '0' to a '1'.
Grid dimensions are at maximum constraints	Ensure the solution uses appropriate data structures and algorithms (e.g., DFS/BFS with efficient memory management) to avoid exceeding memory limits.
Integer overflow when calculating island size	Use a data type that can accommodate large island sizes (e.g., long) for calculating the island size.
Multiple possible '0' flips resulting in the same maximum island size.	The solution should return the maximum possible size, regardless of how many locations result in that maximum.
Disjoint islands separated by multiple 0s	The algorithm must correctly consider neighboring islands separated by multiple 0s and identify the largest combined size after flipping one 0.