Partition Array Into Three Parts With Equal Sum: Greedy Prefix Scan

You are given an integer array arr. Your task is to determine whether you can partition it into three non-empty contiguous parts such that each part has the same sum. This is LeetCode 1013: Partition Array Into Three Parts With Equal Sum.

Example: arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1] returns true because the array can be split into [0,2,1,-6,6], [-7,9,1], and [2,0,1], each summing to 3.

Why this problem matters

Prefix sums are one of the most versatile tools in array problem solving. They let you compute the sum of any subarray in constant time, and they show up in problems ranging from range queries to sliding windows to partitioning. This problem gives you a clean, focused exercise in prefix sum thinking: you walk through the array once, accumulating a running sum, and you use that running total to decide where to draw partition lines.

Greedy partitioning is the other big idea here. Instead of trying all possible ways to split the array (which would be O(n^2) or worse), you greedily lock in partition boundaries as soon as you find them. The first time the running sum equals the target, you declare the first partition complete and move on. This "commit early" strategy works because the partition must be contiguous and the order of elements is fixed. You are not rearranging anything; you are simply choosing where to draw the dividing lines.

Together, these two ideas -- prefix sums and greedy commitment -- form a pattern you will see again and again. Problems like "Split Array into Consecutive Subsequences," "Partition Labels," and "Subarray Sum Equals K" all build on the same foundation. Mastering this problem gives you a reusable mental model for the whole family.

The key insight

If the total sum of the array is not divisible by 3, there is no way to split it into three equal parts. You can return false immediately.

If the total is divisible by 3, then each part must sum to target = total / 3. Now think about what the running (prefix) sum looks like at each partition boundary:

• After Part 1 ends, the running sum equals target.
• After Part 2 ends, the running sum equals 2 * target (because Part 1 + Part 2 = two targets' worth).
• After Part 3 ends, the running sum equals 3 * target = total. But this is just the end of the array, which is guaranteed.

So you only need to find two split points: one where the running sum first hits target, and a later one where it hits 2 * target. If both exist and there is at least one element left after the second split, the third part is automatically valid. You do not need to check it explicitly.

This means a single left-to-right scan is enough. You count how many times the running sum reaches the next multiple of the target. Once you have found two such points (with room for at least one element in the third part), you are done.

The solution

def can_three_parts_equal_sum(arr):
    total = sum(arr)
    if total % 3 != 0:
        return False
    target = total // 3
    running = 0
    parts = 0
    for i in range(len(arr)):
        running += arr[i]
        if running == target * (parts + 1) and parts < 2:
            parts += 1
    return parts == 2

This version works, but it has a subtle flaw: it does not guarantee that the third part is non-empty. If the running sum reaches 2 * target at the very last element, the third part would be empty. Here is a cleaner version that handles this:

def can_three_parts_equal_sum(arr):
    total = sum(arr)
    if total % 3 != 0:
        return False
    target = total // 3
    running = 0
    count = 0
    for i in range(len(arr) - 1):  # stop before last element
        running += arr[i]
        if running == target * (count + 1):
            count += 1
            if count == 2:
                return True
    return False

Let us walk through the code line by line.

First, you compute the total sum. If it is not divisible by 3, no partition exists, so you return false. Otherwise, target is the sum each part needs to have.

Next, you initialize running (the prefix sum so far) and count (how many partition boundaries you have found). You iterate from index 0 through index len(arr) - 2. Stopping one element before the end ensures the third part always has at least one element.

At each index, you add arr[i] to the running sum. Then you check: does running equal target * (count + 1)? When count is 0, you are looking for the running sum to equal target (end of Part 1). When count is 1, you are looking for 2 * target (end of Part 2). Each time you find a match, you increment count. The moment count reaches 2, you know both boundaries exist with room to spare, so you return true.

If you finish the loop without finding two boundaries, you return false.

Visual walkthrough

The walkthrough shows the running sum growing as you move through the array. The first time it hits 3, you lock in the first partition. The next time it hits 6, you lock in the second. Everything after that is the third partition, which must sum to 3 by the pigeonhole principle.

Complexity analysis

Time is O(n) because you iterate through the array exactly once to compute the total and once more to find the partition boundaries. Both passes are linear, so the overall time is O(n).

Space is O(1) because you only store a handful of variables: total, target, running, and count. No auxiliary arrays or data structures are needed.

The building blocks

1. Prefix sum divisibility check

Before doing any work, you check whether total % 3 == 0. This single check eliminates all impossible cases instantly. If the total is 10, for example, there is no way to split 10 into three equal integers. This kind of early exit is a hallmark of greedy algorithms: if the necessary condition fails, do not waste time on the sufficient condition.

The divisibility check also defines your target. Once you know target = total // 3, you have a concrete number to look for in the running sum. This turns an abstract partitioning problem into a concrete "find the value" search.

2. Greedy partition counting

The counting loop is where the greedy strategy lives. You scan left to right and commit to a partition boundary the moment you find one. You do not backtrack. You do not consider alternative split points. You grab the earliest valid boundary and move on.

Why is greedy correct here? Because the partition must be contiguous. Once the running sum equals target, every element up to that point belongs to Part 1. There is no benefit to extending Part 1 further, because any extra elements you add would need to be "paid back" later. The running sum would overshoot target, and you would need it to come back down before you could find the second boundary. It works out the same in the end, but you might miss Part 2 or Part 3 being non-empty. Taking the earliest boundary maximizes the remaining space for Parts 2 and 3.

Edge cases

• Total not divisible by 3: e.g., [1, 2, 3, 4] has total = 10. Since 10 % 3 != 0, return false immediately.
• All zeros: [0, 0, 0] returns true. The target is 0, and the running sum equals 0 at every index, so you find two partition points right away.
• Negative numbers: [1, -1, 1, -1, 1, -1] has total = 0, target = 0. The running sum oscillates, but it hits 0 at indices 1, 3, and 5. You find two split points before the end, so it returns true.
• Minimum length 3: [1, 1, 1] returns true since target = 1, and the running sum hits 1 at index 0 and 2 at index 1, giving two boundaries with index 2 left for Part 3.
• Large target with single match: [3, 0, 0, 0, 3, 0, 0, 0, 3] with target = 3 finds boundaries at index 0 and index 4, returning true.

From understanding to recall

This problem tests a clean two-step pattern: check divisibility, then greedily scan for partition boundaries. Understanding the logic once is the easy part. The harder part is being able to reproduce it quickly under interview pressure, weeks or months after you first studied it. That is where spaced repetition helps. By revisiting the prefix-sum-and-greedy-counting pattern at increasing intervals, you move it from short-term understanding to long-term recall. When you see a partitioning problem in an interview, the approach should surface automatically.

Related posts

• Partition Labels - Greedy partitioning with a different splitting criterion
• Subarray Sum Equals K - Prefix sum counting with a hash map
• Split Array Largest Sum - Partitioning with constraints using binary search

Master greedy prefix sum patterns and dozens of other coding interview techniques with structured practice.