What is the brute force approach and complexity for Connecting Cities With Minimum Cost?

Grow the connected group one city at a time, reading every road in each round with time complexity O(N · M) and space complexity O(N).

What is the optimal approach and complexity for Connecting Cities With Minimum Cost?

Sort roads by cost; keep a road only if its two cities are in different groups with optimal time complexity O(M log M) and space complexity O(N).

How do you identify the pattern for Connecting Cities With Minimum Cost?

Look for key signals in the prompt: "two-way roads with a cost" indicates A weighted undirected edge list is given: sort it, then let Union-Find decide each road.; "smallest total cost to connect all cities" indicates Minimum spanning tree: n − 1 roads, no loop, the smallest total.; "return -1 if it is impossible" indicates Kruskal ends with fewer than n − 1 kept roads, so the graph is not connected..

Connecting Cities With Minimum Cost

Medium·LeetCode #1135 Premium Pro OnlySlight Variation

LeetCode

Problem Statement

There are n cities, numbered from 1 to n. You are given connections, a list of two-way roads. Each road [city1, city2, cost] joins two cities and has a cost.

Choose some roads so that every city can reach every other city, at the smallest total cost. Return that total cost. If the roads cannot connect all the cities, return -1.

Input

n, the number of cities, and connections, a list of [city1, city2, cost] roads.

Output

A single integer: the minimum total cost to connect all cities, or -1 if that is impossible.

Example 1

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]

Output: 6

Take road 2–3 (1) and road 1–2 (5). Together they connect all 3 cities for 6. Using 1–3 (6) instead of 1–2 (5) would cost 7.

Example 2

Input: n = 4, connections = [[1,2,3],[3,4,4]]

Output: -1

Cities 1 and 2 are linked to each other, and cities 3 and 4 are linked to each other, but no road joins the two pairs. Some cities cannot be reached.

Example 3

Input: n = 6, connections = [[1,3,1],[4,5,2],[4,6,3],[5,6,4],[2,3,5],[2,4,6],[3,4,7],[1,2,9]]

Output: 17

Keep 1–3 (1), 4–5 (2), 4–6 (3), 2–3 (5) and 2–4 (6): 1 + 2 + 3 + 5 + 6 = 17. Road 5–6 (4) is skipped, because 5 and 6 are already connected through 4.

Constraints

• Cities are numbered from 1 to n.
• Each road joins two cities and has a cost. Roads go both ways.
• Limits on n, the number of roads and the costs are not confirmed (this is a premium problem), so none are given here.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“two-way roads with a cost”

→ A weighted undirected edge list is given: sort it, then let Union-Find decide each road.

“smallest total cost to connect all cities”

→ Minimum spanning tree: n − 1 roads, no loop, the smallest total.

“return -1 if it is impossible”

→ Kruskal ends with fewer than n − 1 kept roads, so the graph is not connected.

Approach Complexity Ladder

Brute Force — naive Prim: reread every road each roundO(N · M)O(N)

Grow the connected group one city at a time, reading every road in each round

Optimal — Kruskal with Union-FindO(M log M)O(N)

Sort roads by cost; keep a road only if its two cities are in different groups

Brute Force Intuition

Start the group with city 1. Each round, read every road and keep the cheapest one that has exactly one city inside the group. Add that outside city and its cost. If no road leaves the group before all cities are in, return -1.

Recognition rule for this sub-pattern:

Sort edges by cost; take an edge only if it joins two different groups.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture