Longest Continous Zero Sum Subarray


  • 1

    Find the length of longest continuous subarray within an array (containing at least one number) whose sum equals zero.

    For example, given the array [1,0,-1,2],

    The longest continuous subarray of zero-sum is [1,0,-1] , which has length = 3.

    Python prototype:

    class Solution(object):
        def longestContinousZeroSumSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """

  • 1

    One solution I have is first accumulate the nums array, then it will help us quickly know the sum between any indices, it's a very useful technique.

    Once we have the accumulated nums array, we just need to try all the combination of ranges and see if we can find the sum equals to 0 and if the range is longest.

    Here is an example code in Java:

    public int longestContinousZeroSumSubArray(int[] nums) {
      int n = nums.length, max = 0;
      
      // accumulate the nums
      for (int i = 1; i < n; i++) {
        nums[i] += nums[i - 1];
      }
      
      for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
          // calculate the sum between i ... j
          int sum = nums[j] - (i > 0 ? nums[i - 1] : 0);
          
          if (sum == 0 && j - i + 1 > max) {
            max = j - i + 1;
          }
        }
      }
      
      return max;
    }
    

  • 0

    Nice code with time complexity of O(n ^ 2), Could you optimize the time complexity of your algorithm further? :-)


  • 1

    Aha, we can optimize to O(n), after we have the accumulated nums array, we just need to go through this array and find if there's 0 or two identical numbers, if we found them, update the max length. :)


  • 5

    This is the optimized O(n) solution:

    public int longestContinousZeroSumSubArray(int[] nums) {
      int n = nums.length, max = 0;
      
      // accumulate the nums
      for (int i = 1; i < n; i++) {
        nums[i] += nums[i - 1];
      }
      
      Map<Integer, Integer> map = new HashMap<>();
      
      for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        
        if (num == 0)
          max = Math.max(max, i + 1);
        else if (map.containsKey(num))
          max = Math.max(max, i - map.get(num));
        else
          map.put(num, i);
      }
      
      return max;
    }
    

  • 0

    good job, it's O(n) now :D


  • 0

    Thanks mate! Your hint is really helpful! :)


  • 0
    S

    @jeantimex i am lazy to post a comment or reply to one but love you buddy.your code was awesome.it was not copy paste


  • 0
    V

    @jeantimex How can you modify this algorithm so that you can extract the subarray yielding highest sum.


  • 0
    M

    @vaid-abhi : You can keep a track of start and end index while updating max, your end index will be i and start will be something like max-i


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.