Partition Array Into Three Parts With Equal Sum

easy prefix sum greedy array

Problem

Given an array of integers arr, return true if you can partition the array into three non-empty contiguous parts with equal sums. Formally, you must find indices i < j such that arr[0]+…+arr[i] = arr[i+1]+…+arr[j-1] = arr[j]+…+arr[n-1].

Inputarr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]

Outputtrue

Total = 9, so each part must sum to 3: 0+2+1 = -6+6-7+9+1 = 2+0+1 = 3.

arr (comma-separated)

def can_three_parts_equal_sum(arr):
    total = sum(arr)
    if total % 3 != 0:
        return False
    target = total // 3
    parts, run = 0, 0
    for x in arr:
        run += x
        if run == target:
            parts += 1
            run = 0
    return parts >= 3

function canThreePartsEqualSum(arr) {
  const total = arr.reduce((a, b) => a + b, 0);
  if (total % 3 !== 0) return false;
  const target = total / 3;
  let parts = 0, run = 0;
  for (const x of arr) {
    run += x;
    if (run === target) { parts++; run = 0; }
  }
  return parts >= 3;
}

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

bool canThreePartsEqualSum(vector<int>& arr) {
    int total = 0;
    for (int x : arr) total += x;
    if (total % 3 != 0) return false;
    int target = total / 3, parts = 0, run = 0;
    for (int x : arr) {
        run += x;
        if (run == target) { parts++; run = 0; }
    }
    return parts >= 3;
}

Explanation

If the array can split into three equal parts, each part must sum to exactly one third of the whole. So the very first check is: if total is not divisible by 3, the answer is immediately false. Otherwise our target per part is total / 3.

Now we do a single greedy pass with a running sum run. Every time run reaches target, we have completed one part, so we increment parts and reset run to 0 to start accumulating the next part.

At the end we return whether we closed at least three parts. We check parts >= 3 rather than exactly 3 because extra trailing elements that sum to zero can form additional target-hitting segments, but as long as three full parts exist the partition is valid.

Example: arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1] totals 9, so target = 3. The running sum hits 3 after 0+2+1, again after -6+6-7+9+1, and again after 2+0+1 — three parts, so the answer is true.

Time: O(n) Space: O(1)