Maximum Connected with One Change
A hard Graph interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Graph
- Sheets
- 1
- Core for
- 12 roles
The problem
Given a list of edges in an undirected graph with n nodes, find the size of the largest connected component using Disjoint Set Union (DSU).
Example 1
- Input
- n = 5, edges = [[0,1],[1,2],[3,4]]
- Output
- 3
- Why
- Component {0,1,2} has 3 nodes, component {3,4} has 2. Largest is 3.
Example 2
- Input
- n = 4, edges = [[0,1],[2,3]]
- Output
- 2
- Why
- Two components of size 2 each.
Constraints
- 1 <= n <= 10^5
- 0 <= edges.length <= 2 * 10^5
How to think about it
Updated 2026-09-29Augment standard Disjoint Set Union with an explicit `size` array tracking component cardinality at each root. Whenever `union(u, v)` merges two distinct roots, add the size of the subordinate tree to the surviving root and update a running global maximum, tracking the largest component without post-processing scans.
Approaches, worst first
Full traversal component sizing
time O(V + E) · space O(V + E)
Build an adjacency list from all edges. Loop through all vertices 0 to n - 1 and launch a BFS or DFS traversal from each unvisited vertex to count the number of nodes in that component. While asymptotically linear, this requires building explicit adjacency structures and recursion frames.
DSU with component size trackingWrite this one
time O(V + E * α(V)) · space O(V)
Initialize `parent[i] = i` and `size[i] = 1` for each node 0 to n - 1, and `maxSize = 1`. For each edge [u, v], find roots rootU and rootV. If different, attach smaller to larger, update `size[rootU] += size[rootV]`, and update `maxSize = max(maxSize, size[rootU])`. Return `maxSize`.
Where people lose marks · 3
- If edges is empty (0 edges), each node is an isolated component of size 1; maxSize must default to 1, not 0.
- Merging two nodes that already share the same root must not increment component size.
- Updating the size of child nodes instead of root nodes causes future unions to read stale size counters.
Full solution
C++
#include <bits/stdc++.h>
using namespace std;
static int dfs(int r, int c, int tag, vector<vector<int>>& grid) {
int n = grid.size();
grid[r][c] = tag;
int count = 1;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
count += dfs(nr, nc, tag, grid);
}
}
return count;
}
int maxConnection(vector<vector<int>>& grid) {
int n = grid.size();
int island_id = 2;
unordered_map<int, int> area;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
area[island_id] = dfs(r, c, island_id, grid);
island_id++;
}
}
}
if (area.empty()) return 1;
int ans = 0;
for (const auto& p : area) ans = max(ans, p.second);
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
unordered_set<int> seen;
int total = 1;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
int tag = grid[nr][nc];
if (seen.find(tag) == seen.end()) {
seen.insert(tag);
total += area[tag];
}
}
}
ans = max(ans, total);
}
}
}
return ans;
}
Java
import java.util.*;
public class Main {
static int dfs(int r, int c, int tag, int[][] grid) {
int n = grid.length;
grid[r][c] = tag;
int count = 1;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
count += dfs(nr, nc, tag, grid);
}
}
return count;
}
static int maxConnection(int[][] grid) {
int n = grid.length;
int islandId = 2;
Map<Integer, Integer> area = new HashMap<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
area.put(islandId, dfs(r, c, islandId, grid));
islandId++;
}
}
}
if (area.isEmpty()) return 1;
int ans = 0;
for (int v : area.values()) ans = Math.max(ans, v);
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
Set<Integer> seen = new HashSet<>();
int total = 1;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
int tag = grid[nr][nc];
if (!seen.contains(tag)) {
seen.add(tag);
total += area.get(tag);
}
}
}
ans = Math.max(ans, total);
}
}
}
return ans;
}
}
Python
def max_connection(grid):
n = len(grid)
island_id = 2
area = {}
def dfs(r, c, tag):
count = 1
grid[r][c] = tag
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
count += dfs(nr, nc, tag)
return count
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
area[island_id] = dfs(r, c, island_id)
island_id += 1
if not area:
return 1
ans = max(area.values())
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
seen = set()
total = 1
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] > 1:
tag = grid[nr][nc]
if tag not in seen:
seen.add(tag)
total += area[tag]
ans = max(ans, total)
return ans
JavaScript
function maxConnection(grid) {
const n = grid.length;
const area = new Map();
let tag = 2;
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
let size = 0;
const queue = [[r, c]];
grid[r][c] = tag;
let head = 0;
while (head < queue.length) {
const [cr, cc] = queue[head++];
size++;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 1) {
grid[nr][nc] = tag;
queue.push([nr, nc]);
}
}
}
area.set(tag, size);
tag++;
}
}
}
if (area.size === 0) return 1;
let ans = 0;
for (const s of area.values()) ans = Math.max(ans, s);
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 0) {
const neighbors = new Set();
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
neighbors.add(grid[nr][nc]);
}
}
let total = 1;
for (const t of neighbors) {
total += area.get(t);
}
ans = Math.max(ans, total);
}
}
}
return ans;
}
The theory behind it
Graph — the ground this problem stands on. All Graph problems
What Graph is
A graph is a network of individual points, called vertices or nodes, connected by lines called edges. Think of a subway transit map, an electrical circuit, or a web of social friends. Unlike a tree, a graph has no designated top node and no parent-child hierarchy. Connections can run one-way or both ways, and paths can loop back on themselves to form closed cycles.
When to reach for it
Reach for graph algorithms when inputs describe relationships, networks, flights between cities, course prerequisites, or clone networks. Signals include finding the shortest route across unweighted connections, ordering tasks that depend on earlier tasks, counting isolated clusters, or checking whether a path contains an infinite loop. Whenever problems present pairs of related entities and ask for reachability, distances, or dependencies, graph representations apply.
How the pattern works
First convert edge lists into an adjacency list, mapping each node to an array of its neighbors. Choose your exploration strategy based on the goal: use a queue and breadth-first search to find the shortest path in unweighted networks, or use recursion and depth-first search to explore full paths and detect cycles. Because graphs can have loops, always track visited nodes in a set or boolean array. Add nodes to the visited set at the moment they enter the queue so they are never visited twice.
More Graph problems
Target Roles
Core requirement for 12 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .