1658. Minimum Operations to Reduce X to Zero
Problem Description
You are given an array of integers called nums
and another integer x
. Your goal is to remove either the first or last element from the array in each operation. By doing so, you decrease the value of x
by the value of the element you removed. This process changes the array for the next operation since the element is no longer part of it.
The challenge is to find the minimum number of operations needed to reduce x
to exactly 0. It's a puzzle where you must choose which side to take numbers from at each step. However, the array has a fixed order, so you cannot rearrange it. If it's possible to reduce x
to 0, you should return the minimum number of operations you need. If it's not possible to do so, then the answer is -1
.
Intuition
The initial intuition might be to always choose the larger number between the first and last element of the array to subtract from x
. However, this greedy approach might not lead to the optimal solution. Instead, a different perspective can provide a more systematic method: instead of thinking in terms of our original target x
, think about the rest of the numbers that will remain in the array nums
after all the operations.
The key insight is to transform the problem into finding the longest subarray in nums
that sums up to a new target, which is sum(nums) - x
. This approach flips the original problem on its headāyou're now looking for the subarray that remains rather than the numbers to reduce x
to zero.
In the code, an inf
(infinity) is initially set to represent an impossible situation. A two-pointer approach is then used to find the longest subarray whose sum equals sum(nums) - x
. As we iterate through the array with a variable i
, indicating the right end of our subarray, a variable s
(the running sum) is continuously updated. A second pointer j
represents the potential left end of our subarray. We make sure to adjust j
and s
whenever our current running sum surpasses our new target, by subtracting values while moving j
to the right.
When we find a subarray that sums to the new target, we calculate the number of operations it would take to remove the other elements by subtracting the length of this subarray from the total number of elements n
. This operation count is kept if it is smaller than our current best answer in variable ans
.
Once the loop is finished, if ans
remains as infinity, it means no suitable subarray was found, and we return -1
. Otherwise, we return the value of ans
, which represents the minimum number of operations required to reduce x
to exactly 0.
Learn more about Binary Search, Prefix Sum and Sliding Window patterns.
Solution Approach
The solution follows a sliding window approach, which is a pattern used when we need to find a range or a subarray in an array that satisfies certain conditions. The idea behind a sliding window approach is to maintain a subset of items from the array as the window and slide it to explore different subsets, according to conditions given in the problem.
In this specific problem, the target condition for the subarray is that its elements' sum should equal sum(nums) - x
. The reason for this is that the sum of elements removed (to reduce x
to 0) and the sum of elements that remain (the subarray) should equal the sum of the original array.
Here is a step-by-step explanation of the code:
-
Calculate the new target
x
as the sum of all elements innums
minus the originalx
. This represents the sum of the subarray we want to find. -
Initialize
ans
with the valueinf
to represent a very high number of operations (assumed to be impossible) that will be minimized as we find valid subarrays. -
Set
n
to the length ofnums
,s
to 0 as the current sum, andj
to 0 as the starting index of our sliding window. -
Start iterating through the array with index
i
representing the end boundary of the sliding window. Addnums[i]
to the sums
. -
While the current sum
s
exceeds the targetx
, adjust the window by moving the startj
to the right (increasingj
and subtractingnums[j]
froms
). -
When a subarray sum equals the target, update
ans
with the minimum of its current value andn - (i - j + 1)
. This calculation gives us the number of operations becausei - j + 1
is the length of our subarray, and subtracting this from the total lengthn
gives the number of operations needed to achieve the originalx
. -
Continue the steps 4-6 until all elements have been visited.
-
At the end, if no valid subarray is found (meaning
ans
is stillinf
), return-1
. Otherwise, return the value ofans
as the final result.
The use of a sliding window ensures that we check every possible subarray in an efficient manner, only making a single pass through the array, which gives us a time complexity of O(n).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach. Consider the following array nums
and integer x
:
nums = [3, 2, 20, 1, 1, 3] x = 10
The sum of nums
is 3 + 2 + 20 + 1 + 1 + 3 = 30
, so our new target is sum(nums) - x
which is 30 - 10 = 20
.
Now we apply the sliding window approach:
-
Initialize
ans
with a value representing infinity,s
(current sum) to 0,j
(window start index) to 0, andn
(the length ofnums
) to 6. -
Start iterating over the array, beginning with
i = 0
:- First iteration (i=0): window is [3],
s = 3
. - Second iteration (i=1): window is [3, 2],
s = 5
. - Third iteration (i=2): window is [3, 2, 20],
s = 25
.
At this point, our sum
s
exceeds our target20
. We need to adjust the window:j
is incremented to 1 (removingnums[0]
from sum), so the window is [2, 20], ands = 22
.j
is incremented to 2 (removingnums[1]
), so the window is [20], ands = 20
.
- First iteration (i=0): window is [3],
-
We have found a subarray that sums up to our target (20), which is
[20]
. We updateans
with the number of operations needed to remove the other elements:n - (i - j + 1)
which is6 - (2 - 2 + 1) = 5
. -
Continue the algorithm with the rest of
nums
, checking for a longer subarray that sums to20
, but no such longer subarray will be found. The window would shrink and grow as the sum oscillates relative to our target. -
At the end of the process, we will find that the smallest
ans
was 5, which corresponds to removing the first two elements (3 and 2) and the last three elements (1, 1, and 3) while keeping the subarray[20]
, which adds up exactly to our target of20
.
Hence, the minimum number of operations required to reduce x
to 0 in this example is 5.
The sliding window approach makes this process efficient by ensuring that we only need to scan through the array once, which provides us with an O(n) complexity for the problem.
Solution Implementation
1from math import inf
2
3class Solution:
4 def minOperations(self, nums: List[int], x: int) -> int:
5 # Calculate new target which is the sum of elements that remain after removing the elements summing to x.
6 target = sum(nums) - x
7
8 # Initialize variables: set answer to infinity to represent initially impossible scenario
9 # `n` holds the length of the nums list; `current_sum` and `left_index` for the sliding window
10 answer = inf
11 n = len(nums)
12 current_sum = left_index = 0
13
14 # Use a sliding window approach to find if there's a continuous subarray summing to `target`
15 for right_index, value in enumerate(nums):
16 # Expand the window by adding the current value to the `current_sum`
17 current_sum += value
18
19 # Shrink the window from the left as long as `current_sum` exceeds `target`
20 while left_index <= right_index and current_sum > target:
21 current_sum -= nums[left_index]
22 left_index += 1
23
24 # If `current_sum` matches `target`, we found a valid subarray
25 # Update the answer with the minimum number of operations
26 if current_sum == target:
27 # Since we're looking for the minimum operations, we subtract the length of current subarray from total length
28 answer = min(answer, n - (right_index - left_index + 1))
29
30 # If answer has not been updated, return -1, otherwise return the minimum operations
31 return -1 if answer == inf else answer
32
1class Solution {
2 public int minOperations(int[] nums, int x) {
3 int target = -x;
4
5 // Calculate the negative target by adding all the numbers in 'nums' array
6 // Since we are looking for a subarray with the sum that equals the modified 'target'
7 for (int num : nums) {
8 target += num;
9 }
10
11 int n = nums.length;
12 int minimumOperations = Integer.MAX_VALUE;
13 int sum = 0;
14
15 // Two pointers approach to find the subarray with the sum equals 'target'
16 for (int left = 0, right = 0; left < n; ++left) {
17 // Add the current element to 'sum'
18 sum += nums[left];
19
20 // If 'sum' exceeds 'target', shrink the window from the right
21 while (right <= left && sum > target) {
22 sum -= nums[right];
23 right++;
24 }
25
26 // If a subarray with sum equals 'target' is found, calculate the operations required
27 if (sum == target) {
28 minimumOperations = Math.min(minimumOperations, n - (left - right + 1));
29 }
30 }
31
32 // If no such subarray is found, return -1
33 // Otherwise, return the minimum number of operations
34 return minimumOperations == Integer.MAX_VALUE ? -1 : minimumOperations;
35 }
36}
37
1#include <vector>
2#include <unordered_map>
3#include <numeric>
4#include <algorithm>
5
6class Solution {
7public:
8 // Calculate the minimum number of operations to reduce the sum of the array
9 // by 'x' by either removing elements from the start or end.
10 int minOperations(std::vector<int>& nums, int x) {
11 // Compute the new target which is the desired sum of the subarray we want to find
12 int target = std::accumulate(nums.begin(), nums.end(), 0) - x;
13
14 // If target is negative, no solution is possible as we cannot create a negative sum.
15 if (target < 0) {
16 return -1;
17 }
18
19 // Special case: if target is 0, it means we want to remove the whole array
20 if (target == 0) {
21 return nums.size();
22 }
23
24 // Use a hashmap to store the cumulative sum at each index
25 std::unordered_map<int, int> prefixSumIndex;
26 prefixSumIndex[0] = -1; // Initialize hashmap with base case
27
28 int n = nums.size(); // Size of the input array
29
30 // Initialize the answer with a large number, signifying that we haven't found a solution yet
31 int minOperations = std::numeric_limits<int>::max();
32
33 for (int i = 0, sum = 0; i < n; ++i) {
34 sum += nums[i]; // Cumulative sum up to the current index
35
36 // Record the first occurrence of this sum. This prevents overwriting previous indices.
37 if (!prefixSumIndex.count(sum)) {
38 prefixSumIndex[sum] = i;
39 }
40
41 // Check if (sum - target) has been observed before
42 if (prefixSumIndex.count(sum - target)) {
43 int startIdx = prefixSumIndex[sum - target];
44 // Calculate operations as the difference between the current ending index and
45 // the starting index of the subarray, adjusting for whole array length.
46 minOperations = std::min(minOperations, n - (i - startIdx));
47 }
48 }
49
50 // If minOperations hasn't changed, return -1 to indicate no solution found
51 return minOperations == std::numeric_limits<int>::max() ? -1 : minOperations;
52 }
53};
54
1function minOperations(nums: number[], x: number): number {
2 // Calculate the target sum by subtracting x from the total sum of nums
3 let target = nums.reduce((acc, current) => acc + current, 0) - x;
4 const length = nums.length;
5 let minimumOps = Infinity; // Initialize with a large number representing infinity
6
7 // Initialize two pointers for the sliding window and a sum to hold the window's sum
8 let windowStart = 0;
9 let currentSum = 0;
10
11 // Loop over the array to find the maximum-sized subarray that adds up to target
12 for (let windowEnd = 0; windowEnd < length; ++windowEnd) {
13 // Add the current element to windowSum
14 currentSum += nums[windowEnd];
15
16 // Shrink the window from the start if the currentSum exceeds the target
17 while (windowStart <= windowEnd && currentSum > target) {
18 currentSum -= nums[windowStart++];
19 }
20
21 // If the currentSum equals the target, update minimumOps if the found window is better
22 if (currentSum == target) {
23 minimumOps = Math.min(minimumOps, length - (windowEnd - windowStart + 1));
24 }
25 }
26
27 // Return minimum operations required, or -1 if the target sum isn't achievable
28 return minimumOps == Infinity ? -1 : minimumOps;
29}
30
Time and Space Complexity
Time Complexity
The provided code has a time complexity of O(n)
, where n
is the length of the input list nums
. This is because the code uses a two-pointer approach (variables i
and j
) that iterates through the list only once. The inner while
loop adjusts the second pointer (denoted by j
), but it does not iterate more than n
times across the entire for loop due to the nature of the two-pointer strategyāeach element is visited by each pointer at most once.
Space Complexity
The space complexity of the code is O(1)
. Outside of the input data, the algorithm uses only a constant number of additional variables (x
, ans
, n
, s
, j
, i
, and v
). The space required for these variables does not scale with the size of the input list; hence, the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Want a Structured Path to Master System Design Too? Donāt Miss This!