Problem Description

You are given an array of integers arr. Your task is to determine if you can split this array into exactly three non-empty parts where each part has the same sum.

More specifically, you need to find two split points (indices i and j) such that:

• The first part includes elements from index 0 to i (inclusive)
• The second part includes elements from index i+1 to j-1 (inclusive)
• The third part includes elements from index j to the end of the array (inclusive)
• All three parts must have equal sums

The constraint i + 1 < j ensures that all three parts are non-empty.

For example:

• If arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1], you can split it into [0, 2, 1], [-6, 6, -7, 9, 1], and [2, 0, 1], where each part sums to 3. So the answer would be true.
• If arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1], no valid three-way partition exists with equal sums, so the answer would be false.

Return true if such a partition is possible, otherwise return false.

Intuition

To split an array into three parts with equal sums, we first need to think about what the sum of each part should be. If the total sum of the array is S, and we want three equal parts, then each part must have a sum of S/3. This immediately tells us that if S is not divisible by 3, it's impossible to create three equal parts.

Once we know each part should sum to S/3, we can traverse the array and keep a running sum. Every time our running sum reaches S/3, we've found one complete part. We then reset our running sum to 0 and continue looking for the next part.

The key insight is that we don't need to track the exact positions where we split the array. We just need to count how many times we can form a part with sum S/3. If we can form at least 3 such parts, then we can definitely partition the array into exactly 3 parts with equal sums.

Why "at least 3" instead of "exactly 3"? Consider an array like [0, 1, -1, 0] where the total sum is 0, so each part should sum to 0. We might find more than 3 points where the running sum equals 0, but as long as we have at least 3, we can choose any two of them as our split points to create exactly 3 parts.

This greedy approach works because once we've accumulated a sum of S/3, we can "commit" to ending a part there. We don't need to consider other possibilities because all valid partitions must have parts summing to S/3.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a straightforward traversal and summation strategy:

1. Calculate Total Sum and Check Divisibility: First, we compute the sum of all elements in the array and check if it's divisible by 3 using divmod(sum(arr), 3). This gives us both the quotient s (which represents the target sum for each part) and the remainder mod. If mod is non-zero, we immediately return false since it's impossible to split into three equal parts.

2. Initialize Tracking Variables: We use two variables:

   • cnt: Counts how many complete parts with sum s we've found
   • t: Tracks the running sum of the current part being formed

3. Traverse and Count Parts: We iterate through each element x in the array:

   • Add x to the running sum t
   • If t equals s, we've found a complete part:
     • Increment cnt by 1
     • Reset t to 0 to start tracking the next part

4. Check Result: After traversing the entire array, we return true if cnt >= 3, otherwise false.

The algorithm works because:

• Every time we reach the target sum s, we greedily mark it as the end of a part
• We don't need to track exact split positions - just counting occurrences is sufficient
• Having at least 3 parts with sum s guarantees we can choose appropriate split points to create exactly 3 parts
• The last element is automatically included in the count since after processing all elements, if we've found at least 2 parts of sum s, the remaining elements must also sum to s (since total = 3s)

Time Complexity: O(n) where n is the length of the array (one pass through the array)
Space Complexity: O(1) as we only use a few variables regardless of input size

Example Walkthrough

Let's walk through the solution with a small example: arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]

Step 1: Calculate total sum and check divisibility

• Total sum = 0 + 2 + 1 + (-6) + 6 + (-7) + 9 + 1 + 2 + 0 + 1 = 9
• Using divmod(9, 3): quotient s = 3, remainder mod = 0
• Since remainder is 0, we can proceed (each part should sum to 3)

Step 2: Initialize tracking variables

• cnt = 0 (number of complete parts found)
• t = 0 (running sum of current part)

Step 3: Traverse the array and count parts

Step 4: Check result

• cnt = 3, which is >= 3
• Return true

The algorithm found 3 complete parts with sum 3:

• Part 1: [0, 2, 1] = 3
• Part 2: [-6, 6, -7, 9, 1] = 3
• Part 3: [2, 0, 1] = 3

Note that the algorithm doesn't track the exact split positions, but by counting 3 occurrences of the target sum, it confirms that a valid 3-way partition exists.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. This is because the algorithm performs two linear operations: first calculating the sum of all elements in the array using sum(arr) which takes O(n) time, and then iterating through the array once with a for loop to count the partitions, which also takes O(n) time. The total time complexity is O(n) + O(n) = O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables s, mod, cnt, t, and x, regardless of the input array size. No additional data structures that grow with the input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrectly Handling Arrays with Target Sum of 0

The most significant pitfall in this solution is when the target sum equals 0 (i.e., when the total array sum is 0). In this case, the algorithm counts every occurrence where the running sum becomes 0 as a partition boundary, which can lead to incorrect results.

Example of the Problem: Consider arr = [0, 1, -1, 0]:

• Total sum = 0, so target_sum = 0
• As we traverse:
  • After index 0: current_sum = 0 → partition_count = 1
  • After index 2: current_sum = 0 → partition_count = 2
  • After index 3: current_sum = 0 → partition_count = 3
• The algorithm returns true (partition_count >= 3)

However, this is incorrect! We need exactly 3 non-empty parts. The algorithm is essentially counting 4 partition points (including the implicit end), which would create 4 parts if we tried to reconstruct the actual partitions.

Solution to the Pitfall:

To fix this issue, we need to ensure we're finding exactly 2 explicit partition points (not including the array end), which will create exactly 3 parts:

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        target_sum, remainder = divmod(sum(arr), 3)
      
        if remainder != 0:
            return False
      
        partition_count = 0
        current_sum = 0
      
        # Important: We iterate until len(arr) - 1 to ensure the last part is non-empty
        for i in range(len(arr) - 1):
            current_sum += arr[i]
          
            if current_sum == target_sum:
                partition_count += 1
                current_sum = 0
              
                # Early termination: once we find 2 partitions, 
                # the remaining elements automatically form the third
                if partition_count == 2:
                    return True
      
        return False

Key Changes:

1. Loop until len(arr) - 1: This ensures we leave at least one element for the third part
2. Early termination at partition_count == 2: Once we find 2 parts with the target sum, we know the remaining elements form the third part (which must also sum to target_sum)
3. Return False if we don't find exactly 2 partition points: This handles edge cases where we might find more potential partition points than needed

This approach correctly handles all cases, including when target_sum = 0, by ensuring we create exactly 3 non-empty parts.