Show problems as
Classic problem #1722MediumArrayDepth-First SearchUnion-Find

Minimize Hamming Distance After Swap Operations

Real-world version: Rearranging Shelf Slots Toward A Target Layout
Tracked in this browser only
Read Minimize Hamming Distance After Swap Operations on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics