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

Date published: 2020-04-17

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops

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

# 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

# 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

# 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

# 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

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

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

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

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

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