1658. Minimum Operations to Reduce X to Zero

MediumArrayHash TableBinary SearchPrefix SumSliding Window
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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:

  1. Calculate the new target x as the sum of all elements in nums minus the original x. This represents the sum of the subarray we want to find.

  2. Initialize ans with the value inf to represent a very high number of operations (assumed to be impossible) that will be minimized as we find valid subarrays.

  3. Set n to the length of nums, s to 0 as the current sum, and j to 0 as the starting index of our sliding window.

  4. Start iterating through the array with index i representing the end boundary of the sliding window. Add nums[i] to the sum s.

  5. While the current sum s exceeds the target x, adjust the window by moving the start j to the right (increasing j and subtracting nums[j] from s).

  6. When a subarray sum equals the target, update ans with the minimum of its current value and n - (i - j + 1). This calculation gives us the number of operations because i - j + 1 is the length of our subarray, and subtracting this from the total length n gives the number of operations needed to achieve the original x.

  7. Continue the steps 4-6 until all elements have been visited.

  8. At the end, if no valid subarray is found (meaning ans is still inf), return -1. Otherwise, return the value of ans 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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the following array nums and integer x:

1nums = [3, 2, 20, 1, 1, 3]
2x = 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:

  1. Initialize ans with a value representing infinity, s (current sum) to 0, j (window start index) to 0, and n (the length of nums) to 6.

  2. 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 target 20. We need to adjust the window:

    • j is incremented to 1 (removing nums[0] from sum), so the window is [2, 20], and s = 22.
    • j is incremented to 2 (removing nums[1]), so the window is [20], and s = 20.

  3. We have found a subarray that sums up to our target (20), which is [20]. We update ans with the number of operations needed to remove the other elements: n - (i - j + 1) which is 6 - (2 - 2 + 1) = 5.

  4. Continue the algorithm with the rest of nums, checking for a longer subarray that sums to 20, but no such longer subarray will be found. The window would shrink and grow as the sum oscillates relative to our target.

  5. 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 of 20.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which two pointer technique does Quick Sort use?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Binary Search Speedrun

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

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

Sliding Window Maximum

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ