Making A Large Island
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the largest group of connected 1s in an n x n binary grid after converting at most one 0 to 1, Disjoint Set Union, Union by Size, Path Compression, Matrices, Grid Traversal, Connected Components, Brute Force, Set, Time Complexity, Space Complexity, graph representation, union-find, graph components, set, grid traversal, brute force optimization, DSU Applications, Grid as a Graph, Sets & Hash Sets, DSU Optimizations (Union by Size/Rank & Path Compression).
Largest Group of Connected 1s Problem Statement You are given an n x n binary grid. A grid is said to be binary if every value in the grid is either 1 or 0. You can change at most one cell in the grid from 0 to 1. Your task is to find the largest group of connected 1's that can be formed after this modification. Two cells are considered connected if they are adjacent (share a common side) and have the same value. Input Specification The input consists of a square binary grid grid of size n x n. Output Specification Return an integer representing the size of the largest group of connected 1s that can be formed. Constraints Implicitly, n will be within typical competitive programming limits (e.g., 1 <= n <= 500, though not explicitly stated in the source content, it's a common competitive programming constraint). Sample Test Cases Example 1: Input: Output: Explanation: Changing the cell at (2,2) (0 indexed) from 0 to 1 results in the largest group of 20 connected 1s. Example 2: Input: Output: Explanation: If we change (0,0) to 1, we get connected group of (0,0), (1,0) and (0,1) which gives size 3. If we change (0,1) to 1, we get connected group of (0,1), (0,0) and (1,1) which gives size 3. Similarly for other 0s. (Note: Example 2 from original text was not complete for parsing, provided a small custom one that fits the problem.)