Teaching Kids Programming – Index with Equal Left and Right Sums (Prefix and Suffix Sum Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integer nums, return the earliest index i such that the sum of the numbers left of i is equal to the sum of numbers right of i. If there’s no solution, return -1. Sum of an empty list is defined to be 0.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [2, 3, 4, 0, 5, 2, 2]
Output
3
Explanation
Sum of the numbers left of index 3 is 9 and sum of the numbers right of index 3 also 9.

Example 2
Input
nums = [1, -2, 2]
Output
0
Explanation
Sum of the numbers left of index 0 is 0 and sum of the numbers right of index 0 also 0.

Hints:
Calculate prefix and suffix list.

Bruteforce Algorithm to Iterate over Index

We can iterate over N indices and then calculate the sum of the numbers for the left, and right parts. This takes O(N^2) time overall as sum function takes O(N) time.

class Solution:
    def equalPartitionIndex(self, nums):
        for i in range(len(nums)):
            if sum(nums[:i]) == sum(nums[i+1:]):
                return i
        return -1

Dynamic Updates of Left and Right Sum

We can dynamically update the left and right sum. Basically, the right subarray gives a number to the left. The time complexity is O(N) and we need to compute the total sum which is the initial value of the right sum.

class Solution:
    def equalPartitionIndex(self, nums):
        left = 0
        right = sum(nums)
        for i, c in enumerate(nums):
            right -= c
            if left == right:
                return i
            left += c
        return -1        

Prefix and Suffix Algorithm

We can use accumulate the compute the prefix sum. Alternatively we can compute the suffix sum. The total sum is the last value of the accumulate/prefix sum. Then as we iterate over the indices, we can compute the sum of the other part.

class Solution:
    def equalPartitionIndex(self, nums):
        left = [0] + list(accumulate(nums))
        total = sum(nums)
        for i in range(len(nums)):
            if left[i] == total - left[i + 1]:
                return i
        return -1     

The time complexity is O(N) linear. The space complexity is O(N) as we need to store the prefix/suffix sum.

–EOF (The Ultimate Computing & Technology Blog) —