Partition Array Into Three Parts With Equal Sum — Greedy Two-Pointer Walk

Problem Statement#

Given an integer array arr, return true if and only if it can be partitioned into three non-empty contiguous parts with equal sums. Formally, find indices i < j such that sum(0..i) = sum(i+1..j-1) = sum(j..end).

Constraints:

• 3 <= arr.length <= 5 * 10^4
• -10^4 <= arr[i] <= 10^4

Input:  arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true   (parts: [0,2,1], [-6,6,-7,9,1], [2,0,1])

Why This Problem Matters#

LeetCode 1013 looks easy at first glance, yet it tests two interview fundamentals at once: prefix-sum reasoning and a greedy linear scan with counters. It is a beloved warm-up at Google and Amazon because it cleanly separates candidates who memorise patterns from those who can derive them.

Keywords interviewers expect: prefix sum partition, three equal parts, greedy array split, and single pass O(n) array.

The Core Insight#

If the total sum is not divisible by 3, partitioning is impossible. Otherwise target = total / 3. Walk left-to-right, maintaining a running sum. Each time the running sum equals target, you have completed one part — reset and count. If you complete two parts before reaching the end, the remaining suffix automatically forms the third part.

Visual Dry Run#

For arr = [0,2,1,-6,6,-7,9,1,2,0,1], total = 9, target = 3:

We return true at i = 7 since two parts are confirmed and a non-empty suffix remains.

Solution (Optimal Greedy)#

class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False
        target = total // 3
        running = 0
        parts = 0
        for i, x in enumerate(arr):
            running += x
            if running == target:
                parts += 1
                running = 0
                if parts == 2 and i < len(arr) - 1:
                    return True
        return False

var canThreePartsEqualSum = function(arr) {
    let total = 0;
    for (const x of arr) total += x;
    if (total % 3 !== 0) return false;
    const target = total / 3;
    let running = 0, parts = 0;
    for (let i = 0; i < arr.length; i++) {
        running += arr[i];
        if (running === target) {
            parts++;
            running = 0;
            if (parts === 2 && i < arr.length - 1) return true;
        }
    }
    return false;
};

Time: O(n) — single pass plus the initial sum. Space: O(1).

Two-Pointer Variant#

You can also solve this with two converging pointers from the ends, each accumulating until they hit target. The middle must then sum to target.

class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False
        target = total // 3
        l, r = 0, len(arr) - 1
        ls, rs = arr[l], arr[r]
        while l + 1 < r and ls != target:
            l += 1
            ls += arr[l]
        while r - 1 > l and rs != target:
            r -= 1
            rs += arr[r]
        return ls == target and rs == target and l + 1 < r

Common Mistakes#

• Forgetting the total % 3 != 0 early exit — leads to false positives.
• Returning true once parts == 2 without checking that a non-empty third part remains. Critical edge case: [1, -1, 1, -1, 1, -1] with target 0.
• Using parts == 3 instead of parts == 2 and i < n - 1. The third part is inferred from the suffix; you do not need to consume it explicitly.
• Resetting running only at the end instead of after each match.
• Treating it as a backtracking problem — pure greedy is sufficient.

Interview Tips#

• Lead with the divisibility check; this signals algorithmic discipline.
• Explain why greedy works: once a prefix hits target, including more would prevent the next part from also hitting target. So the earliest valid cut is always safe.
• Mention the edge case explicitly when describing the loop's exit condition.
• Briefly note the two-pointer variant; it scores style points without being required.

Follow-up Questions#

• Partition into K equal-sum parts (LeetCode 698): unlike this Easy variant, K-way partition is NP-hard and uses backtracking + bitmask DP.
• Subarray Sum Equals K (LeetCode 560): different prefix-sum technique using a hashmap of running sums.
• Maximum Sum of 3 Non-Overlapping Subarrays: harder cousin requiring DP over fixed-size windows.
• Streaming version: can we partition an infinite stream as it arrives? Hint: yes, with O(1) state — just count parts as soon as target hits.
• What if the array is rotated? Consider using a doubled array and a sliding pointer.

Key Takeaways#

• Always start with the sum % 3 == 0 precheck — it converts an "impossible" case into O(1) instead of O(n).
• Greedy left-to-right scanning works because the earliest legal cut is always safe. This is a hallmark of prefix-sum partition problems.
• Stop the scan as soon as you see two parts equal to target with a non-empty remainder — the third part is implicit.
• Watch for the target == 0 edge case where consecutive zeros can produce multiple "parts" in the same window.
• The two-pointer variant gives the same O(n) time and is a nice talking point in interviews.
• This pattern generalises to "split array into K equal-sum parts in linear time when K is small and contiguous" — a building block for prefix-sum DP.
• Practising prefix-sum greedy now makes Subarray Sum Equals K and 3-Sum variants substantially easier later.