Partition Array Into Three Parts With Equal Sum

Difficulty: Easy | Acceptance: 42.70% | Paid: No Topics: Array, Greedy

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 find indices i + 1 < j with (arr[0] + arr[1] + … + arr[i] == arr[i + 1] + arr[i + 2] + … + arr[j] == arr[j + 1] + arr[j + 2] + … + arr[arr.length - 1])

• Examples
• Constraints
• Brute Force with Prefix Sums
• Greedy Single Pass

Examples

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 + 2 = 0 + 1 = 3

Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Constraints

3 <= arr.length <= 5 * 10⁴
-10⁴ <= arr[i] <= 10⁴

Brute Force with Prefix Sums

Intuition We can iterate through all possible pairs of indices (i, j) that split the array into three parts. Using a prefix sum array allows us to calculate the sum of any subarray in O(1) time.

Steps

• Calculate the total sum of the array. If it is not divisible by 3, return false immediately.
• Compute a prefix sum array where prefix[i] is the sum of elements from index 0 to i-1.
• Iterate through all possible end indices i for the first part (from 0 to n-3).
• If the sum of the first part equals the target, iterate through all possible end indices j for the second part (from i+1 to n-2).
• Check if the sum of the second part and the third part both equal the target.
• If a valid pair (i, j) is found, return true. If the loops finish without success, return false.

class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        n = len(arr)
        total = sum(arr)
        if total % 3 != 0:
            return False
        target = total // 3
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + arr[i]
        for i in range(n - 2):
            if prefix[i + 1] != target:
                continue
            for j in range(i + 1, n - 1):
                if prefix[j + 1] - prefix[i + 1] == target and total - prefix[j + 1] == target:
                    return True
        return False

Complexity

• Time: O(N²) - Nested loops to find partition indices.
• Space: O(N) - For the prefix sum array.
• Notes: This approach is conceptually simple but inefficient for large arrays.

Greedy Single Pass

Intuition If the total sum is divisible by 3, we know the exact sum each part must achieve. We can iterate through the array, accumulating the sum. Every time the accumulated sum hits the target, we increment a counter and reset the accumulator. If we find at least 3 such segments, we return true.

Steps

• Calculate the total sum of the array. If it is not divisible by 3, return false.
• Calculate the target sum for each part (total / 3).
• Initialize a counter for found parts and a variable for the current running sum.
• Iterate through the array, adding each element to the running sum.
• If the running sum equals the target, increment the counter and reset the running sum to 0.
• After the loop, return true if the counter is greater than or equal to 3. (Note: If the target is 0, we might find more than 3 parts, which is still valid).

class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False
        target = total // 3
        curr = 0
        count = 0
        for num in arr:
            curr += num
            if curr == target:
                count += 1
                curr = 0
        return count >= 3

Complexity

• Time: O(N) - Single pass through the array.
• Space: O(1) - Constant extra space used.
• Notes: This is the optimal solution for this problem.