Partition Array Into Three Parts With Equal Sum

Easy
485.

Partition Array Into Three Parts With Equal Sum

Partition Array Into Three Parts With Equal Sum is an easy coding problem on arrays, greedy and prefix sum, asked in Amazon interviews.

Given an array of integers arr, return true if it can be partitioned into three non-empty contiguous parts with equal sums.

Formally, you need indices i < j with i + 1 < j such that arr[0..i], arr[i+1..j-1] and arr[j..n-1] all have the same sum.

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... the three parts each sum to 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
Each part sums to 6.

Constraints

  • 3 <= arr.length <= 50000
  • -10000 <= arr[i] <= 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canThreePartsEqualSum = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition Array Into Three Parts With Equal Sum — Solution

Partition Array Into Three Parts With Equal Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Partition Array Into Three Parts With Equal Sum is an easy coding problem on arrays, greedy and prefix sum, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy, Prefix Sum
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of integers arr, return true if it can be partitioned into three non-empty contiguous parts with equal sums.

Formally, you need indices i < j with i + 1 < j such that arr[0..i], arr[i+1..j-1] and arr[j..n-1] all have the same sum.

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... the three parts each sum to 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: Each part sums to 6.

Constraints

  • 3 <= arr.length <= 50000
  • -10000 <= arr[i] <= 10000

Hints for Partition Array Into Three Parts With Equal Sum

  1. Hint 1

    If the total is not divisible by 3 the answer is immediately false.

  2. Hint 2

    Sweep once, cutting greedily the moment the running sum reaches one third, then two thirds.

  3. Hint 3

    The third part must be non-empty — check that the second cut happens before the last index.

How to solve Partition Array Into Three Parts With Equal Sum

The two cut positions are forced: the first must land where the prefix sum first hits total/3, and the second where it first hits 2·total/3. Cutting later can never help.

Approach

  1. Sum the array. If total % 3 != 0, return false.
  2. Set part = total / 3 and sweep with a running prefix acc, counting cuts made.
  3. When acc equals part * (cuts + 1), take the cut.
  4. Return true as soon as the second cut is taken at an index strictly before the last, so the third part is non-empty.

Why it works

Prefix sums are the only quantity that matters, and the earliest index reaching each threshold leaves the most room for the remaining parts. Because the trailing part is fixed by the second cut, taking cuts greedily is optimal.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Zeros make prefix sums plateau, so the running sum can equal part many times — count cuts, do not re-trigger on the same threshold.
  • Allowing the second cut at the final index yields an empty third part.
  • total % 3 on negative totals still works in every language here because the check is against 0, but the divisibility test must precede the division.

Reference solution

Python

from typing import List

def canThreePartsEqualSum(arr: List[int]) -> bool:
    total = sum(arr)
    if total % 3 != 0:
        return False
    part = total // 3
    acc = 0
    found = 0
    for i, x in enumerate(arr):
        acc += x
        if acc == part * (found + 1):
            found += 1
            if found == 2 and i < len(arr) - 1:
                return True
    return False

Java

public static boolean canThreePartsEqualSum(int[] arr) {
    long total = 0;
    for (int x : arr) total += x;
    if (total % 3 != 0) return false;
    long part = total / 3;
    long acc = 0;
    int found = 0;
    for (int i = 0; i < arr.length; i++) {
        acc += arr[i];
        if (acc == part * (found + 1)) {
            found++;
            if (found == 2 && i < arr.length - 1) return true;
        }
    }
    return false;
}

C++

bool canThreePartsEqualSum(vector<int>& arr) {
    long long total = 0;
    for (int x : arr) total += x;
    if (total % 3 != 0) return false;
    long long part = total / 3;
    long long acc = 0;
    int found = 0;
    for (int i = 0; i < (int) arr.size(); i++) {
        acc += arr[i];
        if (acc == part * (found + 1)) {
            found++;
            if (found == 2 && i < (int) arr.size() - 1) return true;
        }
    }
    return false;
}

JavaScript

var canThreePartsEqualSum = function(arr) {
    let total = 0;
    for (let i = 0; i < arr.length; i++) total += arr[i];
    if (total % 3 !== 0) return false;
    const part = total / 3;
    let acc = 0, found = 0;
    for (let i = 0; i < arr.length; i++) {
        acc += arr[i];
        if (acc === part * (found + 1)) {
            found++;
            if (found === 2 && i < arr.length - 1) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms