Keys and Rooms
Real-world version: Depot Locker KeysThe statement here is our own: the same inputs, outputs and technique.
A depot has n numbered lockers, 0 through n - 1. Every locker is bolted shut except locker 0, which the night clerk leaves open.
Inside each locker hangs a ring of keys. lockers[i] lists the numbers of the lockers that the keys inside locker i open. A locker's ring never lists the same locker twice, though it may list a locker that is already open, and it may even list itself. Once you can open a locker you can take everything on its ring and keep going.
Starting from the open locker 0, return true if every locker in the depot can be opened, and false otherwise.
Examples
Example 1
- Input
- lockers = [[2], [], [1, 3], []]
- Output
- true
Locker 0 is open and holds the key to locker 2. Locker 2 holds keys to lockers 1 and 3, so all four end up open.
Example 2
- Input
- lockers = [[2], [3], [1], []]
- Output
- true
Locker 0 gives locker 2, locker 2 gives locker 1, and locker 1 gives locker 3.
Example 3
- Input
- lockers = [[1], [0], [3], [2]]
- Output
- false
Lockers 0 and 1 only hold each other's keys, so lockers 2 and 3 stay shut even though their numbers do appear on rings elsewhere in the depot.
Example 4
- Input
- lockers = [[0, 2], [], [1]]
- Output
- true
Locker 0's ring lists itself, which changes nothing, and its other key opens locker 2, whose ring opens locker 1.
Example 5
- Input
- lockers = [[], [0], [0]]
- Output
- false
The open locker holds no keys at all, so lockers 1 and 2 can never be opened.
Constraints
- n == lockers.length
- 2 <= n <= 1000
- 0 <= lockers[i].length <= 1000
- 1 <= sum(lockers[i].length) <= 3000
- 0 <= lockers[i][j] < n
- The values inside one lockers[i] are all different.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def can_open_all_lockers(lockers: list[list[int]]) -> bool:public boolean canOpenAllLockers(List<List<Integer>> lockers)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's