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.
1 2 3 4 5 6 | class Solution: def equalPartitionIndex(self, nums): for i in range(len(nums)): if sum(nums[:i]) == sum(nums[i+1:]): return i return -1 |
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.
1 2 3 4 5 6 7 8 9 10 | 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 |
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.
1 2 3 4 5 6 7 8 | 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 |
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) —
loading...
Last Post: Teaching Kids Programming - Rearrange Array Elements by Sign (Two Pointer Algorithm)
Next Post: Teaching Kids Programming - Top Down and Bottom Up Recursive Algorithms to Determine a Balanced Binary Tree