Partition Array Into Three Parts With Equal Sum - Leetcode Solution

Problem Statement: Given an array of integers arr, return True if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]).

Example 1: Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true Explanation: The array can be partitioned as [0, 2, 1], [-6, 6, -7, 9, 1], [2, 0, 1], where each group has a sum of 3.

Approach: To partition the array into, we need to first calculate the sum of all the elements in the array. If the sum is not divisible by 3, then we cannot partition the array into 3 non-empty parts with equal sums.

Otherwise, we need to find two positions in the array where we can partition it into 3 parts. To do that, we can use 2 pointers, left and right. We start from the first element of the array and the last element of the array respectively. We keep a track of the sum of elements from left to right and from right to left. If at any point the sum of the elements between left and right is equal to one-third of the total sum, we increment our counter of partitions. We keep doing this until the left pointer is less than the right pointer. If we are able to make 3 partitions, we return true, else false.

Algorithm:

1. Initialize two pointers left and right to the first and last index of the array respectively.
2. Calculate the sum of all the elements in the array and keep it in a variable called totalSum.
3. If totalSum is not divisible by 3, return false.
4. Initialize two variables leftSum and rightSum to 0. These variables will keep track of the sum of elements from left to right and right to left.
5. Initialize a variable called partitions to 0. This variable will keep track of the number of partitions we have made so far.
6. While left is less than right: a. If leftSum is equal to one-third of totalSum, increment partitions and reset leftSum to 0. b. If rightSum is equal to one-third of totalSum, increment partitions and reset rightSum to 0. c. Add arr[left] to leftSum and move the left pointer to the right. d. Add arr[right] to rightSum and move the right pointer to the left.
7. If partitions is equal to 3, return true, else false.

Code:

def canThreePartsEqualSum(arr: List[int]) -> bool: totalSum = sum(arr) if totalSum % 3 != 0: return False

left, right = 0, len(arr) - 1
leftSum, rightSum = 0, 0
partitions = 0

while left < right:
    if leftSum == totalSum // 3:
        partitions += 1
        leftSum = 0
    else:
        leftSum += arr[left]
        left += 1
        
    if rightSum == totalSum // 3:
        partitions += 1
        rightSum = 0
    else:
        rightSum += arr[right]
        right -= 1
    
    if partitions == 3:
        return True
    
return False

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input array. We need to iterate over the entire array to calculate the sum and find the partition points.

Space Complexity: The space complexity of the algorithm is O(1). We are not using any extra space except for some variables to keep track of pointers, sum, and partitions.

1