Skip to content

3762. Minimum Operations to Equalize Subarrays

Description

You are given an integer array nums and an integer k.

In one operation, you can increase or decrease any element of nums by exactly k.

You are also given a 2D integer array queries, where each queries[i] = [li, ri].

For each query, find the minimum number of operations required to make all elements in the subarray nums[li..ri] equal. If it is impossible, the answer for that query is -1.

Return an array ans, where ans[i] is the answer for the ith query.

 

Example 1:

Input: nums = [1,4,7], k = 3, queries = [[0,1],[0,2]]

Output: [1,2]

Explanation:

One optimal set of operations:

i [li, ri] nums[li..ri] Possibility Operations Final
nums[li..ri]		 ans[i]
0 [0, 1] [1, 4] Yes nums[0] + k = 1 + 3 = 4 = nums[1] [4, 4] 1
1 [0, 2] [1, 4, 7] Yes nums[0] + k = 1 + 3 = 4 = nums[1]
nums[2] - k = 7 - 3 = 4 = nums[1]		 [4, 4, 4] 2

Thus, ans = [1, 2].

Example 2:

Input: nums = [1,2,4], k = 2, queries = [[0,2],[0,0],[1,2]]

Output: [-1,0,1]

Explanation:

One optimal set of operations:

i [li, ri] nums[li..ri] Possibility Operations Final
nums[li..ri]		 ans[i]
0 [0, 2] [1, 2, 4] No - [1, 2, 4] -1
1 [0, 0] [1] Yes Already equal [1] 0
2 [1, 2] [2, 4] Yes nums[1] + k = 2 + 2 = 4 = nums[2] [4, 4] 1

Thus, ans = [-1, 0, 1].

 

Constraints:

  • 1 <= n == nums.length <= 4 × 104
  • 1 <= nums[i] <= 109​​​​​​​
  • 1 <= k <= 109
  • 1 <= queries.length <= 4 × 104
  • ​​​​​​​queries[i] = [li, ri]
  • 0 <= li <= ri <= n - 1

Solutions

Solution 1

Thinking

Adding or subtracting \(k\) can equalize a range iff every value shares the same residue modulo \(k\); the cheapest target is a median. With many queries we group indices by residue, then answer each range with prefix sums on the sorted values of that group.

1


1


1


1

Comments