Problem Description

Given an array of integers arr, determine if it can be partitioned into three non-empty parts such that the sum of each part is equal. Each part must be contiguous (i.e., the elements in each part are consecutive in the original array), and every element must be used in exactly one part.

Specifically, you must check if there exist indices i and j (with 0 < i < j < arr.length - 1) such that:

• The sum of arr[0] ... arr[i-1] equals the sum of arr[i] ... arr[j-1] and also equals the sum of arr[j] ... arr[arr.length-1].
• All parts are non-empty and together cover the entire array.

Thought Process

To tackle this problem, let's first consider the brute-force approach: trying every possible way to split the array into three contiguous parts and checking if the sums are equal. This would involve nested loops and checking all possible i and j indices, which is inefficient for large arrays.

Instead, let's look for an optimized strategy. Since the parts must have equal sums, the total sum of the array must be divisible by 3. If it's not, we can immediately return false.

Next, we can scan the array from left to right, keeping track of the running sum. Each time we reach a running sum equal to one-third of the total, we have a candidate for a partition point. We need to find two such points (with at least one element between them for the middle part) to form three equal parts.

The key is to avoid unnecessary work by leveraging prefix sums and the divisibility property, instead of brute-force enumeration.

Solution Approach

Let's break down the optimized solution step by step:

1. Calculate the total sum: Find the sum of all elements in arr. If the total sum is not divisible by 3, it's impossible to split into three equal parts, so return false.
2. Determine the target sum: The sum each part must have is total_sum / 3.
3. Iterate and count partitions: Traverse the array, maintaining a current_sum. Each time current_sum equals the target, increment a count and reset current_sum to zero. This indicates we've found one partition with the required sum.
4. Check for at least three partitions: If we can find at least three such partitions before the end of the array, return true. However, to ensure all parts are non-empty, the third partition must not start at the last element. So, we only need to find the first two partitions before the last element; the remainder will be the third part.

This approach is efficient because it only requires a single pass through the array and uses constant extra space.

Example Walkthrough

Let's consider an example: arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]

• Total sum: 0 + 2 + 1 + (-6) + 6 + (-7) + 9 + 1 + 2 + 0 + 1 = 9
• Target sum for each part: 9 / 3 = 3

Now, let's scan the array, keeping a running sum:

• Index 0: sum = 0
• Index 1: sum = 2
• Index 2: sum = 3 (First partition found; count = 1; reset sum to 0)
• Index 3: sum = -6
• Index 4: sum = 0
• Index 5: sum = -7
• Index 6: sum = 2
• Index 7: sum = 3 (Second partition found; count = 2; reset sum to 0)
• Index 8: sum = 2
• Index 9: sum = 2
• Index 10: sum = 3 (Third partition found; count = 3)

Since we've found at least two partitions before the end of the array, and the rest forms the third partition, the answer is true.

Time and Space Complexity

• Brute-force approach: O(N²) time, since we would try every possible pair of partition indices i and j and sum the segments each time. Space is O(1) if we don't use extra storage.
• Optimized approach: O(N) time, as we only traverse the array once to compute the total sum and again to find the partitions. Space is O(1), since we use only a few variables for tracking sums and counts.

Summary

The key insight is that the array can only be partitioned into three parts with equal sum if the total sum is divisible by 3. By scanning the array and counting how many times we reach the required sum, we can efficiently determine if such a partition exists. This approach is elegant because it reduces the problem to a simple linear scan, avoiding the inefficiency of brute-force checking.

Code Implementation

class Solution:
    def canThreePartsEqualSum(self, arr):
        total = sum(arr)
        if total % 3 != 0:
            return False
        target = total // 3
        count, curr_sum = 0, 0
        for i in range(len(arr)):
            curr_sum += arr[i]
            if curr_sum == target:
                count += 1
                curr_sum = 0
                # To ensure each part is non-empty, stop early if two parts found before the end
                if count == 2 and i < len(arr) - 1:
                    return True
        return False
      

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total = 0;
        for (int num : arr) total += num;
        if (total % 3 != 0) return false;
        int target = total / 3, curr_sum = 0, count = 0;
        for (int i = 0; i < arr.size(); ++i) {
            curr_sum += arr[i];
            if (curr_sum == target) {
                count++;
                curr_sum = 0;
                if (count == 2 && i < arr.size() - 1) return true;
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int total = 0;
        for (int num : arr) total += num;
        if (total % 3 != 0) return false;
        int target = total / 3, curr_sum = 0, count = 0;
        for (int i = 0; i < arr.length; ++i) {
            curr_sum += arr[i];
            if (curr_sum == target) {
                count++;
                curr_sum = 0;
                if (count == 2 && i < arr.length - 1) return true;
            }
        }
        return false;
    }
}
      

var canThreePartsEqualSum = function(arr) {
    const total = arr.reduce((a, b) => a + b, 0);
    if (total % 3 !== 0) return false;
    const target = total / 3;
    let curr_sum = 0, count = 0;
    for (let i = 0; i < arr.length; ++i) {
        curr_sum += arr[i];
        if (curr_sum === target) {
            count++;
            curr_sum = 0;
            if (count === 2 && i < arr.length - 1) return true;
        }
    }
    return false;
};