0744MediumArrayDepth-First SearchUnion-Find

Rearranging Shelf Slots Toward A Target Layout

Tracked in this browser only

Trains the technique from

LeetCode 1722Minimize Hamming Distance After Swap Operations

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 storage wall has n slots numbered 0 to n - 1. current[i] is the part number sitting in slot i today and wanted[i] is the part number the new layout asks for in slot i.

The wall's rails only let certain slots exchange contents. swaps lists those rails: swaps[k] = [a, b] means the contents of slot a and slot b may be exchanged, and a rail may be used as many times as you like, in any order, including rails that share a slot. Rails may be listed more than once.

A slot is wrong when the part number it holds is not the part number the new layout asks for in that slot. Perform any number of exchanges along the rails and return the smallest number of wrong slots you can end up with.

Examples

Example 1

Input: current = [1, 2, 3], wanted = [3, 2, 1], swaps = [[0, 1], [1, 2]]
Output: 0

Exchange slots 1 and 2 to reach `[1, 3, 2]`, then slots 0 and 1 to reach `[3, 1, 2]`, then slots 1 and 2 again to reach `[3, 2, 1]`. Every slot now holds the part number the new layout asks for.

Example 2

Input: current = [7, 9, 8, 10], wanted = [8, 7, 10, 9], swaps = [[0, 1], [2, 3]]
Output: 2

Exchanging slots 0 and 1 gives `[9, 7, 8, 10]`, so slot 1 is right. Exchanging slots 2 and 3 gives `[9, 7, 10, 8]`, so slot 2 is right as well. Slots 0 and 3 are still wrong, which is two wrong slots.

Example 3

Input: current = [4, 4, 6], wanted = [4, 4, 9], swaps = [[0, 1], [1, 2]]
Output: 1

The two rails let the three part numbers 4, 4 and 6 be arranged across the three slots in any order. Leaving them where they are makes slots 0 and 1 right, with slot 2 holding 6 while the layout asks for 9, which is one wrong slot.

Constraints

current.length == wanted.length
1 <= current.length <= 10^5
1 <= current[i], wanted[i] <= 10^5
0 <= swaps.length <= 10^5
swaps[k].length == 2
0 <= swaps[k][j] <= 10^5 - 1
Each rail names two different slots that both exist.

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_wrong_slots(current: list[int], wanted: list[int], swaps: list[list[int]]) -> int:

Java

public int fewestWrongSlots(int[] current, int[] wanted, int[][] swaps)

The intended approach

Time O(n + m) for n slots and m rails, up to the near-constant disjoint-set factor.Space O(n) for the forest and the per-group tallies.

Rails make slot membership transitive: if `a` can trade with `b` and `b` with `c`, repeated exchanges move any part between all three, so the slots split into groups inside which the parts can be arranged in any order at all. Build those groups in a disjoint-set forest over the slot indices, with path halving in the lookup. Then tally, per group, how many of each part number the group currently holds and how many the new layout asks for. A group can satisfy `min(held, asked)` slots for each part number, so summing that minimum over all part numbers of all groups counts the slots that can be made right, and the answer is `n` minus that total. Nothing recurses, so a wall of 10^5 slots is safe.

Pythonentry point: fewest_wrong_slots

def fewest_wrong_slots(current, wanted, swaps):
    # Slots joined by swap pairs form groups whose contents can be permuted
    # freely, so within a group only the multiset of values matters.
    # O(n + m) time up to the disjoint-set factor, O(n) space.
    n = len(current)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for a, b in swaps:
        ra, rb = find(a), find(b)
        if ra != rb:
            root[ra] = rb

    have = {}
    need = {}
    for i in range(n):
        g = find(i)
        h = have.setdefault(g, {})
        h[current[i]] = h.get(current[i], 0) + 1
        d = need.setdefault(g, {})
        d[wanted[i]] = d.get(wanted[i], 0) + 1

    matched = 0
    for g, h in have.items():
        d = need[g]
        for val, cnt in h.items():
            other = d.get(val, 0)
            matched += cnt if cnt < other else other
    return n - matched

The obvious version

Build an adjacency list from the rails and collect each group with a breadth-first walk driven by an explicit queue. For each group, put the held part numbers in a plain list and, slot by slot, search that list for the asked part number and remove it, counting a wrong slot when the search fails. No tallies and no disjoint-set forest.

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_wrong_slots(current, wanted, swaps):
    """Group the slots with a breadth-first walk over an adjacency list, then for
    each group hand out values by searching and removing them from a plain list."""
    n = len(current)
    adj = [[] for _ in range(n)]
    for a, b in swaps:
        adj[a].append(b)
        adj[b].append(a)

    seen = [False] * n
    wrong = 0
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        queue = [s]
        head = 0
        members = []
        while head < len(queue):
            node = queue[head]
            head += 1
            members.append(node)
            for nb in adj[node]:
                if not seen[nb]:
                    seen[nb] = True
                    queue.append(nb)
        pool = [current[i] for i in members]
        for i in members:
            v = wanted[i]
            if v in pool:
                pool.remove(v)
            else:
                wrong += 1
    return wrong

How this problem was checked

Reference solution executed against 14 test cases — 14 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