Compute max island with constrained flips
Company: Dropbox
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Overview: 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.
Read the full Dropbox Data Scientist interview experience this question came from
Return the largest 4-connected island size achievable by flipping at most one 0 to 1.
Constraints
- grid is n by n and contains 0/1
Examples
Input: ([[1, 0], [0, 1]],)
Expected Output: 3
Explanation: Flip connects two diagonal islands through one cell only to adjacent land.
Input: ([[1, 1], [1, 1]],)
Expected Output: 4
Explanation: All land.
Hints
- Label each island and size, then evaluate each zero by unique neighboring island ids.