Teaching Kids Programming – Longest Zero Sublist Sum via Prefix Sum

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, which contains either -1 or 1, return the length of the longest sublist that sums to 0.

Constraints
n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [1, 1, 1, 1, -1, -1, 1, -1]
Output
6
Explanation
The longest sublist that sums to 0 is [1, 1, -1, -1, 1, -1] which has length 6.

Hints:
Can you use an efficient data structure to store the current sum?

Bruteforce Algorithm to Compute the Longest Zero Sublist Sum

Let’s bruteforce the sublist in O(N^2) time and use O(N) – sum function to compute the sum of the sublist.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def longestZeroSubListSum(self, nums):
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                s = sum(nums[i: j+1])
                if s == 0:
                    ans = max(ans, j - i + 1)                
        return ans

class Solution:
    def longestZeroSubListSum(self, nums):
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                s = sum(nums[i: j+1])
                if s == 0:
                    ans = max(ans, j - i + 1)                
        return ans

The overall time complexity is O(N^3) i.e. O(N^2*N).

Improved Bruteforce Algorithm to Compute the Longest Zero Sublist Sum

Since we know the sum of sublist from index i to index j, we can just accumulate the sum when we calculate the new sublist from i to j+1.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def longestZeroSubListSum(self, nums):
        n = len(nums)
        ans = 0
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                if s == 0:
                    ans = max(ans, j - i + 1)                
        return ans

class Solution:
    def longestZeroSubListSum(self, nums):
        n = len(nums)
        ans = 0
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                if s == 0:
                    ans = max(ans, j - i + 1)                
        return ans

This improves the bruteforce algorithm to O(N^2) as we compute the sum of sublist along the way (accumulate) in O(1) time.

Prefix Sum Algorithm to Compute the Longest Zero Sublist

If two prefixs are the same, we then can compute the corresponding zero sublist length. Therefore, with the help of a hash table (prefix sum) – O(N) space we can improve the runtime complexity to O(N).

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def longestZeroSubListSum(self, nums):
        seen = {0: -1}
        s = ans = 0
        for i, n in enumerate(nums):
            s += n
            if s in seen:
                ans = max(ans, i - seen[s])
            else:
                seen[s] = i
        return ans

class Solution:
    def longestZeroSubListSum(self, nums):
        seen = {0: -1}
        s = ans = 0
        for i, n in enumerate(nums):
            s += n
            if s in seen:
                ans = max(ans, i - seen[s])
            else:
                seen[s] = i
        return ans

We can also manually update the max length to i+1 once we have current prefix sum equal to zero:

1
2

if s == 0:
    ans = i + 1

if s == 0:
    ans = i + 1

We can also store the indices for the equal prefix sum and the longest length for a prefix will be the difference between the first and last index.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def longestZeroSubListSum(self, nums):
        prefix = [0] + list(accumulate(nums))
        seen = defaultdict(list[int])
        for i, s in enumerate(prefix):
            seen[s].append(i)
        ans = 0
        for k in seen:
            ans = max(ans, seen[k][-1] - seen[k][0])
        return ans

class Solution:
    def longestZeroSubListSum(self, nums):
        prefix = [0] + list(accumulate(nums))
        seen = defaultdict(list[int])
        for i, s in enumerate(prefix):
            seen[s].append(i)
        ans = 0
        for k in seen:
            ans = max(ans, seen[k][-1] - seen[k][0])
        return ans

This also runs at O(N) time and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —