0812HardArrayHash TableBreadth-First Search

Fewest Hops Along the Locker Row

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 row of lockers is numbered from 0 to label.length - 1, and label[i] is the code stencilled on locker i. Two lockers may carry the same code.

A porter starts at locker 0 and wants to reach the last locker. Standing at locker i, one move takes the porter to any single one of these:

locker i + 1, if that locker exists;
locker i - 1, if that locker exists;
any locker j with j != i and label[j] == label[i], however far away it is.

Return the fewest moves needed to reach the last locker. If the porter already starts there, the answer is 0.

Examples

Example 1

Input: label = [4, 9, 9, 9, 4, 8]
Output: 2

One route is locker 0 to locker 4, allowed because both are stencilled 4, and then locker 4 to locker 5. That is two moves.

Example 2

Input: label = [11, 12, 13, 14, 15]
Output: 4

No two lockers share a code, so the porter walks 0 to 1 to 2 to 3 to 4, which is four moves.

Example 3

Input: label = [5]
Output: 0

Locker 0 is already the last locker, so no move is needed.

Constraints

1 <= label.length <= 5 * 10^4
-10^8 <= label[i] <= 10^8

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 fewest_hops(label: list[int]) -> int:

Java

public int fewestHops(int[] label)

The intended approach

Time O(n): each position is queued once and each code group is scanned once overall.Space O(n) for the code groups, the visited flags and the queue.

Every move costs the same, so a breadth-first walk over locker positions gives the answer, with the positions grouped by code up front so the third kind of move is a lookup rather than a search. The one thing that has to be handled is that a code shared by many lockers would otherwise be scanned once per locker in the group: the first time a code is used, every locker carrying it is entered at that same distance, so the group list is emptied straight after and never scanned again. The walk stops as soon as the last locker is entered.

Pythonentry point: fewest_hops

def fewest_hops(label):
    # Breadth-first over locker positions. Every locker of one label is reachable
    # from every other in a single move, so the first time a label is used the
    # whole group is settled and the group list is emptied; without that emptying
    # a label shared by thousands of lockers would be rescanned thousands of
    # times.
    #
    # Time: O(n) -- each position is queued once and each label group is scanned
    # once in total. Space: O(n) for the groups and the queue.
    n = len(label)
    if n <= 1:
        return 0
    groups = {}
    for i, v in enumerate(label):
        if v in groups:
            groups[v].append(i)
        else:
            groups[v] = [i]
    seen = [False] * n
    seen[0] = True
    frontier = [0]
    moves = 0
    last = n - 1
    while frontier:
        moves += 1
        nxt = []
        for i in frontier:
            for j in (i + 1, i - 1):
                if 0 <= j < n and not seen[j]:
                    if j == last:
                        return moves
                    seen[j] = True
                    nxt.append(j)
            group = groups.get(label[i])
            if group:
                for j in group:
                    if not seen[j]:
                        if j == last:
                            return moves
                        seen[j] = True
                        nxt.append(j)
                groups[label[i]] = []
        frontier = nxt
    return -1

The obvious version

Write out every legal move as an explicit edge, including one edge per pair of lockers sharing a code, then walk the graph level by level from locker 0. The edge list is quadratic when a code repeats often, so it only suits small rows, but it encodes the move rules directly.

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_fewest_hops(label):
    """List every legal move as an edge, then walk the graph level by level."""
    n = len(label)
    groups = {}
    for i, v in enumerate(label):
        groups.setdefault(v, []).append(i)
    edges = [[] for _ in range(n)]
    for i in range(n):
        if i + 1 < n:
            edges[i].append(i + 1)
        if i - 1 >= 0:
            edges[i].append(i - 1)
        for j in groups[label[i]]:
            if j != i:
                edges[i].append(j)
    dist = [-1] * n
    dist[0] = 0
    queue = [0]
    head = 0
    while head < len(queue):
        i = queue[head]
        head += 1
        for j in edges[i]:
            if dist[j] == -1:
                dist[j] = dist[i] + 1
                queue.append(j)
    return dist[n - 1]

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 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