Partition Array Into Three Parts With Equal Sum

Problem Description

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

Key Insights

• The total sum of the array must be divisible by 3 for it to be partitioned into three equal parts.
• If the total sum is not zero, we need to find two indices i and j such that the sum of the first part equals the sum of the second part, and both equal one third of the total sum.
• We can use a prefix sum approach to track the cumulative sum as we iterate through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we first calculate the total sum of the array. If the total sum is not divisible by 3, we immediately return false. Next, we determine the target sum for each part, which is one third of the total sum. We then use a single pass through the array to track the cumulative sum and identify if we can find the required partitions.

Code Solutions