Graph Real-Life Problems
What is this?
Two problems that start as graph or matching questions and finish somewhere else. Smallest String With Swaps finds which positions can reach each other with union-find (or a DFS/BFS), and then the answer is a sort. Campus Bikes II looks like a matching problem with an easy greedy and is really a bitmask DP, because the greedy is wrong.
Both are about what comes after you have the structure.
Fun fact: the greedy for Campus Bikes II (repeatedly take the closest remaining worker and bike pair) is not merely unproven, it fails on a four-point input. Put workers at
(0,0)and(0,2), bikes at(0,1)and(1,0). Both workers are at distance 1 from bike(0,1), and the usual tie-break by worker index gives it to the first worker. The second worker is left with a cost-3 ride, total 4. Giving(0,0)the other bike costs 1 + 1 = 2. That greedy is the right answer to a different problem, Campus Bikes I, which asks for exactly that pairing rule rather than the minimum total.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: connectivity tells you what is possible; a second technique, a sort or a DP over subsets, picks the best among the possibilities. Stopping at the graph gives you half a solution.
1. Connectivity, then a sort
The given pairs are not the only swaps available. Swaps compose, so any permutation within a connected component is reachable and each component's characters can be arranged freely:
for a, b in pairs: union(a, b)
groups = defaultdict(list)
for i in range(len(s)): groups[find(i)].append(i)
out = list(s)
for idxs in groups.values():
for i, ch in zip(sorted(idxs), sorted(out[i] for i in idxs)):
out[i] = ch # smallest char at the smallest index
Sorting the indices and the characters separately, then zipping them, is what makes the result lexicographically smallest: within a component the earliest position gets the smallest available character. Positions in no pair form singleton components and are left alone by the same code, so there is no special case.
Union-find with path halving and union by size is what the lesson codes. An iterative DFS or BFS over the index graph finds the same components. Either way the cost is O(n log n + m alpha(n)), where m is the number of pairs and the n log n is the sorting.
2. When the greedy fails, enumerate the subsets
dp = [inf] * (1 << m); dp[0] = 0
for mask in range(1 << m):
if dp[mask] == inf: continue
w = popcount(mask) # the worker to assign next
if w == n: continue
for b in range(m):
if not mask >> b & 1:
dp[mask | 1 << b] = min(dp[mask | 1 << b], dp[mask] + dist(workers[w], bikes[b]))
return min(dp[mask] for mask in range(1 << m) if popcount(mask) == n)
The trick that removes a whole DP dimension: the number of bits set in the mask is the index of the next worker. Workers are assigned in order, so "which bikes are taken" already determines "how many workers are done". One dimension instead of two, and the cost is O(2^m * m) time and O(2^m) space, fine because m <= 10. The lesson also shows the brute-force search over assignments and the running-sum DFS prune before the bitmask DP.
Naming why the greedy fails is worth as much here as the DP itself.
3. A 30-second worked example (swaps)
s = "dcab", pairs = [[0,3], [1,2]]
Add the single pair [0,2] and everything merges into one component. All four characters can then be arranged freely, and the answer improves to "abcd". One extra edge, a completely different result, and not a line of the algorithm changes.
4. Where you'll actually meet this
- Dispatch and delivery. Assigning drivers to requests at minimum total distance is the same objective as Campus Bikes II. Systems with many agents use the Hungarian algorithm or min-cost flow instead of a bitmask.
- Small exact assignment. With a handful of agents and a handful of targets, an exact bitmask DP is cheap and removes the guesswork.
- Grouping by transitive rules. "These records are the same if A matches B and B matches C" is a connected-components question, and union-find is the usual tool.
- Rearrangement constraints. Any "these positions may be rearranged among themselves" rule is a component sort.
5. Problems in this chapter
Smallest String With Swaps
Lexicographically smallest string reachable by repeated swaps. Union the paired indices (or walk the index graph with an iterative DFS/BFS), then sort each component's indices and characters and write them back in order.
Pattern: union-find + per-component sort. Target: O(n log n + m alpha(n)) time, O(n) space.
Campus Bikes II
Assign each worker a distinct bike minimising total Manhattan distance. DP over the set of used bikes, with the popcount naming the next worker.
Pattern: bitmask DP over subsets. Target: O(2^m * m) time, O(2^m) space.
6. Common pitfalls
- Only swapping the listed pairs. Swaps compose, so the reachable set is the whole connected component.
- Sorting the whole string. Only positions inside one component may be permuted.
- Sorting characters but not indices. The component's slots must be filled in ascending index order.
- Reusing the nearest-pair greedy from Campus Bikes I. Different question, and there is a four-point counterexample.
- Adding a worker dimension to the DP. The popcount of the mask already says which worker is next.
- Iterating masks out of order. Ascending order guarantees every predecessor state is final before it is read.
- Reading the answer from
dp[full]. Withm > nthe answer is the best mask with exactlynbits set. - Forgetting singleton components. They need no special handling, but only if the grouping includes every index.
7. Key takeaways
- Connectivity establishes what is possible; a second step chooses the best of it.
- Swaps compose, which turns a pair list into components and the problem into a sort.
- Smallest character at the smallest index, per component, is the whole lexicographic argument.
- A plausible greedy needs a counterexample or a proof. Here the counterexample has four points.
- A subset mask can encode two things at once. Its popcount removes an entire DP dimension.
- Small constraints are a hint.
m <= 10is the interviewer telling you2^mis acceptable. - Why interviewers like it: both problems punish stopping at the first idea, and reward saying why it fails.
Order: Smallest String With Swaps, then Campus Bikes II.
Smallest String With Swaps
Core idea: The given pairs are not the only swaps you have, because swaps compose. Inside a connected component of indices, every permutation of the characters is reachable. So union the paired indices, group positions by component, sort each group's indices and sort each group's characters, and zip them together: the earliest position gets the smallest available character, which is exactly what lexicographically smallest means. Positions in no pair are singleton components and need no special case. O(n log n), dominated by the sorts.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson