Redundant Connection

Medium

Graph · Union-Find~20m

00:00

Section 1Understand Problem

Section 01

Understand the problem

Restate the problem precisely. Interviewers reward candidates who pause, define the contract, and name the guarantees before coding.

Problem statement

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [aᵢ, bᵢ]` indicates that there is an edge between nodes `aᵢ` and `bᵢ` in the graph. Return an edge that can be removed so that the resulting graph is a tree of `n` nodes. If there are multiple answers, return the answer that occurs last in the input.

Example

edges = [[1,2],[1,3],[2,3]] → [2,3]

Constraints

n == edges.length · 3 ≤ n ≤ 1000 · edges[i].length == 2 · 1 ≤ aᵢ < bᵢ ≤ edges.length

Audio recording unsupported on this browser.

WPM—Fillers0Pace—Thinking0%

Explain the problem in your own words

0 words0 chars

AI Review

Write your thinking above first.

Once you've drafted a response, click Submit for AI review and a senior engineer will critique your reasoning.

Ready to submit Section 1?

The reviewer will check whether you stated inputs, output, guarantees, and any assumption you flagged.

Write at least a couple of sentences explaining the problem before submitting.

AI Interview Prep is optimized for larger screens

Understand the problem