algoadvance

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

Formally, you need to find indices i and j with i+1 < j such that (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 is partitioned as [0,2,1], [-6,6,-7,9,1], [2,0,1])
2. Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1] Output: false
3. Input: arr = [3,3,6,5,-2,2,5,1,-9,4] Output: true (Explanation: The array can be partitioned as [3,3], [6,5,-2,2], [5,1,-9,4])

Clarifying Questions

1. Can the array be empty or have fewer than 3 elements? No, the problem states that the array must be partitioned into three non-empty parts.
2. Are there any constraints on the values within the array, such as the range of integers? No specific constraints regarding the range of integer values, but typical integer handling should suffice.

Strategy

1. Calculate the Total Sum: Determine the total sum of the array.
2. Check Divisibility: If the total sum is not divisible by 3, return false immediately as it cannot be partitioned into three equal parts.
3. Partitioning: Traverse through the array while maintaining a running sum. Whenever the running sum equals one-third of the total sum, we increment a counter and reset the running sum. If we find exactly two such partitions (which means we also have a third part automatically), we can partition the array into three parts.
4. Return Result: If the counter reaches at least two by the end, return true. Otherwise, return false.

Code

def canThreePartsEqualSum(arr):
    total_sum = sum(arr)
    if total_sum % 3 != 0:
        return False
    
    target_sum = total_sum // 3
    running_sum, count, n = 0, 0, len(arr)
    
    for num in arr:
        running_sum += num
        if running_sum == target_sum:
            count += 1
            running_sum = 0
        if count == 2 and running_sum == 0:
            return True
    
    return False

# Test Cases
print(canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1])) # Expected: True
print(canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1])) # Expected: False
print(canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4]))   # Expected: True

Time Complexity

• Time Complexity: O(n) where n is the length of the array. We traverse the array at most once.
• Space Complexity: O(1) since we use a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?