Partition Array Into Three Parts With Equal Sum

Problem

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])

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

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^4
• -10^4 <= arr[i] <= 10^4

Solution

Method 1 – Greedy Partition by Running Sum

Intuition

If the total sum of the array is not divisible by 3, it's impossible to split it into three equal parts. Otherwise, we can scan the array and count how many times we reach a running sum equal to one third of the total. If we can do this at least twice before the end, the array can be partitioned as required.

Approach

1. Compute the total sum of the array. If it's not divisible by 3, return false.
2. Let target be one third of the total sum.
3. Iterate through the array, maintaining a running sum.
4. Each time the running sum equals target, reset the sum and increment a counter.
5. If the counter reaches 3 (i.e., we found three parts), return true.
6. Otherwise, return false.

Code

C++

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total = accumulate(arr.begin(), arr.end(), 0);
        if (total % 3 != 0) return false;
        int target = total / 3, sum = 0, cnt = 0;
        for (int i = 0; i < arr.size(); ++i) {
            sum += arr[i];
            if (sum == target) {
                ++cnt;
                sum = 0;
            }
        }
        return cnt >= 3;
    }
};

Go

func canThreePartsEqualSum(arr []int) bool {
    total := 0
    for _, v := range arr {
        total += v
    }
    if total%3 != 0 {
        return false
    }
    target := total / 3
    sum, cnt := 0, 0
    for _, v := range arr {
        sum += v
        if sum == target {
            cnt++
            sum = 0
        }
    }
    return cnt >= 3
}

Java

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int total = 0;
        for (int v : arr) total += v;
        if (total % 3 != 0) return false;
        int target = total / 3, sum = 0, cnt = 0;
        for (int v : arr) {
            sum += v;
            if (sum == target) {
                cnt++;
                sum = 0;
            }
        }
        return cnt >= 3;
    }
}

Kotlin

class Solution {
    fun canThreePartsEqualSum(arr: IntArray): Boolean {
        val total = arr.sum()
        if (total % 3 != 0) return false
        val target = total / 3
        var sum = 0
        var cnt = 0
        for (v in arr) {
            sum += v
            if (sum == target) {
                cnt++
                sum = 0
            }
        }
        return cnt >= 3
    }
}

Python

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

Rust

impl Solution {
    pub fn can_three_parts_equal_sum(arr: Vec<i32>) -> bool {
        let total: i32 = arr.iter().sum();
        if total % 3 != 0 { return false; }
        let target = total / 3;
        let (mut sum, mut cnt) = (0, 0);
        for &v in &arr {
            sum += v;
            if sum == target {
                cnt += 1;
                sum = 0;
            }
        }
        cnt >= 3
    }
}

TypeScript

class Solution {
    canThreePartsEqualSum(arr: number[]): boolean {
        const total = arr.reduce((a, b) => a + b, 0);
        if (total % 3 !== 0) return false;
        const target = total / 3;
        let sum = 0, cnt = 0;
        for (const v of arr) {
            sum += v;
            if (sum === target) {
                cnt++;
                sum = 0;
            }
        }
        return cnt >= 3;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of arr. We scan the array once to compute the sum and once to partition.
• 🧺 Space complexity: O(1), only a few variables are used for counting and summing.