Compute max island with constrained flips

Q: Compute max island with constrained flips

This question evaluates understanding of grid-based graph connectivity, connected-component labeling, and algorithmic complexity analysis (time and space) within the Coding & Algorithms domain, emphasizing practical algorithm design for large-scale inputs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an n×n binary grid G where 1=land and 0=water with 4-directional connectivity, return the size of the largest island achievable by flipping at most one 0 to 1. n can be up to 10^3. Provide an O(n^2) time, O(n^2) or better space solution and justify correctness. Follow-ups: (a) If you must flip exactly one 1 to 0, what is the minimum number of islands you can achieve? Give an algorithm and complexity. (b) If you may perform one 0→1 flip and one 1→0 flip on distinct cells (in any order), compute the maximum possible largest-island size and prove optimality or provide a counterexample. Discuss edge cases (all 0s, all 1s), recursion-depth limits, and how you’d adapt for very large grids (e.g., chunking/streaming or union-find labeling).

Compute max island with constrained flips

Overview

Comments (0)