HardNo. 2612
Minimum Reverse Operations — LeetCode 2612 Python Solution
- Pattern
- Union-Find
- Topics
- Breadth-First Search, Union Find, Array, Hash Table, Ordered Set
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an integer n and an integer p representing an array arr of length n where all elements are set to 0's, except position p which is set to 1. You are also given an integer array banned containing restricted positions.
Python solution
class Solution:
def minReverseOperations(
self, n: int, p: int, banned: List[int], k: int
) -> List[int]:
ans = [-1] * n
ans[p] = 0
ts = [SortedSet() for _ in range(2)]
for i in range(n):
ts[i % 2].add(i)
ts[p % 2].remove(p)
for i in banned:
ts[i % 2].remove(i)
ts[0].add(n)
ts[1].add(n)
q = deque([p])
while q:
i = q.popleft()
mi = max(i - k + 1, k - i - 1)
mx = min(i + k - 1, n * 2 - k - i - 1)
s = ts[mi % 2]
j = s.bisect_left(mi)
while s[j] <= mx:
q.append(s[j])
ans[s[j]] = ans[i] + 1
s.remove(s[j])
j = s.bisect_left(mi)
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2612. Minimum Reverse 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 |
|---|---|---|
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0959 | Regions Cut By Slashes | Medium |
| 1202 | Smallest String With Swaps | Medium |
Frequently asked questions
- How hard is LeetCode 2612. Minimum Reverse Operations?
LeetCode 2612. Minimum Reverse Operations is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2612. Minimum Reverse Operations?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2612. Minimum Reverse Operations?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2612. Minimum Reverse Operations cover?
LeetCode 2612. Minimum Reverse Operations is tagged Breadth-First Search, Union Find, Array, Hash Table and Ordered Set on LeetCode.