Zero Sum Subarray
Uncover efficient methods for identifying subarrays that sum to zero within a larger array of integers.
Published At
3/5/2023
Reading Time
~ 3 min read
You're given a list of integers nums. Write a function that returns a boolean representing whether there exists a zero-sum subarray of nums.
A zero-sum subarray is any subarray where all the values add up to zero. A subarray is any contiguous section of the array. For the purposes of this problem, a subarray can be as small as one element and as long as the original array.
Sample Input
nums = [-5, -5, 2, 3, -2]
nums = [-5, -5, 2, 3, -2]
Sample Output
True // The subarray [-5, 2, 3] has a sum of 0
True // The subarray [-5, 2, 3] has a sum of 0
Hints
Hint 1
A good way to approach this problem is to first think of a simpler version. How would you check if the entire array sum is zero?
Hint 2
If the entire array does not sum to zero, then you need to check if there are any smaller sub-arrays that sum to zero. For this, it can be helpful to keep track of all the sums from [0, i], where i is every index in the array.
Hint 3
After recording all sums from [0, i], what would it mean if a sum is repeated?
Optimal Space & Time Complexity
O(n) time | O(n) space - where n is the length of nums
function zeroSumSubarray(nums) {
for (let i = 0; i < nums.length; i++) {
let sum = nums[i]
if (sum === 0) {
return true
}
for (let j = i + 1; j < nums.length; j++) {
sum = sum + nums[j]
if (sum === 0) {
console.log(nums[i], nums[j])
return true
}
}
}
return false;
}
function zeroSumSubarray(nums) {
for (let i = 0; i < nums.length; i++) {
let sum = nums[i]
if (sum === 0) {
return true
}
for (let j = i + 1; j < nums.length; j++) {
sum = sum + nums[j]
if (sum === 0) {
console.log(nums[i], nums[j])
return true
}
}
}
return false;
}
function zeroSumSubarray(nums) {
// Write your code here.
const sums = new Set([0])
let currentSum = 0
for (const num of nums) {
currentSum += num
if(sums.has(currentSum)) return true
sums.add(currentSum)
}
return false
}
function zeroSumSubarray(nums) {
// Write your code here.
const sums = new Set([0])
let currentSum = 0
for (const num of nums) {
currentSum += num
if(sums.has(currentSum)) return true
sums.add(currentSum)
}
return false
}
🧝♂️
Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.
Have a wonderful day.
Abhishek 🙏