Question

Formatted question description: https://leetcode.ca/all/1658.html

 1658. Minimum Operations to Reduce X to Zero

 You are given an integer array nums and an integer x.
 In one operation, you can either remove the leftmost or the rightmost element from the array nums
    and subtract its value from x. Note that this modifies the array for future operations.

 Return the minimum number of operations to reduce x to exactly 0 if it's possible, otherwise, return -1.


 Example 1:

 Input: nums = [1,1,4,2,3], x = 5
 Output: 2
 Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

 Example 2:

 Input: nums = [5,6,7,8,9], x = 4
 Output: -1

 Example 3:

 Input: nums = [3,2,20,1,1,3], x = 10
 Output: 5
 Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.


 Constraints:
     1 <= nums.length <= 105
     1 <= nums[i] <= 104
     1 <= x <= 109

Algorithm - prefix sum

The idea is the prefix sum. First, let’s deal with the target value x, because the question is actually a certain sub-array in the middle of the array that satisfies its array and = the sum of all numbers in the array-some numbers on both sides, so we first set the target value as -x, so when When we use the idea of ​​prefix sum to find a sub-array that meets the requirements, this sub-array is already equal to the sum of all numbers in the array-x.

Time O(n)

Space O(n)

Code

Java

    class Solution {
        public int minOperations(int[] nums, int x) {
            int target = -x;
            int len = nums.length;
            for (int num : nums) {
                target += num;
            }
            // corner case
            if (target == 0) {
                return len;
            }
            // normal case
            int res = Integer.MIN_VALUE;
            int sum = 0;
            HashMap<Integer, Integer> map = new HashMap<>(); // sum value 0-i => index i
            map.put(0, -1);
            for (int i = 0; i < len; i++) {
                sum += nums[i];
                if (map.containsKey(sum - target)) {
                    res = Math.max(res, i - map.get(sum - target));
                }
                map.put(sum, i);
            }
            return res == Integer.MIN_VALUE ? -1 : len - res;
        }
    }

Algorithm - sliding window

In fact, we can also think in reverse. That is: our remaining array must be the middle part of the original array.

Does that mean that we only need to know the length of the sub-order sum equal to sum(nums)-x in the data. Just subtract it from the length of nums?

Since our goal is the smallest operand, we only require the sum to be the longest sub-sequence of a fixed value, which is a typical sliding window problem.

Code

Java

    class Solution_window {
        public int minOperations(int[] nums, int x) {

            int len = nums.length;
            int target = IntStream.of(nums).sum() - x;

            if (target == 0) {
                return len;
            }

            int left = 0;
            int right = 0;
            int sum = 0;

            int result = Integer.MAX_VALUE;

            while (right < nums.length) {
                sum += nums[right];

                // start shrink
                while (left < right && sum > target) {
                    sum -= nums[left++];
                }

                if (sum == target) {
                    result = Math.min(result, len - (right - left + 1));
                }

                right++;
            }

            return result == Integer.MAX_VALUE ? -1 : result;
        }
    }

Algorithm - DFS

Typical DFS.

Code

Java

    class Solution_dfs {
        public int minOperations(int[] nums, int x) {

//            Arrays.sort(nums);

            return dfs(nums, x, 0, nums.length - 1);
        }

        private int dfs (int[] nums, int x, int start, int end) {

            if (x < 0) {
                return -1;
            }

            if (x == 0) {
                return 0;
            }

            if (start == end) {
                return nums[start] == x ? 1 : -1;
            }

            int l = dfs(nums, x - nums[start], start + 1, end);
            int left = l == -1 ? -1 : 1 + l;

            int r = dfs(nums, x - nums[end], start, end - 1);
            int right = r == -1 ? -1 : 1 + r;

//            System.out.println(start + "," + end + "," + left + "," + right);

            if (left == -1 && right == -1) {
                return -1;
            } else if (left == -1 && right != -1) {
                return right;
            } else if (left != -1 && right == -1) {
                return left;
            } else {
                return Math.min(left, right);
            }
        }
    }

Java

class Solution {
    public int minOperations(int[] nums, int x) {
        int maxLength = -1;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int length = nums.length;
        int[] prefixSums = new int[length];
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            prefixSums[i] = sum;
            map.put(sum, i);
        }
        int remainSum = sum - x;
        for (int i = 0; i < length; i++) {
            int prefixSum = prefixSums[i];
            if (map.containsKey(prefixSum - remainSum))
                maxLength = Math.max(maxLength, i - map.get(prefixSum - remainSum));
        }
        if (maxLength == -1)
            return -1;
        else
            return length - maxLength;
    }
}

All Problems

All Solutions