Leetcode 2612: Minimum Reverse Operations

You are given an integer n and an integer p in the range [0, n - 1]. Representing a 0-indexed array arr of length n where all positions are set to 0's, except position p which is set to 1.

You are also given an integer array banned containing some positions from the array. For the ith position in banned, arr[banned[i]] = 0, and banned[i] != p.

You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.

Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.

• A subarray is a contiguous non-empty sequence of elements within an array.
• The values of ans[i] are independent for all i's.
• The reverse of an array is an array containing the values in reverse order.

Example 1:

Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,-1,-1,1]
Explanation: In this case k = 4 so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is 0. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is -1. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is 1.

Example 2:

Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation: In this case the 1 is initially at position 0, so the answer for that position is 0. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray [0, 2] for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions -1.

Example 3:

Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [-1,-1,0,-1]
Explanation: In this case we can only perform reverse operations of size 1. So the 1 never changes its position.

Constraints:

• 1 <= n <= 105
• 0 <= p <= n - 1
• 0 <= banned.length <= n - 1
• 0 <= banned[i] <= n - 1
• 1 <= k <= n
• banned[i] != p
• all values in banned are unique

Problem Analysis:

We use some examples to describe the reverse action. Suppose we have an array with index 0, 1, …, 9, p = 4, k = 4, so the first time we can reverse subarray 1…4, 2…5, 3…6, 4…7, and then the position in index 1, 3, 5, 7 can set to 1.

If we change k = 3, then the first time we can reverse subarray 2…4, 3…5, 4…6, and then the position in index 2, 6 can set to 1.

So we find the rule, every time we can get reverse index which is 2 diffs in neighbor index. If k is odd, then we can get most k-1 positions, if k is even, we can get most k positions.

So we iterate with this operation, we can finally get the answer.

Solution

class Solution {
public:
  vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
    unordered_set<int> bans{banned.begin(), banned.end()};
    vector<int> res(n, -1);
    set<int> data[2];
    res[p] = 0;
    for (int i = 0; i < n; ++i) {
      if (i != p && bans.count(i) == 0)
        data[i & 1].insert(i);
    }

    queue<int> q;
    q.push(p);
    while (!q.empty()) {
      int pivot = q.front();
      q.pop();
      auto range = getRange(n, pivot, k);
      int index = (k % 2) ? (pivot & 1) : (1 - pivot & 1);
      auto it1 = data[index].lower_bound(range.first);
      auto it2 = data[index].upper_bound(range.second);
      for (auto it = it1; it != it2; ++it) {
        res[*it] = res[pivot] + 1;
        q.push(*it);
      }

      data[index].erase(it1, it2);
    }

    return res;
  }
private:
  pair<int, int> getRange(int n, int pivot, int k) {
    int l1 = max(0, pivot - k + 1);
    int r1 = l1 + k - 1;

    int r2 = min(n - 1, pivot + k - 1);
    int l2 = r2 - k + 1;
    
    int left = r1 - (pivot - l1);
    int right = l2 + (r2 - pivot);

    return {left, right};
  }
};

Time complexity is O(nlgn)

Space complexity is O(n)