Is Making A Large Island easy or hard?

Making A Large Island is rated Hard on LeetCode because it combines matrix traversal, connected component labeling, and careful handling of duplicate neighboring islands. The optimal solution requires recognizing that island sizes must be precomputed.

How to solve Making A Large Island in O(n^2)?

Label every connected land component using DFS and assign it a unique id while recording its size in a map. For each 0 cell, gather the unique neighboring island ids and sum their sizes plus one for the flipped cell. This avoids recomputing island sizes and keeps the total work proportional to the grid size.

What is the best approach for Making A Large Island?

DFS with island labeling is the most common optimal solution. First label each island with a unique id and store its size using DFS in O(n^2). Then evaluate every 0 cell and combine the sizes of adjacent distinct islands to compute the largest possible island after one flip.

What data structure is used in Making A Large Island?

The most common solution uses DFS with a hash map to store island sizes and a set to avoid counting duplicate neighboring islands. Some implementations also use the Union Find (Disjoint Set) data structure to track connected components.

What is the time complexity of Making A Large Island?

The optimal solution runs in O(n^2) time for an n x n grid. One DFS pass labels every island and computes sizes, and a second pass evaluates each water cell by checking its four neighbors.

Making A Large Island Python or Java solution approach?

Python and Java implementations typically run a DFS to label islands and store their sizes in a dictionary or map. Then each 0 cell checks its four neighbors, combines distinct island sizes, and updates the maximum possible island area.

Is Making A Large Island asked at Google, Amazon, or Meta?

Making A Large Island is a classic grid connectivity problem and appears in interviews at companies that test graph and matrix traversal skills, including Google, Amazon, and Meta-style interview loops. It evaluates DFS/BFS reasoning and component merging logic.

Description Solution Video 26:16

827. Making A Large Island

Hard57.0% acceptance16 companies

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.

Asked at 16 companies

Snapchat Moloco UiPath Meta Tiktok Anduril Uber Snowflake DoorDash Medianet LinkedIn

Google

+4 more

Amazon Microsoft Airbnb Bloomberg

Topics

26:16

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def largestIsland(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,0],[0,1]]

Input

[[1,1],[1,0]]

Input

[[1,1],[1,1]]

Your code is saved on this device.Solution