Friend Circles and Redundant Connections
Zomato / Eternal● MediumFULLTIMEPHONE SCREENProblem statement
People are labeled from 0 through peopleCount - 1. Each undirected friendship joins two people.
Return [circleCount, redundantEdgeCount], where a friend circle is a connected component and an edge is redundant when its endpoints were already connected by earlier edges. Isolated people count as circles.
Function
countCirclesAndRedundantEdges(peopleCount: int, friendships: int[][]) → int[]Examples
Example 1
peopleCount = 5friendships = [[0,1],[2,3],[3,4]]return = [2,0]Case 1 exercises the documented deterministic contract.
Example 2
peopleCount = 3friendships = [[0,1],[1,2],[0,2]]return = [1,1]Case 2 exercises the documented deterministic contract.
Example 3
peopleCount = 4friendships = []return = [4,0]Case 3 exercises the documented deterministic contract.
Constraints
1 <= peopleCount <= 200000.0 <= friendships.length <= 200000.- Endpoints are valid labels and self-edges are permitted.