# Partition Array Into Three Parts With Equal Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-into-three-parts-with-equal-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## 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])`

**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 * 104`
* `-104 <= arr[i] <= 104`

# Approaches
## Brute Force with Prefix Sums
This approach involves checking every possible pair of split points `(i, j)` to partition the array into three parts. To optimize the calculation of subarray sums, we can pre-calculate a prefix sum array. We iterate through all valid `i` and `j` and check if the three resulting subarrays have equal sums.
**Time:** O(N^2), where N is the length of the array. We have two nested loops to iterate through all possible split points `i` and `j`. The prefix sum calculation takes O(N), but it's dominated by the O(N^2) loops. · **Space:** O(N) to store the prefix sum array.
**Pros:** Conceptually simple and easy to understand.; Correctly explores all possible partitions.
**Cons:** Inefficient due to nested loops, leading to a quadratic time complexity.; Requires extra space for the prefix sum array.
### Explanation
The brute-force method systematically checks every possible way to split the array into three non-empty parts. A partition is defined by two indices, `i` and `j`, which mark the end of the first part and the start of the third part, respectively. The condition `i + 1 < j` ensures that the middle part is also non-empty.

To avoid re-calculating the sum of subarrays repeatedly, which would be very inefficient (O(N^3)), we can pre-compute a prefix sum array. The prefix sum array, let's call it `prefix`, stores the cumulative sum up to each index. Specifically, `prefix[k]` will store the sum of `arr[0]...arr[k-1]`. With this, the sum of any subarray `arr[a...b]` can be found in O(1) time by computing `prefix[b+1] - prefix[a]`.

After building the prefix sum array, we use two nested loops to iterate through all valid pairs of `(i, j)` and check if `sum(part1) == sum(part2) == sum(part3)`.

```java
class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int n = arr.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + arr[i];
        }

        // i is the end of the first part, j-1 is the end of the second part
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 2; j < n; j++) {
                int sum1 = prefixSum[i + 1];
                int sum2 = prefixSum[j] - prefixSum[i + 1];
                int sum3 = prefixSum[n] - prefixSum[j];

                if (sum1 == sum2 && sum2 == sum3) {
                    return true;
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- Create a prefix sum array `P` where `P[k]` stores the sum of elements from `arr[0]` to `arr[k-1]`.
- Iterate through the first possible split point `i` from `0` to `arr.length - 3`.
- For each `i`, iterate through the second possible split point `j` from `i + 2` to `arr.length - 1`.
- The condition `i + 1 < j` ensures that all three parts are non-empty.
- For each pair `(i, j)`, calculate the sums of the three parts using the prefix sum array:
  - Part 1: `sum1 = P[i + 1]`
  - Part 2: `sum2 = P[j] - P[i + 1]`
  - Part 3: `sum3 = P[arr.length] - P[j]`
- If `sum1`, `sum2`, and `sum3` are all equal, a valid partition is found, so return `true`.
- If the loops complete without finding such a partition, return `false`.

## Two-Pass Linear Scan
This approach improves upon brute force by avoiding nested loops. A key observation is that if a valid partition exists, the total sum of the array must be divisible by 3. We can find the first possible end `i` for the first part (from the left) and the first possible start `j` for the third part (from the right). If such `i` and `j` exist and are separated by at least one element (i.e., `i + 1 < j`), we have found a valid partition.
**Time:** O(N), where N is the length of the array. It involves at most two full passes over the array to find the cut points. · **Space:** O(1), as it only uses a few variables for sums and indices.
**Pros:** Efficient with O(N) time complexity.; Intuitive logic that directly maps to finding the three parts from the ends of the array.
**Cons:** Requires two passes over the array, which is slightly less efficient than a true single-pass solution.; The logic finds only the first possible cuts from either end, which might not be intuitive but works for this specific problem.
### Explanation
This method leverages the fact that if the array can be partitioned, each of the three parts must sum to `totalSum / 3`. 

First, we compute the total sum of the array. If it's not divisible by 3, we immediately know a partition is impossible. Otherwise, we calculate the `target` sum for each part.

Next, we perform two linear scans:
1. A forward scan from the beginning of the array to find the first index `i` where the prefix sum `arr[0] + ... + arr[i]` equals the `target` sum.
2. A backward scan from the end of the array to find the first index `j` where the suffix sum `arr[j] + ... + arr[n-1]` equals the `target` sum.

If we successfully find both such an `i` and a `j`, we then need to check if the partitions are valid. The partitions are `arr[0...i]`, `arr[i+1...j-1]`, and `arr[j...n-1]`. For all three to be non-empty, we must satisfy the condition `i + 1 < j`. If this holds, the middle part's sum is guaranteed to also be `target`, and we've found a solution.

```java
class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }

        if (totalSum % 3 != 0) {
            return false;
        }
        int target = totalSum / 3;

        int firstCutIndex = -1;
        int currentSum = 0;
        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            if (currentSum == target) {
                firstCutIndex = i;
                break;
            }
        }

        if (firstCutIndex == -1) {
            return false;
        }

        int thirdCutIndex = -1;
        currentSum = 0;
        for (int j = arr.length - 1; j >= 0; j--) {
            currentSum += arr[j];
            if (currentSum == target) {
                thirdCutIndex = j;
                break;
            }
        }

        if (thirdCutIndex == -1) {
            return false;
        }

        // Check if the parts are non-empty and distinct
        return firstCutIndex < thirdCutIndex - 1;
    }
}
```
### Algorithm
- First, calculate the total sum `S` of all elements in the array.
- If `S` is not divisible by 3, it's impossible to partition the array into three equal sum parts. Return `false`.
- Calculate the required sum for each part, `target = S / 3`.
- Find the first index `i` from the left such that the sum of `arr[0...i]` is `target`. Let this be `firstCutIndex`.
- Find the first index `j` from the right (i.e., last index) such that the sum of `arr[j...n-1]` is `target`. Let this be `thirdCutIndex`.
- If either `firstCutIndex` or `thirdCutIndex` is not found, return `false`.
- A valid partition requires three non-empty parts. This is satisfied if `firstCutIndex < thirdCutIndex - 1`.
- If this condition is met, return `true`; otherwise, return `false`.

## Optimal Single-Pass Approach
The most optimal approach involves a single pass through the array. After confirming the total sum is divisible by 3 and calculating the target sum for each part, we can iterate through the array once. We maintain a running sum and count how many times this sum equals the target value, effectively forming partitions greedily from the left.
**Time:** O(N), where N is the length of the array. We iterate through the array once to calculate the total sum and once more to find the partitions. · **Space:** O(1), as we only use a few variables to store the sums and counters.
**Pros:** Highly efficient with a linear time complexity.; Uses constant extra space.; Simple and elegant logic implemented in a single pass.
**Cons:** The logic might seem non-obvious at first, especially the `partsFound >= 3` condition for the `target = 0` case.
### Explanation
This approach is both efficient and elegant. It relies on the same initial check: if the `totalSum` of the array is not divisible by 3, partitioning is impossible. If it is, each part must sum to `target = totalSum / 3`.

The core of the algorithm is a single loop through the array. We maintain a `currentSum` and a counter `partsFound`. As we iterate, we accumulate the `currentSum`. Whenever `currentSum` equals the `target`, we have successfully identified a complete part. At this point, we increment `partsFound` and reset `currentSum` to 0 to start accumulating the sum for the next part.

After the loop finishes, we check if we have found at least 3 parts. If `partsFound >= 3`, it means we were able to find at least two partitions summing to `target` before reaching the end of the array. This guarantees that the third part is non-empty and, because the total sum is `3 * target`, the third part's sum is also `target`. The condition `>= 3` is used instead of `== 3` to correctly handle the edge case where `target` is 0, as there could be multiple consecutive zero-sum partitions.

```java
class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }

        if (totalSum % 3 != 0) {
            return false;
        }

        int target = totalSum / 3;
        int partsFound = 0;
        int currentSum = 0;

        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            if (currentSum == target) {
                partsFound++;
                currentSum = 0;
            }
        }
        
        // If totalSum is 0, we could have more than 3 parts of sum 0.
        // e.g., [0,0,0,0]. target=0, partsFound=4. Valid partition: [0], [0], [0,0]
        // If totalSum is not 0, we must find exactly 3 parts that consume the whole array.
        // The check `partsFound >= 3` covers both cases because if we find 2 parts
        // and there's a non-empty remainder, the partition is valid.
        return partsFound >= 3;
    }
}
```
### Algorithm
- First, calculate the total sum `S` of all elements in the array.
- If `S` is not divisible by 3, it's impossible to partition the array. Return `false`.
- Calculate the required sum for each part, `target = S / 3`.
- Initialize a counter for the number of parts found, `partsFound = 0`, and a running sum, `currentSum = 0`.
- Iterate through the array from index `i = 0` to `arr.length - 1`.
- In each iteration, add `arr[i]` to `currentSum`.
- If `currentSum` becomes equal to `target`, we have found a valid partition. Increment `partsFound` and reset `currentSum` to 0.
- After the loop, if `partsFound` is 3 or more, it means we have successfully partitioned the array. Return `true`. The condition `>= 3` correctly handles cases where `target = 0`, which might lead to more than 3 zero-sum partitions. If `totalSum != 0`, `partsFound` will be exactly 3 if a solution exists and the entire array sum is consumed.

# Solutions
### Java

```java
class Solution {
public
  boolean canThreePartsEqualSum(int[] arr) {
    int s = 0;
    for (int v : arr) {
      s += v;
    }
    if (s % 3 != 0) {
      return false;
    }
    int i = 0, j = arr.length - 1;
    int a = 0, b = 0;
    while (i < arr.length) {
      a += arr[i];
      if (a == s / 3) {
        break;
      }
      ++i;
    }
    while (j >= 0) {
      b += arr[j];
      if (b == s / 3) {
        break;
      }
      --j;
    }
    return i < j - 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canThreePartsEqualSum(vector<int> &arr) {
    int s = 0;
    for (int v : arr)
      s += v;
    if (s % 3)
      return false;
    int i = 0, j = arr.size() - 1;
    int a = 0, b = 0;
    while (i < arr.size()) {
      a += arr[i];
      if (a == s / 3) {
        break;
      }
      ++i;
    }
    while (~j) {
      b += arr[j];
      if (b == s / 3) {
        break;
      }
      --j;
    }
    return i < j - 1;
  }
};

```

### Python

```python
class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool: s = sum(arr) if s % 3 != 0: return False i, j = 0, len(arr) - 1 a = b = 0 while i < len(arr): a += arr[i] if a == s // 3: break i += 1 while ~ j: b += arr[j] if b == s // 3: break j -= 1 return i < j - 1

```