Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Bytedance SWE interview with a graph/union-find problem that sounds straightforward until you actually sit down to code it under pressure.

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 4-directionally connected island you can form after doing so?

Algorithms & Data Structures

Author's notes

I went straight for BFS to label each island and track sizes, then scanned for zeros and checked neighboring island labels to sum up potential merges.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify all existing islands and label each cell with its island ID and size using DFS/BFS. Then, for each 0 cell, compute the sum of sizes of distinct neighboring islands plus 1, and track the maximum. If no 0 exists, return the size of the largest island.

Pro tip: Use a hash set to collect distinct neighboring island IDs for each 0 to avoid double-counting when the same island touches the 0 from multiple directions. Also, handle the edge case where the matrix has no 0s by returning the maximum island size found during labeling.

1. Label islands and compute sizes

Traverse the matrix and for each unvisited 1, perform DFS/BFS to assign an island ID and calculate its size. Store sizes in a map or array.

2. Iterate over each 0 cell

For every cell with value 0, examine its four neighbors. Collect the island IDs of neighboring 1s into a set to ensure uniqueness.

3. Calculate potential island size

Sum the sizes of the distinct neighboring islands and add 1 (for flipping the 0). Update the maximum size if this sum is larger.

4. Handle edge cases

If there are no 0s in the matrix, return the maximum island size found during labeling. Also, consider the case where flipping a 0 connects no islands (sum = 1).

Key Points to Mention

Use DFS/BFS to label islands and compute their sizes efficiently.
Employ a set to avoid double-counting the same island when checking neighbors of a 0.
Time complexity: O(n^2) for labeling plus O(n^2) for checking each 0, overall O(n^2).
Space complexity: O(n^2) for the visited/label matrix and island size map.
Edge case: matrix with no 0s, return the largest existing island size.
Edge case: matrix with all 0s, flipping one 0 yields island size 1.

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