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 \times \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.

Minimum Reverse Operations — LeetCode 2612 Python Solution

HardBreadth-First SearchUnion FindArrayHash TableOrdered Set

Problem: #2612
Pattern: Union-Find
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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

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.

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 \times \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.