Solve island connectivity and string multiplication
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given N distinct islands (e.g., a, b, c…) and a list of existing undirected paths between them, compute the minimum number of additional paths required so that all islands become connected. LeetCode 43. Multiply Strings – Given two non-negative integers represented as strings, return their product as a string. (Clarify whether the carry can exceed 10.)
https://leetcode.com/problems/multiply-strings/description/
Quick Answer: This question evaluates graph connectivity reasoning (computing minimum edges to unify components) and string-based big-integer arithmetic (multiplying numbers represented as strings), testing competency in graph theory, component analysis, and numeric string manipulation.
You are given n islands labeled from 0 to n-1 and a list of existing undirected paths (connections) between them. Each connection is a pair [u, v] with 0 <= u, v < n and u != v. Determine the minimum number of additional paths needed to make all islands belong to a single connected component. You may add a path between any two distinct islands.
Constraints
- 1 <= n <= 200000
- 0 <= len(connections) <= 200000
- connections[i] = [u, v], where 0 <= u, v < n and u != v
- Islands are distinct and labeled 0 to n-1
- Multiple or duplicate connections may be present and should be treated as a single connection for connectivity
Solution
def min_additional_paths(n: int, connections: list[list[int]]) -> int:
# Union-Find (Disjoint Set Union) implementation
parent = list(range(n))
rank = [0] * n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression (halving)
x = parent[x]
return x
def union(a: int, b: int) -> bool:
ra, rb = find(a), find(b)
if ra == rb:
return False
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True
# Merge sets for each connection
for u, v in connections:
# Assuming inputs are valid per constraints; ignore self-loops if any
if u != v:
union(u, v)
# Count unique roots (connected components)
roots = set(find(i) for i in range(n))
components = len(roots)
# Minimum additional edges to connect all components is components - 1
return components - 1
Explanation
We treat islands as nodes in an undirected graph. Using Union-Find, we merge endpoints of each existing path to form connected components. The minimum number of edges required to connect k components into a single component is k - 1, since each new edge can join two components. Thus, after counting components via Union-Find, we return components - 1.
Time complexity: O(n + m) where m = len(connections). Space complexity: O(n).
Hints
- The minimum number of additional paths required equals the number of connected components minus one.
- Use DFS/BFS or Union-Find (Disjoint Set Union) to count connected components efficiently.
- Be careful to handle duplicate connections without affecting the component count.