</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Graph Coloring

What is this?

"Colouring" here means the plain version: give every node a component id, then answer questions about the components rather than about the nodes. Minimize Malware Spread is the archetype: a network, a set of initially infected nodes, and the question of which single one to disinfect. The graph work is a routine flood fill, and the reasoning after it is what the problem is for.

Graph colouring decision flow for minimizing malware spread

Fun fact: the trap in Minimize Malware Spread is that removing an infected node usually accomplishes nothing. If its component holds another infected node, the malware reaches every node there anyway and the final count is unchanged. Only a component with exactly one infected node can be saved. That filter decides the answer, and a solution that simulates the spread once per candidate is slower and easier to get wrong on the tie-break.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.


Core idea: colour the components, then count. A node is only worth removing if it is the sole infection in its component, and among those the best is the one guarding the most nodes.


1. Colour, then count

colour = [-1] * n
for start in range(n):
    if colour[start] == -1:
        stack = [start]
        while stack:
            u = stack.pop()
            if colour[u] != -1: continue
            colour[u] = start                        # the first node found is the id
            stack += [v for v in range(n) if graph[u][v] and colour[v] == -1]

size = Counter(colour)                               # nodes per component
infected = Counter(colour[u] for u in initial)       # infected per component

Two counters and the rest is arithmetic. The adjacency matrix makes the traversal O(n²), which is fine at n ≤ 300 and worth naming out loud. With an adjacency list it would be O(n + e).

2. The decision

best, best_saved = min(initial), 0
for u in sorted(initial):                            # ascending → ties resolve themselves
    if infected[colour[u]] == 1 and size[colour[u]] > best_saved:
        best, best_saved = u, size[colour[u]]
return best

Two details carry the whole answer. The == 1 filter is the insight: a component with two or more infected nodes is doomed regardless. Ascending iteration with a strict > implements "smallest index on a tie" without a special case. The initial min(initial) covers the case where no component qualifies: every removal is equally useless, so the smallest index wins by default.


3. A 30-second worked example

graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1, 2]

Minimize malware spread worked example, answer node 1

Removing node 1 leaves node 2 to infect everything; removing node 2 leaves node 1 to do the same. Both end with all three infected, so the answer is decided purely by the tie-break. The fallback is part of the specification, not an edge case to bolt on afterwards.


4. Where you'll actually meet this

  • Network security. Isolating a compromised host only helps if it is the only compromise in its segment.
  • Rumour and misinformation containment. Removing one source matters only when it is the sole source in its cluster.
  • Failure-domain analysis. Component size is blast radius, and the counting argument is the same.

5. Problems in this chapter

Minimize Malware Spread

Remove one initially infected node to minimise the final infected count. Approach 1 simulates every removal; Approach 2 colours the components, keeps only those with exactly one infection, and picks the largest.
Pattern: component colouring + counting argument. Target: O(n²) time on an adjacency matrix, O(n) space.


6. Common pitfalls

  • Removing any infected node and hoping. Only a component with exactly one infection can be saved.
  • Simulating the spread once per candidate. Correct but O(k·n²) for k infected nodes, which is O(n³) in the worst case, and it still needs the tie-break handled explicitly.
  • Forgetting the fallback. When no component qualifies the answer is the smallest index in initial, not -1 and not nothing.
  • Getting the tie-break backwards. Iterate ascending and use a strict >; the first best index then wins for free.
  • Confusing size with saved count. What you save is the whole component, not the number of infections in it.
  • Assuming the removed node stays clean. It is only removed from the initial set; it can still be infected by neighbours.
  • Reading the diagonal as edges. graph[i][i] is 1 by definition and is not a real connection.

7. Key takeaways

  1. Colour the components first, then treat the question as counting.
  2. Exactly one infection per component is the filter the answer turns on.
  3. The saving is the component's size, not the number of infections in it.
  4. Ascending iteration plus a strict comparison implements the tie-break with no extra code.
  5. Handle "nothing qualifies" as part of the spec. It is a common input, not an afterthought.
  6. Name the representation's cost. O(n²) here comes from the matrix, not from the algorithm.
  7. Why interviewers like it: the traversal is trivial, so all the signal is in whether you reason about what a removal actually changes.

Order: Minimize Malware Spread.

Minimize Malware Spread

Core idea: Give every node its component id, then count two things per component: its size and how many initially infected nodes it holds. Removing an infected node only helps when it is the sole infection in its component. Otherwise the malware still floods the component and the final count does not change. So keep the components with exactly one infection and pick the largest. Walk the candidates in ascending order with a strict > and the "smallest index on a tie" rule needs no special case. Start the answer at min(initial) so the case where nothing qualifies uses the same code. O(n²) on the adjacency matrix.

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.