HardCoding

Making a large island

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an n x n binary matrix grid, it is allowed to change at most one 0 to 1. A group of connected 1s forms an island, where two 1s are connected if they share one of their sides.

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

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

Input: grid = [[1,1],[1,1]] **Output: **4 Explanation: The largest island already exists with size 4.

Input: grid = [[1,1],[1,0]]

1 <= n <= 500
0 <= grid[i][j] <= 1

cpp

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        
    }
};

java

class Solution {
    public int largestIsland(int[][] grid) {
      
    }
}

python

class Solution:
    def largestIsland(self, grid):

javascript

class Solution {
   largestIsland(grid) {
       
    }
}

csharp

public class Solution
{
    public int LargestIsland(int[][] grid)
    {
      
    }
}

func largestIsland(grid [][]int) int {
	
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Restate the objective and identify the key invariant
02Develop the component labeling and one flip approach step by step
03Walk through a small adversarial example
04Cover boundary conditions before coding
05State time and space Big-O and explain the trade-off

Reference answer

Approach

For Making a large island, begin by restating the condition that must remain true throughout the algorithm. Use component labeling and one flip; do not jump straight to code. Derive why the local state is sufficient, then walk through a small example and identify exactly when the answer is updated. Make the implementation’s ordering explicit, because most bugs here come from updating state before querying it, using an inclusive bound where a strict one is needed, or losing original indices.

Correctness and edge cases

Explain the invariant in one sentence and show why initialization, each transition, and termination preserve it. Test the empty or smallest allowed input, one-element structures, duplicates or ties, extreme values, and cases where the natural answer is absent. Use a wide numeric type when accumulated values can overflow. The intended approach runs in the standard complexity for component labeling and one flip: state the dominant scan, sort, traversal, or lookup honestly. For this formulation, target O(n log n) when sorting or balanced lookups are needed, otherwise O(n) time; auxiliary space is O(n) unless the input structure itself supplies the storage.

Then expect these follow-ups

How would the approach change for streaming input?
Tests: constraint adaptation
Which boundary case is most likely to break an implementation?
Tests: implementation extension

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question