Checkpoint Certainty Map
Nodes where every path eventually reaches a target in a directed graph
An online game's dungeon contains n rooms numbered from 0 to n - 1. Each entry [a, b] in portals is a one-way portal from room a to room b.
Some rooms are listed in checkpoints. A run succeeds immediately upon entering a checkpoint, even if that room has outgoing portals. Starting in a checkpoint also succeeds immediately.
In any other room, the player must choose one of its outgoing portals. If there are no outgoing portals, the run fails. The player may choose portals arbitrarily, including repeatedly following a cycle forever; such an infinite run does not succeed.
A room is certain if every possible run starting there reaches a checkpoint after finitely many portal moves.
Return the IDs of all certain rooms in increasing order. Portals may lead back to the same room, and repeated portal entries are allowed.
Examples
Example 1
Input: n = 5, portals = [[0,1],[0,2],[1,4],[2,4],[3,3]], checkpoints = [4] Output: [0,1,2,4]
Room 4 is a checkpoint. Rooms 1 and 2 both lead directly to it, and either choice from room 0 leads through one of those rooms. Those rooms are certain. Room 3 can keep using its self-loop forever, so it is not certain.
Example 2
Input: n = 4, portals = [[0,1],[0,3],[1,2],[2,0]], checkpoints = [2] Output: [1,2]
Room 2 is a checkpoint, so its outgoing portal is irrelevant. Room 1 always reaches it. Room 0 can instead enter room 3, which has no outgoing portals and is not a checkpoint, so room 0 is not certain.
Example 3
Input: n = 3, portals = [[0,1],[1,0]], checkpoints = [] Output: []
There are no checkpoints. Rooms 0 and 1 can cycle forever, while room 2 is a non-checkpoint dead end. No starting room guarantees success.
Constraints
- 1 <= n <= 100000
- 0 <= portals.length <= 3000
- Each portals entry contains exactly two integers in the range [0, n - 1].
- 0 <= checkpoints.length <= min(n, 1000)
- The room IDs in checkpoints are distinct.
- Self-loops and repeated portal entries are allowed.
The reference solutions use O(n + portals.length) time and space. Checkpoints are absorbing: their outgoing portals do not affect their status. Repeated portals are counted and removed separately.
Hints
Show hint 1Hint 1
Begin with the checkpoints, whose success is already known. When can another room be declared certain?
Show hint 2Hint 2
Store incoming portals and count each room's outgoing portals whose destinations have not yet been declared certain. A non-checkpoint dead end must not be accepted merely because its initial count is zero.
Follow-up questions
What an interviewer might ask once you have a working solution.
- For each certain room, also compute the maximum number of moves an adversarial player can take before reaching a checkpoint.
- For every room that is not certain, how could you produce a witness route leading to a non-checkpoint dead end or to a cycle?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem