Practice/Meta/Leetcode 827. Making A Large Island

Leetcode 827. Making A Large Island

CodingMust

Problem

You are given an n × n binary grid where each cell is either 0 (water) or 1 (land). An island is a group of land cells connected in 4 directions (up, down, left, right).

You can convert at most one water cell (0) into a land cell (1). Your task is to find the maximum possible size of an island after performing this operation.

Requirements

1. Return the size (number of cells) of the largest possible island
2. You may flip at most one 0 to 1
3. Islands are defined by 4-directional connectivity (not diagonal)
4. If the grid is already all land, return the total number of cells

Constraints

• n == grid.length == grid[i].length
• 1 ≤ n ≤ 500
• grid[i][j] is either 0 or 1
• Expected time complexity: O(n²)
• Expected space complexity: O(n²)

Examples

Example 1:

Input: grid = [[1, 0], [0, 1]] Output: 3 Explanation: Flipping either 0 to 1 connects both islands, creating an island of size 3.

Example 2:

Input: grid = [[1, 1], [1, 1]] Output: 4 Explanation: The grid is already all land, so the entire grid forms one island of size 4.

Example 3:

Input: grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]] Output: 5 Explanation: Flipping the center cell connects all four corner islands plus the flipped cell for a total of 5.