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 [244]:
# 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 [245]:
# 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 [246]:
# 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 [243]:
# 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 [248]:
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 [249]:
assert three_equal_sum_partitions([10,-10,10,-10,10,-10,10,-10]) == True
In [250]:
assert three_equal_sum_partitions([0,2,1,-6,6,-7,9,1,2,0,1]) == True
In [251]:
assert three_equal_sum_partitions([0,2,1,-6,6,7,9,-1,2,0,1]) == False
In [252]:
assert three_equal_sum_partitions([3,3,6,5,-2,2,5,1,-9,4]) == True