0311MediumDepth-First SearchBreadth-First SearchGraph Theory

Depot Locker Keys

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_open_all_lockers(lockers: list[list[int]]) -> bool:

Java

public boolean canOpenAllLockers(List<List<Integer>> lockers)

The intended approach

Time O(n + K), where K is the total number of keysSpace O(n)

Treat each key as a directed step from the locker holding it to the locker it opens and walk outward from locker 0. Keep a flag per locker so each one is expanded at most once, push newly opened lockers onto an explicit stack, and count how many were opened. The depot is fully accessible exactly when that count reaches `n`.

Pythonentry point: can_open_all_lockers

def can_open_all_lockers(lockers):
    # O(n + K) time, where K is the total number of keys across all lockers:
    # each locker is expanded once and each key is read once.
    # O(n) space for the opened flags and the explicit stack.
    n = len(lockers)
    opened = [False] * n
    opened[0] = True
    count = 1
    stack = [0]
    while stack:
        cur = stack.pop()
        for key in lockers[cur]:
            if not opened[key]:
                opened[key] = True
                count += 1
                stack.append(key)
    return count == n

The obvious version

Keep a set of openable lockers and sweep the whole set again and again, adding any key found, until a full sweep adds nothing new.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_open_all_lockers(lockers):
    have = set([0])
    growing = True
    while growing:
        growing = False
        for i in sorted(have):
            for key in lockers[i]:
                if key not in have:
                    have.add(key)
                    growing = True
    return len(have) == len(lockers)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in