Minimum Time to Stabilize Network :
- Posted
- 24 Mar 2026
Summary
This post describes a graph problem focused on determining the minimum time to stabilize a network of computers given initial unstable nodes and a stability threshold. It details the rules for how instability propagates and how computers regain stability.
How it went
You are given a network of n computers connected by m bidirectional cables. Each cable has a latency weight.
Some computers are initially unstable. Every second:
An unstable computer makes all directly connected computers unstable.
However, if a computer has at least k stable neighbors, it becomes stable again (even if it was unstable).
Your task is to determine the minimum number of seconds required for the entire network to become stable, or return -1 if it is impossible.
Input
n → number of nodes (1 ≤ n ≤ 10^5)
edges → list of [u, v, w] connections
unstable → list of initially unstable nodes
k → stability threshold
Output
Minimum time for all nodes to become stable, or -1
Example:
n = 5
edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1]]
unstable = [0]
k = 2
Output:
3
Questions asked (1)
- 01
Minimum Time to Stabilize Network
Data Structures & Algorithms · Hard
You are given a network of n computers connected by m bidirectional cables. Each cable has a latency weight.
Some computers are initially unstable. Every second:
An unstable computer makes all directly connected computers unstable.
However, if a computer has at least k stable neighbors, it becomes stable again (even if it was unstable).
Your task is to determine the minimum number of seconds required for the entire network to become stable, or return -1 if it is impossible.
Input
n → number of nodes (1 ≤ n ≤ 10^5)
edges → list of [u, v, w] connections
unstable → list of initially unstable nodes
k → stability threshold
Output
Minimum time for all nodes to become stable, or -1
Example:
n = 5
edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1]]
unstable = [0]
k = 2
Output:
3