</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Connected Components

What is this?

A component is a set of things that can all reach each other and nothing outside. Finding them is the easy part: a flood fill from every unvisited node. What makes these problems interesting is what you do with the components once you have them: count the pairs they cannot form, decide which are safe, merge them with a budget, or ask what a single change would create.

That last one is the key skill. Rather than re-flooding after every hypothetical change, label each component once and answer every hypothetical with arithmetic.

Connected components toolkit flowchart

Fun fact: Making A Large Island is the clearest example of "precompute, then answer instantly". Flipping each 0 and re-flooding is O(n⁴) on an n × n grid. Instead, label every island with a unique id and record its size in one pass; then for each 0, sum the sizes of the distinct ids around it and add one. That is O(n²), and the word "distinct" is load-bearing, because two neighbouring cells frequently belong to the same island and would otherwise be counted twice.

🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


The core idea: find the components once, record what you will need about them (size, id, whether they touch a boundary), and then answer the actual question with arithmetic instead of more traversals.


1. Counting what is not connected

Count Unreachable Pairs asks for the number of node pairs that cannot reach each other. Enumerating them is O(n²). Counting them is subtraction:

total pairs        = n(n-1)/2
pairs within a component of size s = s(s-1)/2
unreachable        = total - sum over components of s(s-1)/2

Or, walking the components once and accumulating already_seen × current_size as each is discovered. Same result, one pass, no overflow risk from the big subtraction.

2. Sealing regions that touch the edge

Number of Enclaves wants land cells that cannot walk off the grid. Rather than testing each region for an escape route, flood inward from the border first and mark everything reachable, then count what remains. The inversion, starting from the outside rather than the inside, is the same trick that makes Pacific Atlantic Water Flow tractable: flood from each ocean's edge, and the answer is the cells reached by both floods.

3. Spending a budget of edges

Number of Operations to Make Network Connected is a counting argument dressed as a graph problem. With n computers and k components, joining them all requires exactly k − 1 cables, and a cable is spare whenever an edge connects two already-connected machines. So: if edges < n − 1 it is impossible; otherwise the answer is components − 1. You never need to decide which cable to move.


4. A 30-second worked example (Making A Large Island)

Making A Large Island worked example, answer 3

And the reason "distinct" matters, on a different grid:

1 1 0        island A = {(0,0),(0,1),(1,0)}   size 3
1 0 0
0 0 0

cell (1,1): neighbours above (A) and left (A): the SAME island
            counting both gives 3 + 3 + 1 = 7  (wrong)
            counting distinct ids gives 3 + 1 = 4  (right)

5. Where you'll actually meet this

  • Network topology. Counting isolated segments and the minimum links needed to unify them is the cable problem.
  • Image processing. Connected-component labelling is a standard operation, with the same "label once, query many times" structure.
  • Geospatial analysis. Watershed and drainage modelling has the same shape as Pacific Atlantic Water Flow at real scale: start at the outlets and work inward.
  • Social graphs. Counting cross-community pairs, or the reach of a merge between two communities.
  • Game maps. Determining enclosed territory: finding regions that cannot reach the map edge is the enclaves problem.

6. Problems in this chapter

Count Unreachable Pairs of Nodes in an Undirected Graph

Count node pairs with no path between them. Find component sizes, then subtract within-component pairs from the total.
Pattern: component sizes + counting arithmetic. Target: O(V + E) time, O(V) space.

Number Of Enclaves

Count land cells that cannot reach the border. Flood inward from every border land cell, then count what was never reached.
Pattern: flood from the boundary, invert. Target: O(mn) time, O(mn) space.

Number of Operations to Make Network Connected

Minimum cable moves to connect every computer. Impossible if edges < n − 1; otherwise components − 1.
Pattern: component count + a feasibility check. Target: O(V + E) time.

Making A Large Island

Flip one 0 to 1 to make the largest island. Label and size every island in one pass, then evaluate each 0 by summing its distinct neighbouring islands.
Pattern: label once, answer by arithmetic. Target: O(mn) time, O(mn) space.

Pacific Atlantic Water Flow

Cells draining to both oceans. Flood from each ocean's border inward against the gradient, then intersect the two reachable sets.
Pattern: reverse flood from two sources. Target: O(mn) time, O(mn) space.

Flood Fill

Repaint the connected region containing a starting pixel, as a paint-bucket tool does. This is the base case of the whole chapter. Return immediately if the new colour equals the old one.
Pattern: plain flood from one source. Target: O(mn) time, O(mn) space worst case (stack or queue).


7. Common pitfalls

  • Re-flooding for every hypothetical. Label once; the whole point of Making A Large Island is avoiding the extra passes.
  • Forgetting "distinct". Two neighbouring cells often belong to the same island, and double-counting is the classic wrong answer.
  • Missing the all-ones grid. If there are no zeros to flip, the answer is the whole grid, a case that crashes solutions assuming at least one flip.
  • Flooding forward instead of from the boundary. Both the enclaves and water-flow problems become far harder if you start inside.
  • Getting the water-flow direction backwards. Flooding from the ocean means moving to cells of equal or greater height, since you are going against the flow.
  • Integer overflow on pair counts. n(n−1)/2 for n = 10⁵ exceeds 32 bits.
  • Marking visited on dequeue rather than enqueue. The same cell then enters the queue several times and the counts drift.
  • Skipping the Flood Fill guard. In Flood Fill, return at once when the new colour already equals the old one, or the fill never terminates.

8. Key takeaways

  1. Find components once, then reason about them: sizes, ids and boundary flags answer most follow-up questions without another traversal.
  2. Count the complement. Unreachable pairs are total pairs minus within-component pairs.
  3. Flood from the boundary when the question is about what cannot escape.
  4. components − 1 edges join everything, provided you have the spares.
  5. Distinct neighbours, always, when summing adjacent regions.
  6. Reverse the flow in water-flow style problems: start at the destination and go against the gradient.
  7. Why interviewers like it: the flood fill is assumed. What they are watching is whether you precompute the right facts and turn the actual question into arithmetic.

Order: Count Unreachable Pairs → Number Of Enclaves → Number of Operations to Make Network Connected → Making A Large Island → Pacific Atlantic Water Flow → Flood Fill.

Number of Enclaves LeetCode

Core idea: Invert the question. Instead of asking each land region whether it can escape, flood inward from every border land cell and count the land that was never reached. One pass over the grid answers it.

Problem, rephrased

A coastal agency is mapping which terrain would strand people in a flood. Someone standing on land can reach safety only by walking off the edge of the map, one step at a time, over adjacent land. You are given an m x n binary matrix grid, where 0 is sea and 1 is land. A move goes from a land cell to a 4-directionally adjacent land cell, or off the boundary of the grid.

Return the number of land cells from which no sequence of moves leads off the boundary. These are the landlocked cells.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.