👋
Welcome to my blog!

Zero Sum Subarray

Uncover efficient methods for identifying subarrays that sum to zero within a larger array of integers.

Zero Sum Subarray
array
medium

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

js
nums = [-5, -5, 2, 3, -2]
js
nums = [-5, -5, 2, 3, -2]

Sample Output

js
True // The subarray [-5, 2, 3] has a sum of 0
js
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

Solution-1
js
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;
}
Solution-1
js
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;
}
Solution-2
js
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
}
Solution-2
js
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 🙏

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.