Dropbox·Data Scientist·Technical Phone Screen
- Given an n×n binary grid where 1 is land and 0 is water with 4-directional connectivity, return the size of the largest island you can achieve by flipping at most one 0 to 1. Your solution should run in O(n^2) time.
- Follow-up: if you must flip exactly one 1 to 0, what is the minimum number of islands that can result? Describe an algorithm and its complexity.
- Follow-up: if you can perform one 0-to-1 flip and one 1-to-0 flip on distinct cells in any order, what is the maximum possible largest island size? Prove optimality or provide a counterexample.
- How would you handle edge cases like an all-zeros grid or an all-ones grid, recursion depth limits for large n, and adapting the solution for very large grids using chunking, streaming, or union-find labeling?
“I knew the general approach: label each island with a unique id using union-find or BFS, store each island's size, then for every 0-cell check its distinct neighboring island ids and sum their sizes plus one.”