Vault Key Chain
MediumGraphs
Problem
A bank basement has n vaults numbered 0 to n - 1. Vault 0 is open; all others are locked. vaults[i] lists the vault numbers of the keys stored inside vault i (keys may repeat).
You may open any vault for which you hold a key, and take every key inside. Return the number of vaults that remain locked once you can open nothing more.
Example 1
- Input:
- vaults = [[1],[2],[3],[]]
- Output:
- 0
Vault 0 holds the key to 1, which holds the key to 2, which holds the key to 3.
Example 2
- Input:
- vaults = [[1,3],[3,0,1],[2],[0]]
- Output:
- 1
The only key to vault 2 is locked inside vault 2 itself.
Constraints
- 1 ≤ n ≤ 10^4
- Total number of keys ≤ 3 · 10^4
- 0 ≤ vaults[i][j] < n
Hint
Show the first hint
Think of each vault as a node and each key as a directed edge to the vault it opens.
Walkthrough
How to approach it
01Clarify before coding
- Are keys reusable? Yes, opening a vault never consumes anything; holding one key is enough.
- Do the edges go one way? Yes: a key inside i opens j, not the other way round.
- Can a vault contain its own key or duplicates? Yes; they change nothing.
02Brute force
Hold a set of keys; repeatedly scan all vaults, open any whose key you hold and add its keys, until a full pass opens nothing new.
Cost: Each pass costs O(n + K) and a chain of vaults can need n passes: O(n · (n + K)).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.