Making a Large Island Using DSU
Problem and examples
Given an n x n binary grid where each cell is either 0 or 1, your task is to determine the size of the largest island that can be formed by converting at most one 0 to 1.
An island is a group of 1s connected horizontally or vertically (not diagonally). You are allowed to change at most one 0 into 1. The goal is to identify the maximum size of a connected island that can be achieved with such a transformation.
| Grid | Output | Description |
|---|---|---|
| [[1, 0], [0, 1]] | 3 | Flipping any 0 connects the two 1s into a single island of size 3 |
| [[1, 1], [1, 0]] | 4 | Flipping the bottom-right 0 gives a full 2x2 island |
| [[0, 0], [0, 0]] | 1 | All sea — only one flip allowed, gives a single land cell |
| [[1, 1], [1, 1]] | 4 | All land — no flip needed, entire grid is one island |
| [[1, 0, 1], [0, 0, 0], [1, 0, 1]] | 5 | Flipping the center cell (1,1) connects four corner islands |
| [[1, 1, 0], [1, 0, 0], [0, 0, 1]] | 5 | Flipping (1,1) connects the top-left cluster to the bottom-right |
| [[0, 1, 0], [1, 0, 1], [0, 1, 0]] | 5 | Flipping center (1,1) connects all diagonally placed 1s into one island |
| [[1, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, 1, 1]] | 14 | Flipping any center 0 expands the outer ring island inward |
| [[0, 1, 0], [0, 0, 0], [1, 0, 1]] | 3 | Flipping center (1,1) connects up to 3 separate 1s |
| [[1]] | 1 | Single land cell — already one island |
| [[0]] | 1 | Single sea cell — flipping gives one island of size 1 |
Explore Making a Large Island Using DSU
Load an example or enter your own input. Use the player controls to follow each change.
Understanding the Problem
We are given a binary grid where 1 represents land and 0 represents water. An island is formed by connecting adjacent 1s either vertically or horizontally. Our goal is to flip at most one 0 to 1 and determine the size of the largest island possible after this operation.
To solve this efficiently, we use the Disjoint Set Union (DSU) data structure to track connected components (i.e., islands) and their sizes. We simulate flipping each 0 to a 1 and check which islands it could connect to, to maximize the resulting island size.
Step-by-Step Solution with Example
Step 1: Group All Existing Islands Using DSU
We iterate through each cell in the grid. Whenever we find a 1, we perform a union operation with its adjacent 1s (up, down, left, right). Each island is treated as a connected component in DSU.
Step 2: Track the Size of Each Island
We maintain a map that stores the size of each component, using the root representative as the key. This way, we know how big each island is, which is critical when we later evaluate the impact of flipping a 0.
Step 3: Evaluate Each 0 for Maximum Island Size
Now, we scan the grid again. For every 0 cell, we:
- Look in the four directions (up, down, left, right).
- Collect the root IDs of neighboring
1s (i.e., neighboring islands). - Make sure not to count the same island twice (use a set).
- Sum up the sizes of these unique neighboring islands and add 1 (for the current 0 being flipped to 1).
Step 4: Track the Maximum Island Size
During the above evaluations, we keep updating the maximum island size encountered. This ensures we return the largest possible island size that can be formed with one flip.
Step 5: Handle the Case Where No 0 Exists
If the grid has no 0s, the largest island is the entire grid of 1s. In that case, we return the size of the whole grid.
Edge Cases
- All 1s: No 0 to flip. The answer is the total count of 1s.
- All 0s: Flipping any one 0 gives an island of size 1.
- Disconnected 1s: Flipping a 0 between them can connect multiple islands.
- Flipping a border 0: Still needs to check only valid neighbors within grid bounds.
Finally
This problem is a great example of how Disjoint Set Union can be used to manage groups of connected elements efficiently. Instead of recalculating connected components multiple times, we preprocess the island structure once and reuse the information for every possible 0 we might flip. The use of sets to avoid duplicate island counting ensures correctness, and edge cases are naturally handled through the logic flow.
- Initialize DSU for each cell in the grid with parent pointers and size mappings.
- For each cell with value 1:
- Check its 4 neighbors.
- If the neighbor is also 1, union the current cell and neighbor in DSU.
- Map each island's root parent to its size.
- For each cell with value 0:
- Collect unique parent IDs of its 4-directional 1-neighbors.
- Sum their sizes + 1 to simulate flipping the 0 to 1.
- Update max island size accordingly.
- If no 0s exist, return the size of the entire grid as the island.
Implementation and efficiency
C implementation
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
int n;
int grid[MAX_N][MAX_N];
int parent[MAX_N * MAX_N];
int size[MAX_N * MAX_N];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union_sets(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (size[a] < size[b]) {
int temp = a; a = b; b = temp;
}
parent[b] = a;
size[a] += size[b];
}
}
int index(int i, int j) {
return i * n + j;
}
int largestIsland(int grid[MAX_N][MAX_N], int n) {
for (int i = 0; i < n * n; i++) {
parent[i] = i;
size[i] = 1;
}
int dirs[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
for (int d = 0; d < 4; d++) {
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
union_sets(index(i,j), index(ni,nj));
}
}
}
}
}
int maxIsland = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
int total = 1;
int seen[MAX_N * MAX_N] = {0};
for (int d = 0; d < 4; d++) {
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
int root = find(index(ni, nj));
if (!seen[root]) {
total += size[root];
seen[root] = 1;
}
}
}
if (total > maxIsland) maxIsland = total;
}
}
}
if (maxIsland == 0) {
for (int i = 0; i < n * n; i++) {
if (parent[i] == i && size[i] > maxIsland) maxIsland = size[i];
}
}
return maxIsland;
}
int main() {
n = 2;
int exampleGrid[2][2] = {{1, 0}, {0, 1}};
printf("Largest island size: %d\n", largestIsland(exampleGrid, n));
return 0;
}C++ implementation
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class DSU {
private:
vector<int> parent, size;
public:
DSU(int n) {
parent.resize(n);
size.resize(n, 1);
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
int getSize(int x) {
return size[find(x)];
}
};
int index(int i, int j, int n) {
return i * n + j;
}
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
DSU dsu(n * n);
vector<pair<int, int>> dirs = {{0,1},{1,0},{-1,0},{0,-1}};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
for (auto& d : dirs) {
int ni = i + d.first, nj = j + d.second;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
dsu.unite(index(i,j,n), index(ni,nj,n));
}
}
}
}
}
int maxIsland = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
unordered_set<int> seen;
int total = 1;
for (auto& d : dirs) {
int ni = i + d.first, nj = j + d.second;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
int root = dsu.find(index(ni,nj,n));
if (seen.find(root) == seen.end()) {
total += dsu.getSize(root);
seen.insert(root);
}
}
}
if (total > maxIsland) maxIsland = total;
}
}
}
if (maxIsland == 0) {
for (int i = 0; i < n * n; ++i) {
if (dsu.find(i) == i && dsu.getSize(i) > maxIsland) maxIsland = dsu.getSize(i);
}
}
return maxIsland;
}
int main() {
vector<vector<int>> grid = {{1,0},{0,1}};
cout << "Largest island size: " << largestIsland(grid) << endl;
return 0;
}Python implementation
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
a = self.find(a)
b = self.find(b)
if a != b:
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
def get_size(self, x):
return self.size[self.find(x)]
def largest_island(grid):
n = len(grid)
dsu = DSU(n * n)
directions = [(0,1), (1,0), (-1,0), (0,-1)]
def index(i, j):
return i * n + j
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
for dx, dy in directions:
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:
dsu.union(index(i,j), index(ni,nj))
max_island = 0
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
seen = set()
total = 1
for dx, dy in directions:
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:
root = dsu.find(index(ni,nj))
if root not in seen:
total += dsu.get_size(root)
seen.add(root)
max_island = max(max_island, total)
if max_island == 0:
counts = {}
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
root = dsu.find(index(i,j))
counts[root] = dsu.get_size(root)
max_island = max(counts.values()) if counts else 0
return max_island
if __name__ == '__main__':
grid = [[1,0],[0,1]]
print("Largest island size:", largest_island(grid))Java implementation
public class LargestIsland {
static class DSU {
int[] parent, size;
DSU(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (size[a] < size[b]) {
int temp = a;
a = b;
b = temp;
}
parent[b] = a;
size[a] += size[b];
}
}
int getSize(int x) {
return size[find(x)];
}
}
static int index(int i, int j, int n) {
return i * n + j;
}
public static int largestIsland(int[][] grid) {
int n = grid.length;
DSU dsu = new DSU(n * n);
int[][] dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
dsu.union(index(i,j,n), index(ni,nj,n));
}
}
}
}
}
int maxIsland = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
java.util.HashSet<Integer> seen = new java.util.HashSet<>();
int total = 1;
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
int root = dsu.find(index(ni,nj,n));
if (!seen.contains(root)) {
total += dsu.getSize(root);
seen.add(root);
}
}
}
maxIsland = Math.max(maxIsland, total);
}
}
}
if (maxIsland == 0) {
for (int i = 0; i < n * n; i++) {
if (dsu.find(i) == i) maxIsland = Math.max(maxIsland, dsu.getSize(i));
}
}
return maxIsland;
}
public static void main(String[] args) {
int[][] grid = {{1, 0}, {0, 1}};
System.out.println("Largest island size: " + largestIsland(grid));
}
}JavaScript implementation
class DSU {
constructor(n) {
this.parent = Array(n).fill(0).map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let px = this.find(x), py = this.find(y);
if (px === py) return;
if (this.size[px] < this.size[py]) [px, py] = [py, px];
this.parent[py] = px;
this.size[px] += this.size[py];
}
getSize(x) {
return this.size[this.find(x)];
}
}
function largestIsland(grid) {
const n = grid.length;
const dsu = new DSU(n * n);
const dirs = [[0,1],[1,0],[-1,0],[0,-1]];
const index = (i, j) => i * n + j;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
for (const [dx, dy] of dirs) {
let ni = i + dx, nj = j + dy;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
dsu.union(index(i,j), index(ni,nj));
}
}
}
}
}
let maxIsland = 0;
const seen = new Set();
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 0) {
let total = 1;
seen.clear();
for (const [dx, dy] of dirs) {
const ni = i + dx, nj = j + dy;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
let root = dsu.find(index(ni, nj));
if (!seen.has(root)) {
total += dsu.getSize(root);
seen.add(root);
}
}
}
maxIsland = Math.max(maxIsland, total);
}
}
}
if (maxIsland === 0) {
const rootSizes = new Map();
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
let root = dsu.find(index(i, j));
rootSizes.set(root, dsu.getSize(root));
}
}
}
for (const size of rootSizes.values()) maxIsland = Math.max(maxIsland, size);
}
return maxIsland;
}
const grid = [[1, 0], [0, 1]];
console.log("Largest island size:", largestIsland(grid));Go implementation
package main
import "fmt"
func index(i, j, n int) int {
return i*n + j
}
type DSU struct {
parent []int
size []int
}
func NewDSU(n int) *DSU {
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
return &DSU{parent, size}
}
func (d *DSU) find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.find(d.parent[x])
}
return d.parent[x]
}
func (d *DSU) union(a, b int) {
a = d.find(a)
b = d.find(b)
if a != b {
if d.size[a] < d.size[b] {
a, b = b, a
}
d.parent[b] = a
d.size[a] += d.size[b]
}
}
func (d *DSU) getSize(x int) int {
return d.size[d.find(x)]
}
func largestIsland(grid [][]int) int {
n := len(grid)
dsu := NewDSU(n * n)
dirs := [][]int{{0,1}, {1,0}, {-1,0}, {0,-1}}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
for _, d := range dirs {
ni, nj := i + d[0], j + d[1]
if ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1 {
dsu.union(index(i,j,n), index(ni,nj,n))
}
}
}
}
}
maxIsland := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
seen := make(map[int]bool)
total := 1
for _, d := range dirs {
ni, nj := i + d[0], j + d[1]
if ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1 {
root := dsu.find(index(ni,nj,n))
if !seen[root] {
total += dsu.getSize(root)
seen[root] = true
}
}
}
if total > maxIsland {
maxIsland = total
}
}
}
}
if maxIsland == 0 {
for i := 0; i < n*n; i++ {
if dsu.find(i) == i && dsu.getSize(i) > maxIsland {
maxIsland = dsu.getSize(i)
}
}
}
return maxIsland
}
func main() {
grid := [][]int{{1, 0}, {0, 1}}
fmt.Println("Largest island size:", largestIsland(grid))
}Rust implementation
fn index(i: usize, j: usize, n: usize) -> usize {
i * n + j
}
struct DSU {
parent: Vec<usize>,
size: Vec<usize>,
}
impl DSU {
fn new(n: usize) -> Self {
DSU {
parent: (0..n).collect(),
size: vec![1; n],
}
}
fn find(&mut self, x: usize) -> usize {
if self.parent[x] != x {
self.parent[x] = self.find(self.parent[x]);
}
self.parent[x]
}
fn union(&mut self, a: usize, b: usize) {
let mut a = self.find(a);
let mut b = self.find(b);
if a != b {
if self.size[a] < self.size[b] {
std::mem::swap(&mut a, &mut b);
}
self.parent[b] = a;
self.size[a] += self.size[b];
}
}
fn get_size(&mut self, x: usize) -> usize {
self.size[self.find(x)]
}
}
fn largest_island(grid: &Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let mut dsu = DSU::new(n * n);
let dirs = vec![(0,1),(1,0),(-1,0),(0,-1)];
for i in 0..n {
for j in 0..n {
if grid[i][j] == 1 {
for (dx, dy) in &dirs {
let ni = i as i32 + dx;
let nj = j as i32 + dy;
if ni >= 0 && nj >= 0 && (ni as usize) < n && (nj as usize) < n && grid[ni as usize][nj as usize] == 1 {
dsu.union(index(i,j,n), index(ni as usize, nj as usize, n));
}
}
}
}
}
let mut max_island = 0;
for i in 0..n {
for j in 0..n {
if grid[i][j] == 0 {
let mut seen = std::collections::HashSet::new();
let mut total = 1;
for (dx, dy) in &dirs {
let ni = i as i32 + dx;
let nj = j as i32 + dy;
if ni >= 0 && nj >= 0 && (ni as usize) < n && (nj as usize) < n && grid[ni as usize][nj as usize] == 1 {
let root = dsu.find(index(ni as usize, nj as usize, n));
if !seen.contains(&root) {
total += dsu.get_size(root);
seen.insert(root);
}
}
}
if total > max_island {
max_island = total;
}
}
}
}
if max_island == 0 {
for i in 0..n*n {
if dsu.find(i) == i && dsu.get_size(i) > max_island {
max_island = dsu.get_size(i);
}
}
}
max_island as i32
}
fn main() {
let grid = vec![vec![1,0], vec![0,1]];
println!("Largest island size: {}", largest_island(&grid));
}Kotlin implementation
fun index(i: Int, j: Int, n: Int): Int = i * n + j
class DSU(n: Int) {
private val parent = IntArray(n) { it }
private val size = IntArray(n) { 1 }
fun find(x: Int): Int {
if (parent[x] != x) parent[x] = find(parent[x])
return parent[x]
}
fun union(a: Int, b: Int) {
var aRoot = find(a)
var bRoot = find(b)
if (aRoot != bRoot) {
if (size[aRoot] < size[bRoot]) {
val temp = aRoot
aRoot = bRoot
bRoot = temp
}
parent[bRoot] = aRoot
size[aRoot] += size[bRoot]
}
}
fun getSize(x: Int) = size[find(x)]
}
fun largestIsland(grid: Array<IntArray>): Int {
val n = grid.size
val dsu = DSU(n * n)
val dirs = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,-1))
for (i in 0 until n) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
for (d in dirs) {
val ni = i + d[0]
val nj = j + d[1]
if (ni in 0 until n && nj in 0 until n && grid[ni][nj] == 1) {
dsu.union(index(i,j,n), index(ni,nj,n))
}
}
}
}
}
var maxIsland = 0
for (i in 0 until n) {
for (j in 0 until n) {
if (grid[i][j] == 0) {
val seen = mutableSetOf<Int>()
var total = 1
for (d in dirs) {
val ni = i + d[0]
val nj = j + d[1]
if (ni in 0 until n && nj in 0 until n && grid[ni][nj] == 1) {
val root = dsu.find(index(ni,nj,n))
if (root !in seen) {
total += dsu.getSize(root)
seen.add(root)
}
}
}
if (total > maxIsland) maxIsland = total
}
}
}
if (maxIsland == 0) {
for (i in 0 until n*n) {
if (dsu.find(i) == i && dsu.getSize(i) > maxIsland) maxIsland = dsu.getSize(i)
}
}
return maxIsland
}
fun main() {
val grid = arrayOf(intArrayOf(1, 0), intArrayOf(0, 1))
println("Largest island size: ${largestIsland(grid)}")
}Swift implementation
struct DSU {
var parent: [Int]
var size: [Int]
init(_ n: Int) {
parent = Array(0..<n)
size = Array(repeating: 1, count: n)
}
mutating func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
mutating func union(_ a: Int, _ b: Int) {
var a = find(a)
var b = find(b)
if a != b {
if size[a] < size[b] {
swap(&a, &b)
}
parent[b] = a
size[a] += size[b]
}
}
func getSize(_ x: Int) -> Int {
size[find(x)]
}
}
func index(_ i: Int, _ j: Int, _ n: Int) -> Int {
return i * n + j
}
func largestIsland(_ grid: [[Int]]) -> Int {
let n = grid.count
var dsu = DSU(n * n)
let dirs = [(0,1),(1,0),(-1,0),(0,-1)]
for i in 0..<n {
for j in 0..<n {
if grid[i][j] == 1 {
for d in dirs {
let ni = i + d.0
let nj = j + d.1
if ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1 {
dsu.union(index(i,j,n), index(ni,nj,n))
}
}
}
}
}
var maxIsland = 0
for i in 0..<n {
for j in 0..<n {
if grid[i][j] == 0 {
var seen = Set<Int>()
var total = 1
for d in dirs {
let ni = i + d.0
let nj = j + d.1
if ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1 {
let root = dsu.find(index(ni,nj,n))
if !seen.contains(root) {
total += dsu.getSize(root)
seen.insert(root)
}
}
}
if total > maxIsland {
maxIsland = total
}
}
}
}
if maxIsland == 0 {
for i in 0..<n*n {
if dsu.find(i) == i && dsu.getSize(i) > maxIsland {
maxIsland = dsu.getSize(i)
}
}
}
return maxIsland
}
let grid = [[1, 0], [0, 1]]
print("Largest island size: \(largestIsland(grid))")TypeScript implementation
class DSU {
parent: number[];
size: number[];
constructor(n: number) {
this.parent = Array(n).fill(0).map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x: number, y: number): void {
let px = this.find(x), py = this.find(y);
if (px === py) return;
if (this.size[px] < this.size[py]) [px, py] = [py, px];
this.parent[py] = px;
this.size[px] += this.size[py];
}
getSize(x: number): number {
return this.size[this.find(x)];
}
}
function largestIsland(grid: number[][]): number {
const n = grid.length;
const dsu = new DSU(n * n);
const dirs = [[0,1],[1,0],[-1,0],[0,-1]];
const index = (i: number, j: number) => i * n + j;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
for (const [dx, dy] of dirs) {
let ni = i + dx, nj = j + dy;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
dsu.union(index(i,j), index(ni,nj));
}
}
}
}
}
let maxIsland = 0;
const seen = new Set<number>();
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 0) {
let total = 1;
seen.clear();
for (const [dx, dy] of dirs) {
const ni = i + dx, nj = j + dy;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
let root = dsu.find(index(ni, nj));
if (!seen.has(root)) {
total += dsu.getSize(root);
seen.add(root);
}
}
}
maxIsland = Math.max(maxIsland, total);
}
}
}
if (maxIsland === 0) {
const rootSizes = new Map<number, number>();
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
let root = dsu.find(index(i, j));
rootSizes.set(root, dsu.getSize(root));
}
}
}
for (const size of rootSizes.values()) maxIsland = Math.max(maxIsland, size);
}
return maxIsland;
}
const grid = [[1, 0], [0, 1]];
console.log("Largest island size:", largestIsland(grid));