1013. Partition Array Into Three Parts With Equal Sum LeetCode Solution

In this guide, you will get 1013. Partition Array Into Three Parts With Equal Sum LeetCode Solution with the best time and space complexity. The solution to Partition Array Into Three Parts With Equal Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Partition Array Into Three Parts With Equal Sum solution in C++
4. Partition Array Into Three Parts With Equal Sum solution in Java
5. Partition Array Into Three Parts With Equal Sum solution in Python
6. Additional Resources

Problem Statement of Partition Array Into Three Parts With Equal Sum

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

Complexity Analysis

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

1013. Partition Array Into Three Parts With Equal Sum LeetCode Solution in C++

class Solution {
 public:
  bool canThreePartsEqualSum(vector<int>& arr) {
    const int sum = accumulate(arr.begin(), arr.end(), 0);
    if (sum % 3 != 0)
      return false;

    const int average = sum / 3;
    int partCount = 0;
    int partSum = 0;

    for (const int a : arr) {
      partSum += a;
      if (partSum == average) {
        ++partCount;
        partSum = 0;
      }
    }

    // edge case: arr = [0, 0, 0, 0] -> partCount = 4.
    return partCount >= 3;
  }
};
/* code provided by PROGIEZ */

1013. Partition Array Into Three Parts With Equal Sum LeetCode Solution in Java

class Solution {
  public boolean canThreePartsEqualSum(int[] arr) {
    final int sum = Arrays.stream(arr).sum();
    if (sum % 3 != 0)
      return false;

    final int average = sum / 3;
    int partCount = 0;
    int partSum = 0;

    for (final int a : arr) {
      partSum += a;
      if (partSum == average) {
        ++partCount;
        partSum = 0;
      }
    }

    // edge case: arr = [0, 0, 0, 0] -> partCount = 4.
    return partCount >= 3;
  }
}
// code provided by PROGIEZ

1013. Partition Array Into Three Parts With Equal Sum LeetCode Solution in Python

class Solution:
  def canThreePartsEqualSum(self, arr: list[int]) -> bool:
    summ = sum(arr)
    if summ % 3 != 0:
      return False

    average = summ // 3
    partCount = 0
    partSum = 0

    for a in arr:
      partSum += a
      if partSum == average:
        partCount += 1
        partSum = 0

    # edge case: arr = [0, 0, 0, 0] . partCount = 4.
    return partCount >= 3
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.