Here is the Markdown blog post for the problem:

Making A Large Island

Slug: making-a-large-island Difficulty: Hard Id: 716818 Topic Tags: Matrix, DFS, BFS, union-find Company Tags: Intuit

Summary

In this problem, we are given a matrix where each cell can be either land (represented by '0') or water (represented by '1'). We need to find the size of the largest island in the given matrix. An island is defined as any group of connected '0's surrounded by '1's.

Detailed Explanation

The approach to solve this problem involves using a union-find algorithm with depth-first search (DFS) and breadth-first search (BFS). The idea is to traverse the matrix and mark all connected land cells as visited. We start from each unvisited cell and explore its neighbors. If we find an unvisited neighbor, we mark it as visited and add its size to our current island's size.

Here is a step-by-step breakdown of the solution:

Initialize a variable maxSize to store the maximum size of an island.
Iterate through each cell in the matrix.
If the cell is land ('0'), perform DFS/BFS to find all connected land cells and mark them as visited.
Calculate the size of the current island by subtracting the number of visited cells from the total number of cells.
Update maxSize if the current island's size is greater than maxSize.
Repeat steps 2-5 for each cell in the matrix.

Time complexity: O(m*n) where m and n are the dimensions of the matrix, as we need to visit each cell once.

Space complexity: O(m*n) as we need to store the visited cells.

Optimized Solutions

Java

public class Solution { public int maxAreaOfIsland(int[][] grid) { if (grid == null || grid.length == 0) return 0; int maxSize = 0, m = grid.length, n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { int islandSize = dfs(grid, i, j); maxSize = Math.max(maxSize, islandSize); } } } return maxSize; } private int dfs(int[][] grid, int i, int j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0; grid[i][j] = 0; // mark as visited int size = 1; for (int[][] dir : directions) { int ni = i + dir[0], nj = j + dir[1]; if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length && grid[ni][nj] == 1) { size += dfs(grid, ni, nj); } } return size; } private static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; }