Find the Extra Edge
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an undirected graph that started as a tree with `n` nodes labeled from `1` to `n`. One additional edge was then added between two different existing nodes, creating exactly one cycle.
You are given an array `edges`, where `edges[i] = [u, v]` represents an undirected edge between nodes `u` and `v`. Return the edge that can be removed so that the remaining graph is a tree again.
If multiple edges could be removed, return the one that appears last in the input order.
**Example**
```text
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
```
**Constraints**
- `n == edges.length`
- `3 <= n <= 1000`
- `1 <= u, v <= n`
- `u != v`
- The input graph is connected and contains exactly one cycle.
Overview: This question evaluates understanding of graph theory concepts—cycle formation and edge connectivity—and the competency in applying graph algorithm techniques to identify and remove a redundant edge in an undirected graph.
You are given an undirected graph that originally formed a tree with nodes labeled from 1 to n. Exactly one additional edge was added between two different existing nodes, creating exactly one cycle.
Given the list of edges, return the edge that can be removed so the graph becomes a tree again.
If more than one edge could be removed, return the one that appears last in the input order.
Constraints
- n == len(edges)
- 3 <= n <= 1000
- 1 <= u, v <= n
- u != v
- The graph is connected and contains exactly one cycle
Examples
Input: ([[1, 2], [1, 3], [2, 3]],)
Expected Output: [2, 3]
Explanation: This is the smallest valid case. The third edge closes the cycle 1-2-3-1, so removing [2, 3] restores a tree.
Input: ([[1, 4], [1, 2], [2, 3], [3, 4]],)
Expected Output: [3, 4]
Explanation: All four edges are part of the cycle. Any of them could be removed, so we return the one that appears last in the input: [3, 4].
Hints
- A tree has no cycles. As you process edges one by one, what does it mean if the two endpoints are already connected?
- Use a Disjoint Set Union (Union-Find) structure to track connected components efficiently while scanning the edges in input order.
Community answers
Answer by rzcsong
// 11:43AM - 12:26PM
// Brutal Force: remove an edge and see if it can become a tree, remove the edge from the last to front
// Then do BFS to see if we can iterate all nodes in the graph
// Time complexity: O(N * N) where N is total number of nodes
// Optimization?
public class Solution {
public int[] solution(int[][] edges) {
if (edges == null || edges.length == 0) {
return new int[0];
}
Map> graph = new HashMap<>();
for (int i = 0; i < edges.length; i++) {
Set set = graph.getOrDefault(edges[i][0], new HashSet<>());
set.add(edges[i][1]);
graph.put(edges[i][0], set);
set = graph.getOrDefault(edges[i][1], new HashSet<>());
set.add(edges[i][0]);
graph.put(edges[i][1], set);
}
for (int i = edges.length-1; i >= 0; i--) {
int[] edgeToRemove = edges[i];
removeNodes(graph, edgeToRemove[0], edgeToRemove[1]);
removeNodes(graph, edgeToRemove[1], edgeToRemove[0]);
Iterator itr = graph.keySet().iterator();//First element in the updated graph is the node we want to begin
boolean foundCircle = bfs(graph, itr.next());
if (!foundCircle) {
return edgeToRemove;
}
// To do: Add back the nodes and edges
addBackNodes(graph, edgeToRemove[0], edgeToRemove[1]);
addBackNodes(graph, edgeToRemove[1], edgeToRemove[0]);
}
return null;// It shouldn't occur according to constraint
}
private void addBackNodes(Map> graph, int keyToAdd, int valToAdd) {
Set updatedSet = graph.getOrDefault(keyToAdd, new HashSet());
updatedSet.add(valToAdd);
graph.put(keyToAdd, updatedSet);
}
private void removeNodes(Map> graph