MediumNo. 1722
Minimize Hamming Distance After Swap Operations — LeetCode 1722 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Union Find, Array
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source.
Example
- Input
- source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
- Output
- 1
- Explanation
- source can be transformed the following way:
Python solution
class Solution:
def minimumHammingDistance(
self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(source)
p = list(range(n))
for a, b in allowedSwaps:
p[find(a)] = find(b)
cnt = defaultdict(Counter)
for i, x in enumerate(source):
j = find(i)
cnt[j][x] += 1
ans = 0
for i, x in enumerate(target):
j = find(i)
cnt[j][x] -= 1
ans += cnt[j][x] < 0
return ansComplexity
- Time
- O(n × log n) or O(n × α(n))
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1722. Minimize Hamming Distance After Swap Operations is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0695 | Max Area of Island | Medium |
| 0827 | Making A Large Island | Hard |
| 1020 | Number of Enclaves | Medium |
| 1254 | Number of Closed Islands | Medium |
Frequently asked questions
- How hard is LeetCode 1722. Minimize Hamming Distance After Swap Operations?
LeetCode 1722. Minimize Hamming Distance After Swap Operations is rated Medium on LeetCode.
- What topics does LeetCode 1722. Minimize Hamming Distance After Swap Operations cover?
LeetCode 1722. Minimize Hamming Distance After Swap Operations is tagged Depth-First Search, Union Find and Array on LeetCode.