Coding - Making a Large Island

Problem Statement

You are given an n x n binary matrix grid. You may change at most one 0 to 1. Return the size of the largest island after applying this operation. An island is a 4-directionally connected group of 1s.

Examples

Example 1: Input: grid = [[1,0],[0,1]] Output: 3 Explanation: Change the first row, first column 0 to 1, then merge two 1s groups to form a 3-island.

Example 2: Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the second row, second column 0 to 1, then you get a 4-island.

Example 3: Input: grid = [[1,1],[1,1]] Output: 4 Explanation: Can't change any 0 to 1, so the largest island remains 4.

Constraints

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

Hints

1. DFS: Use depth-first search to find the size of each island.
2. Union-Find: Use a union-find data structure to merge islands when changing a 0 to 1.
3. Max Size: Keep track of the maximum island size found during the search.