Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Uber SWE coding round, got a grid problem that looked manageable at first glance but has enough edge cases to trip you up if you're not careful with the union-find or BFS approach.

Questions Asked (1)

Given an n x n binary matrix, you can flip at most one 0 to a 1. What is the maximum size of a 4-directionally connected island you can achieve after that flip?

Algorithms & Data Structures

Author's notes

My first instinct was to BFS from every zero cell and count neighbors, which technically works but is way too slow on a 500x500 grid.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pass approach: first label each existing island and compute its size using DFS/BFS. Then for each 0 cell, sum the sizes of distinct neighboring islands plus 1, and track the maximum; also consider the case where no flip is needed (if the matrix is all 1s or flipping doesn't increase the max).

Pro tip: Clarify edge cases upfront (e.g., all 1s, no 0s, multiple islands) and mention that you'd handle them gracefully; this shows attention to detail and prevents bugs in interviews.

1. Understand the problem and edge cases

Restate the problem: we can flip at most one 0 to 1, and we want the maximum connected island size. Consider edge cases: no 0s, all 1s, no 1s, and multiple islands.

2. Label islands and compute sizes

Traverse the grid; for each unvisited 1, perform DFS/BFS to assign a unique island ID and record its size. Use a hash map to store island ID to size.

3. Evaluate each 0 cell

For each 0, look at its 4 neighbors; collect distinct island IDs and sum their sizes. The potential island size if flipping this 0 is sum + 1. Track the maximum.

4. Handle the no-flip case

If there are no 0s or if flipping any 0 doesn't increase the max (e.g., all 1s), the answer is the maximum island size found in step 2. Also consider if the grid has no 1s, then flipping one 0 gives size 1.

5. Return the maximum

After evaluating all 0s, return the maximum of the best flip result and the original maximum island size.

Key Points to Mention

Use DFS/BFS to label islands and compute their sizes efficiently.
For each 0, sum sizes of distinct neighboring islands (avoid double-counting).
Time complexity: O(n^2) for grid traversal and O(n^2) for checking each 0, overall O(n^2).
Space complexity: O(n^2) for visited array and island size map.
Edge cases: all 1s (answer n^2), all 0s (answer 1), no 0s (answer max island size).
Optimization: only consider 0s that are adjacent to at least one 1; otherwise flipping gives size 1.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.