3762. Minimum Operations to Equalize Subarrays Hard
1/**
2 * [3762] Minimum Operations to Equalize Subarrays
3 *
4 * You are given an integer array nums and an integer k.
5 * In one operation, you can increase or decrease any element of nums by exactly k.
6 * You are also given a 2D integer array queries, where each queries[i] = [li, ri].
7 * For each query, find the minimum number of operations required to make all elements in the <span data-keyword="subarray-nonempty">subarray</span> nums[li..ri] equal. If it is impossible, the answer for that query is -1.
8 * Return an array ans, where ans[i] is the answer for the i^th query.
9 *
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [1,4,7], k = 3, queries = [[0,1],[0,2]]</span>
13 * Output: <span class="example-io">[1,2]</span>
14 * Explanation:
15 * One optimal set of operations:
16 * <table style="border: 1px solid black;">
17 * <tbody>
18 * <tr>
19 * <th style="border: 1px solid black;">i</th>
20 * <th style="border: 1px solid black;">[li, ri]</th>
21 * <th style="border: 1px solid black;">nums[li..ri]</th>
22 * <th style="border: 1px solid black;">Possibility</th>
23 * <th style="border: 1px solid black;">Operations</th>
24 * <th style="border: 1px solid black;">Final<br />
25 * nums[li..ri]</th>
26 * <th style="border: 1px solid black;">ans[i]</th>
27 * </tr>
28 * </tbody>
29 * <tbody>
30 * <tr>
31 * <td style="border: 1px solid black;">0</td>
32 * <td style="border: 1px solid black;">[0, 1]</td>
33 * <td style="border: 1px solid black;">[1, 4]</td>
34 * <td style="border: 1px solid black;">Yes</td>
35 * <td style="border: 1px solid black;">nums[0] + k = 1 + 3 = 4 = nums[1]</td>
36 * <td style="border: 1px solid black;">[4, 4]</td>
37 * <td style="border: 1px solid black;">1</td>
38 * </tr>
39 * <tr>
40 * <td style="border: 1px solid black;">1</td>
41 * <td style="border: 1px solid black;">[0, 2]</td>
42 * <td style="border: 1px solid black;">[1, 4, 7]</td>
43 * <td style="border: 1px solid black;">Yes</td>
44 * <td style="border: 1px solid black;">nums[0] + k = 1 + 3 = 4 = nums[1]<br />
45 * nums[2] - k = 7 - 3 = 4 = nums[1]</td>
46 * <td style="border: 1px solid black;">[4, 4, 4]</td>
47 * <td style="border: 1px solid black;">2</td>
48 * </tr>
49 * </tbody>
50 * </table>
51 * Thus, ans = [1, 2].
52 * </div>
53 * <strong class="example">Example 2:
54 * <div class="example-block">
55 * Input: <span class="example-io">nums = [1,2,4], k = 2, queries = [[0,2],[0,0],[1,2]]</span>
56 * Output: <span class="example-io">[-1,0,1]</span>
57 * Explanation:
58 * One optimal set of operations:
59 * <table style="border: 1px solid black;">
60 * <tbody>
61 * <tr>
62 * <th style="border: 1px solid black;">i</th>
63 * <th style="border: 1px solid black;">[li, ri]</th>
64 * <th style="border: 1px solid black;">nums[li..ri]</th>
65 * <th style="border: 1px solid black;">Possibility</th>
66 * <th style="border: 1px solid black;">Operations</th>
67 * <th style="border: 1px solid black;">Final<br />
68 * nums[li..ri]</th>
69 * <th style="border: 1px solid black;">ans[i]</th>
70 * </tr>
71 * <tr>
72 * <td style="border: 1px solid black;">0</td>
73 * <td style="border: 1px solid black;">[0, 2]</td>
74 * <td style="border: 1px solid black;">[1, 2, 4]</td>
75 * <td style="border: 1px solid black;">No</td>
76 * <td style="border: 1px solid black;">-</td>
77 * <td style="border: 1px solid black;">[1, 2, 4]</td>
78 * <td style="border: 1px solid black;">-1</td>
79 * </tr>
80 * <tr>
81 * <td style="border: 1px solid black;">1</td>
82 * <td style="border: 1px solid black;">[0, 0]</td>
83 * <td style="border: 1px solid black;">[1]</td>
84 * <td style="border: 1px solid black;">Yes</td>
85 * <td style="border: 1px solid black;">Already equal</td>
86 * <td style="border: 1px solid black;">[1]</td>
87 * <td style="border: 1px solid black;">0</td>
88 * </tr>
89 * <tr>
90 * <td style="border: 1px solid black;">2</td>
91 * <td style="border: 1px solid black;">[1, 2]</td>
92 * <td style="border: 1px solid black;">[2, 4]</td>
93 * <td style="border: 1px solid black;">Yes</td>
94 * <td style="border: 1px solid black;">nums[1] + k = 2 + 2 = 4 = nums[2]</td>
95 * <td style="border: 1px solid black;">[4, 4]</td>
96 * <td style="border: 1px solid black;">1</td>
97 * </tr>
98 * </tbody>
99 * </table>
100 * Thus, ans = [-1, 0, 1].
101 * </div>
102 *
103 * Constraints:
104 *
105 * 1 <= n == nums.length <= 4 × 10^4
106 * 1 <= nums[i] <= 10^9
107 * 1 <= k <= 10^9
108 * 1 <= queries.length <= 4 × 10^4
109 * ^queries[i] = [li, ri]
110 * 0 <= li <= ri <= n - 1
111 *
112 */
113pub struct Solution {}
114
115// problem: https://leetcode.com/problems/minimum-operations-to-equalize-subarrays/
116// discuss: https://leetcode.com/problems/minimum-operations-to-equalize-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
117
118// submission codes start here
119
120impl Solution {
121 pub fn min_operations(nums: Vec<i32>, k: i32, queries: Vec<Vec<i32>>) -> Vec<i64> {
122
123 }
124}
125
126// submission codes end
127
128#[cfg(test)]
129mod tests {
130 use super::*;
131
132 #[test]
133 fn test_3762() {
134 }
135}
136Back
© 2026 bowen.ge All Rights Reserved.