bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
MediumAdvanced GraphsLC 1135

Connecting Cities With Minimum Cost

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi. Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1, The cost is the sum of the connections' costs used.

Asked at 2 companies
AmazonUber
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode