# 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¶

```
# 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.

```
# 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]`

```
# 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¶

```
# 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¶

```
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¶

```
assert three_equal_sum_partitions([10,-10,10,-10,10,-10,10,-10]) == True
```

```
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]) == False
```

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