Python Beginner Algorithms Tutorial

# Partition Array Into Three Parts With Equal Sum (via Leetcode)

Problem can be found on Leetcode.

Problem statement:

Given an array of integers, return True if and only if we can partition the array into at least three non-empty parts with equal sums. Otherwise, return False.

### Test Cases¶

In :
# assert three_equal_sum_partitions([10, -10, 10, -10, 10, -10, 10, -10]) == True


The total sum is 0. One third of 0 is still 0. This test case evaluates to True so each partition must have a sum of 0.

• Partition 1 is [10, -10]
• Partition 2 is [10, -10]
• Partition 3 is [10, -10]

It doesn't matter that there's a 4th partition of [10, -10] that has a sum of 0.

In :
# assert three_equal_sum_partitions([0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]) == True


The total sum is 9. One third of 9 is 3. This test case evaluates to True so each partition must have a sum of 3.

• Partition 1 is [0, 2, 1]
• Partition 2 is [-6, 6, -7, 9, 1]
• Partition 3 is [2, 0, 1]
In :
# assert three_equal_sum_partitions([0,2,1,-6,6,7,9,-1,2,0,1]) == False


The total sum is 21. One third of 21 is 7. However, this test case evalutes to False because there are not three partitions with a sum of 7.

### Pseudocode¶

In :
# create a function with an argument for a list of integers
# assign a variable to be one third of sum of list of integers
# assign variable partition_sum to be 0
# assign a count for the number of partitions that equal exactly one third total sum of integers list

# iterate through all indices in integer list
# increment partition_sum by value in in integer list at this index
# if partition_sum is equal to one third of total sum:
# increase count by 1
# if count is equal to 3:
# we've satisfied constraints of *at least* 3...
# return True
# reset partition_sum to 0
# finished iteration and didn't find three equal sums...
# return False


### Code¶

In :
def three_equal_sum_partitions(integers_list):
one_third_total_sum = sum(integers_list)/3
partition_sum = 0
count_one_third_sum_partitions = 0

for i in range(0, len(integers_list)):
partition_sum += integers_list[i]
if partition_sum == one_third_total_sum:
count_one_third_sum_partitions += 1
if count_one_third_sum_partitions == 3:
return True
partition_sum = 0
return False


### Complexity¶

Let n be the count of values in integers_list.

Time complexity:

• Calculation of sum of integers_list requires iteration over all values in integers_list so it's an O(n) operation.
• At worst case, there must be an iteration over all index values in integers_list which is an O(n) operation.

Total time complexity is O(2n). However, the 2 is minimal and can be removed. Final time complexity is O(n).

Space complexity:

Only a few variables are created for O(1) operations which is minor so it's essentially zero.

### Validate Code with Test Cases¶

In :
assert three_equal_sum_partitions([10,-10,10,-10,10,-10,10,-10]) == True

In :
assert three_equal_sum_partitions([0,2,1,-6,6,-7,9,1,2,0,1]) == True

In :
assert three_equal_sum_partitions([0,2,1,-6,6,7,9,-1,2,0,1]) == False

In :
assert three_equal_sum_partitions([3,3,6,5,-2,2,5,1,-9,4]) == True