Scale Engineer

Partition Array Into Three Parts With Equal Sum

Easy
#0967Time: 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.1 company
Patterns
Greedy
Data structures
Array
Companies
Turing

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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).

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem