Largest Connected Region

1. Background Knowledge

Connected Component Analysis identifies groups of foreground pixels (1s) that are connected in a binary grid. Two pixels are connected if they share an edge (4-connectivity) or corner (8-connectivity). Union-Find (Disjoint Set Union - DSU) efficiently tracks these equivalence classes by merging connected sets and finding set representatives.

Union-Find Structure maintains:

• parent[i]: parent of node i
• size[i]: size of component rooted at i (for union-by-size)
• Find: Path-compressed root finding with nearly-constant amortized time $O($\alpha$(n))$, where $\alpha$ is the inverse Ackermann function.
• Union: Merges smaller trees into larger ones, preserving size tracking.

Prerequisites: 2D array traversal, coordinate indexing (i*cols + j), 4/8-neighbor definitions.

2. Algorithm Approach

Union-Find with Grid Traversal is optimal for this problem:

1. Treat each 1 pixel as a node
2. Create virtual edges between adjacent 1s
3. Union connected pixels
4. Track maximum component size during unions

Alternatives (less efficient here):

• DFS/BFS: $O(rows \times cols)$ but requires recursion/stack
• Flood-fill: Memory-intensive for large components

Union-Find excels due to $O(n$\alpha$(n))$ amortized time where $n \leq rows \times cols \leq 10,000$.

3. Step-by-Step Strategy

1. Initialize Union-Find for grid size (rows × cols)
 - parent[i] = i, size[i] = 1 for all 1s
 - max_size = 1

2. Assign unique IDs to 1s only (flatten: id = i*cols + j)

3. Iterate grid with 4-connectivity directions:
 [[0,1], [1,0], [0,-1], [-1,0]] // right, down, left, up

4. For each 1 at (i,j):
 - Check right neighbor (i, j+1): if 1, Union(id, right_id)
 - Check down neighbor (i+1, j): if 1, Union(id, down_id)
 - Update max_size = max(max_size, size[find(id)])