Minimum Operations to Reduce X to Zero

Problem

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 is possible, otherwise, return -1.

Examples

Example 1:

1
2
3
4
5


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:

1
2
3
4


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

Example 3:

1
2
3
4
5


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.

Solution

Method 1 - DFS + Memo

Intuition

The idea is to try every possible way of removing elements from either the left or right end of the array, subtracting their values from x at each step. We recursively explore both options at every step, keeping track of the minimum number of operations needed to reduce x to exactly zero. Memoization is used to avoid recalculating results for the same state.

Approach

Use a recursive function that takes the current left and right indices and the remaining value of x.
At each step, try removing the leftmost or rightmost element, and recursively solve the subproblem for the new indices and updated x.
If x becomes zero, return the number of operations taken so far.
If x becomes negative or the indices cross, return -1 (invalid path).
Use memoization to cache results for each state (left, right, x) to avoid redundant calculations.
Return the minimum number of operations found, or -1 if not possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
	int minOperations(vector<int>& nums, int x) {
		unordered_map<string, int> memo;
		function<int(int, int, int)> dfs = [&](int l, int r, int rem) -> int {
			if (rem == 0) return 0;
			if (rem < 0 || l > r) return -1;
			string key = to_string(l) + "," + to_string(r) + "," + to_string(rem);
			if (memo.count(key)) return memo[key];
			int left = dfs(l + 1, r, rem - nums[l]);
			int right = dfs(l, r - 1, rem - nums[r]);
			int ans = INT_MAX;
			if (left != -1) ans = min(ans, 1 + left);
			if (right != -1) ans = min(ans, 1 + right);
			memo[key] = (ans == INT_MAX) ? -1 : ans;
			return memo[key];
		};
		return dfs(0, nums.size() - 1, x);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func minOperations(nums []int, x int) int {
	type key struct{ l, r, rem int }
	memo := make(map[key]int)
	var dfs func(int, int, int) int
	dfs = func(l, r, rem int) int {
		if rem == 0 {
			return 0
		}
		if rem < 0 || l > r {
			return -1
		}
		k := key{l, r, rem}
		if v, ok := memo[k]; ok {
			return v
		}
		left := dfs(l+1, r, rem-nums[l])
		right := dfs(l, r-1, rem-nums[r])
		ans := 1<<31 - 1
		if left != -1 && 1+left < ans {
			ans = 1 + left
		}
		if right != -1 && 1+right < ans {
			ans = 1 + right
		}
		if ans == 1<<31-1 {
			memo[k] = -1
		} else {
			memo[k] = ans
		}
		return memo[k]
	}
	return dfs(0, len(nums)-1, x)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	public int minOperations(int[] nums, int x) {
		Map<String, Integer> memo = new HashMap<>();
		return dfs(nums, 0, nums.length - 1, x, memo);
	}
	private int dfs(int[] nums, int l, int r, int rem, Map<String, Integer> memo) {
		if (rem == 0) return 0;
		if (rem < 0 || l > r) return -1;
		String key = l + "," + r + "," + rem;
		if (memo.containsKey(key)) return memo.get(key);
		int left = dfs(nums, l + 1, r, rem - nums[l], memo);
		int right = dfs(nums, l, r - 1, rem - nums[r], memo);
		int ans = Integer.MAX_VALUE;
		if (left != -1) ans = Math.min(ans, 1 + left);
		if (right != -1) ans = Math.min(ans, 1 + right);
		memo.put(key, ans == Integer.MAX_VALUE ? -1 : ans);
		return memo.get(key);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	fun minOperations(nums: IntArray, x: Int): Int {
		val memo = mutableMapOf<Triple<Int, Int, Int>, Int>()
		fun dfs(l: Int, r: Int, rem: Int): Int {
			if (rem == 0) return 0
			if (rem < 0 || l > r) return -1
			val key = Triple(l, r, rem)
			memo[key]?.let { return it }
			val left = dfs(l + 1, r, rem - nums[l])
			val right = dfs(l, r - 1, rem - nums[r])
			var ans = Int.MAX_VALUE
			if (left != -1) ans = minOf(ans, 1 + left)
			if (right != -1) ans = minOf(ans, 1 + right)
			memo[key] = if (ans == Int.MAX_VALUE) -1 else ans
			return memo[key]!!
		}
		return dfs(0, nums.size - 1, x)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
	def minOperations(self, nums: list[int], x: int) -> int:
		from functools import lru_cache
		n = len(nums)
		@lru_cache(None)
		def dfs(l: int, r: int, rem: int) -> int:
			if rem == 0:
				return 0
			if rem < 0 or l > r:
				return -1
			left = dfs(l + 1, r, rem - nums[l])
			right = dfs(l, r - 1, rem - nums[r])
			ans = float('inf')
			if left != -1:
				ans = min(ans, 1 + left)
			if right != -1:
				ans = min(ans, 1 + right)
			return -1 if ans == float('inf') else ans
		return dfs(0, n - 1, x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


use std::collections::HashMap;
impl Solution {
	pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
		fn dfs(nums: &Vec<i32>, l: usize, r: usize, rem: i32, memo: &mut HashMap<(usize, usize, i32), i32>) -> i32 {
			if rem == 0 { return 0; }
			if rem < 0 || l > r { return -1; }
			if let Some(&v) = memo.get(&(l, r, rem)) { return v; }
			let mut ans = i32::MAX;
			if l < nums.len() {
				let left = dfs(nums, l + 1, r, rem - nums[l], memo);
				if left != -1 { ans = ans.min(1 + left); }
			}
			if r < nums.len() {
				let right = dfs(nums, l, r - 1, rem - nums[r], memo);
				if right != -1 { ans = ans.min(1 + right); }
			}
			let res = if ans == i32::MAX { -1 } else { ans };
			memo.insert((l, r, rem), res);
			res
		}
		let n = nums.len();
		dfs(&nums, 0, n - 1, x, &mut HashMap::new())
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	minOperations(nums: number[], x: number): number {
		const memo = new Map<string, number>();
		function dfs(l: number, r: number, rem: number): number {
			if (rem === 0) return 0;
			if (rem < 0 || l > r) return -1;
			const key = `${l},${r},${rem}`;
			if (memo.has(key)) return memo.get(key)!;
			const left = dfs(l + 1, r, rem - nums[l]);
			const right = dfs(l, r - 1, rem - nums[r]);
			let ans = Number.MAX_SAFE_INTEGER;
			if (left !== -1) ans = Math.min(ans, 1 + left);
			if (right !== -1) ans = Math.min(ans, 1 + right);
			memo.set(key, ans === Number.MAX_SAFE_INTEGER ? -1 : ans);
			return memo.get(key)!;
		}
		return dfs(0, nums.length - 1, x);
	}
}

Complexity

⏰ Time complexity: O(2^n) in the worst case, since at each step we can remove either the leftmost or rightmost element, leading to exponential possibilities. Memoization reduces repeated work, but the number of unique states is O(n^2 * x).
🧺 Space complexity: O(n^2 * x) due to the memoization table storing results for each combination of left, right, and remaining x.

Method 2 - Prefix Sum + Map

Intuition

Instead of removing elements from the ends, we can think in reverse: the elements we do not remove must form a contiguous subarray in the middle whose sum is totalSum - x. To minimize the number of operations, we want to maximize the length of this subarray. Thus, the problem reduces to finding the longest subarray with sum equal to totalSum - x.

Approach

Calculate the total sum of the array. Set target = totalSum - x.
If target is negative, return -1 (not possible).
Use a prefix sum and a hashmap to store the earliest index where each prefix sum occurs.
Iterate through the array, updating the prefix sum and checking if prefixSum - target exists in the map.
If it does, update the answer with the length of the subarray found.
The minimum number of operations is n - maxLen (where maxLen is the length of the longest subarray found). If no such subarray exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
	int minOperations(vector<int>& nums, int x) {
		int n = nums.size();
		int target = accumulate(nums.begin(), nums.end(), 0) - x;
		unordered_map<int, int> mp;
		mp[0] = -1;
		int ans = -1, sum = 0;
		for (int i = 0; i < n; ++i) {
			sum += nums[i];
			mp[sum] = i;
			if (mp.count(sum - target)) {
				int len = i - mp[sum - target];
				ans = max(ans, len);
			}
		}
		return ans == -1 ? -1 : n - ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func minOperations(nums []int, x int) int {
	n := len(nums)
	total := 0
	for _, v := range nums {
		total += v
	}
	target := total - x
	mp := map[int]int{0: -1}
	ans, sum := -1, 0
	for i, v := range nums {
		sum += v
		mp[sum] = i
		if idx, ok := mp[sum-target]; ok {
			if l := i - idx; l > ans {
				ans = l
			}
		}
	}
	if ans == -1 {
		return -1
	}
	return n - ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
	public int minOperations(int[] nums, int x) {
		int n = nums.length;
		int target = 0;
		for (int v : nums) target += v;
		target -= x;
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, -1);
		int ans = -1, sum = 0;
		for (int i = 0; i < n; i++) {
			sum += nums[i];
			map.put(sum, i);
			if (map.containsKey(sum - target)) {
				int len = i - map.get(sum - target);
				ans = Math.max(ans, len);
			}
		}
		return ans == -1 ? -1 : n - ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
	fun minOperations(nums: IntArray, x: Int): Int {
		val n = nums.size
		val target = nums.sum() - x
		val map = mutableMapOf(0 to -1)
		var ans = -1
		var sum = 0
		for (i in nums.indices) {
			sum += nums[i]
			map[sum] = i
			map[sum - target]?.let { idx ->
				val len = i - idx
				if (len > ans) ans = len
			}
		}
		return if (ans == -1) -1 else n - ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
	def minOperations(self, nums: list[int], x: int) -> int:
		n = len(nums)
		target = sum(nums) - x
		mp = {0: -1}
		ans = -1
		s = 0
		for i, v in enumerate(nums):
			s += v
			mp[s] = i
			if (s - target) in mp:
				l = i - mp[s - target]
				if l > ans:
					ans = l
		return -1 if ans == -1 else n - ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


use std::collections::HashMap;
impl Solution {
	pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
		let n = nums.len();
		let target = nums.iter().sum::<i32>() - x;
		let mut mp = HashMap::new();
		mp.insert(0, -1);
		let mut ans = -1;
		let mut sum = 0;
		for (i, &v) in nums.iter().enumerate() {
			sum += v;
			mp.insert(sum, i as i32);
			if let Some(&idx) = mp.get(&(sum - target)) {
				let len = i as i32 - idx;
				if len > ans { ans = len; }
			}
		}
		if ans == -1 { -1 } else { n as i32 - ans }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
	minOperations(nums: number[], x: number): number {
		const n = nums.length;
		const target = nums.reduce((a, b) => a + b, 0) - x;
		const mp = new Map<number, number>();
		mp.set(0, -1);
		let ans = -1, sum = 0;
		for (let i = 0; i < n; ++i) {
			sum += nums[i];
			mp.set(sum, i);
			if (mp.has(sum - target)) {
				const len = i - mp.get(sum - target)!;
				if (len > ans) ans = len;
			}
		}
		return ans === -1 ? -1 : n - ans;
	}
}

Complexity

⏰ Time complexity: O(n), since we traverse the array once and all map operations are constant time.
🧺 Space complexity: O(n), for storing prefix sums in the hashmap.

Problem#

Examples#

Similar Problems#

Solution#

Method 1 - DFS + Memo#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Prefix Sum + Map#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Similar Problems

Solution

Method 1 - DFS + Memo

Intuition

Approach

Code

Complexity

Method 2 - Prefix Sum + Map

Intuition

Approach

Code

Complexity