2612. Minimum Reverse Operations

Description

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. Perform the following operation on arr:

• Reverse a with size k if the single 1 is not set to a position in banned.

Return an integer array answer with n results where the ith result isthe minimum number of operations needed to bring the single 1 to position i in arr, or -1 if it is impossible.

 

Example 1:

Input: n = 4, p = 0, banned = [1,2], k = 4

Output: [0,-1,-1,1]

Explanation:

• Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
• We can never place 1 on the banned positions, so the answer for positions 1 and 2 is -1.
• Perform the operation of size 4 to reverse the whole array.
• After a single operation 1 is at position 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:

• Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
• We cannot perform the operation on the subarray positions [0, 2] because position 2 is in banned.
• Because 1 cannot be set at position 2, it is impossible to set 1 at other positions in more operations.

Example 3:

Input: n = 4, p = 2, banned = [0,1,3], k = 1

Output: [-1,-1,0,-1]

Explanation:

Perform operations of size 1 and 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 

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @param {number} p
 * @param {number[]} banned
 * @param {number} k
 * @return {number[]}
 */
const minReverseOperations = function (n, p, banned, k) {
  const distances = Array.from({ length: n }, () => -1);
  const jumpDist = k - 1;

  for (const pos of banned) {
    distances[pos] = -2;
  }

  let queue = [p];

  distances[p] = 0;

  while (queue.length) {
    const nextQueue = [];
    const nextDist = distances[queue[0]] + 1;
    let minCovered = -1;
    let maxCovered = -1;

    for (const pos of queue) {
      let low = pos - jumpDist;
      let high = pos + jumpDist;

      if (low < 0) {
        low = jumpDist - pos;
      }

      if (high >= n) {
        high = 2 * (n - 1) - pos - jumpDist;
      }

      let index = low;

      while (index <= high) {
        if (index >= minCovered && index <= maxCovered) {
          index = maxCovered;
        } else if (distances[index] === -1) {
          distances[index] = nextDist;
          nextQueue.push(index);
        }

        index += 2;
      }

      if (high < minCovered || low > maxCovered) {
        minCovered = low;
        maxCovered = high;
      } else {
        minCovered = Math.min(low, minCovered);
        maxCovered = Math.max(high, maxCovered);
      }
    }

    queue = nextQueue.toSorted((a, b) => a - b);
  }

  return distances.map(dist => Math.max(dist, -1));
};