Meta·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Meta Research Engineer coding screen, one algorithmic problem the whole time. Pretty standard graph/island-style question but the twist kept me thinking longer than I expected.

Questions Asked (1)

Given an n x n binary matrix, you can flip at most one 0 to a 1. What is the size of the largest island you can form? An island is defined as a group of 1s connected in four directions.

Algorithms & Data Structures

Author's notes

My first instinct was brute force: try flipping every 0 and run BFS each time.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify all existing islands and label each cell with a unique island ID while recording each island's size. Then, for each 0 cell, compute the sum of sizes of distinct neighboring islands (up to 4) plus 1, and track the maximum. Also consider the case where no 0 is flipped (if the matrix is all 1s).

Pro tip: Clarify edge cases upfront: if the matrix has no 0s, return n*n; if flipping a 0 connects no islands, the answer is at least 1 (or the max existing island size). Mentioning these shows thoroughness.

1. Clarify and handle edge cases

Ask about matrix size constraints, whether flipping is optional, and what to return if no 0 exists. Handle all-1s and all-0s cases early.

2. Label islands and compute sizes

Use BFS/DFS or Union-Find to assign a unique ID to each island and store its size in a hash map. This precomputes all existing island sizes.

3. Evaluate each 0 cell

For every 0, look at its four neighbors, collect distinct island IDs, sum their sizes, add 1 for the flipped cell, and update the maximum.

4. Return the maximum

After scanning all 0s, return the maximum found. If no 0 was flipped (or no 0 exists), return the largest existing island size.

Key Points to Mention

Use BFS/DFS or Union-Find for connected components with O(n^2) time and space.
Store island sizes in a hash map keyed by island ID to avoid recomputation.
When evaluating a 0, deduplicate neighboring island IDs to avoid double-counting.
Consider the case where flipping is not needed (all 1s) and where no 0 exists.
Time complexity: O(n^2) for labeling plus O(n^2) for scanning 0s, overall O(n^2).
Space complexity: O(n^2) for the visited/label matrix and island size map.

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