LeetCode 1013. Partition Array Into Three Parts With Equal Sum Solution in Java, C++, Python & More | Explanation + Code

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

 

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

Solutions

Solution 1: Traversal and Summation

First, we calculate the sum of the entire array and check if the sum is divisible by 3. If it is not, we directly return false.

Otherwise, let s represent the sum of each part. We use a variable cnt to record the number of parts found so far, and another variable t to record the current part's sum. Initially, cnt = 0 and t = 0.

Then we traverse the array. For each element x, we add x to t. If t equals s, it means we have found one part, so we increment cnt by one and reset t to 0.

Finally, we check if cnt is greater than or equal to 3.

The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

class Solution: def canThreePartsEqualSum(self, arr: List[int]) -> bool: s, mod = divmod(sum(arr), 3) if mod: return False cnt = t = 0 for x in arr: t += x if t == s: cnt += 1 t = 0 return cnt >= 3(code-box)

class Solution { public boolean canThreePartsEqualSum(int[] arr) { int s = Arrays.stream(arr).sum(); if (s % 3 != 0) { return false; } s /= 3; int cnt = 0, t = 0; for (int x : arr) { t += x; if (t == s) { cnt++; t = 0; } } return cnt >= 3; } }(code-box)

class Solution { public: bool canThreePartsEqualSum(vector<int>& arr) { int s = accumulate(arr.begin(), arr.end(), 0); if (s % 3) { return false; } s /= 3; int cnt = 0, t = 0; for (int x : arr) { t += x; if (t == s) { t = 0; cnt++; } } return cnt >= 3; } };(code-box)

func canThreePartsEqualSum(arr []int) bool { s := 0 for _, x := range arr { s += x } if s%3 != 0 { return false } s /= 3 cnt, t := 0, 0 for _, x := range arr { t += x if t == s { cnt++ t = 0 } } return cnt >= 3 }(code-box)

function canThreePartsEqualSum(arr: number[]): boolean { let s = arr.reduce((a, b) => a + b); if (s % 3) { return false; } s = (s / 3) | 0; let [cnt, t] = [0, 0]; for (const x of arr) { t += x; if (t == s) { cnt++; t = 0; } } return cnt >= 3; }(code-box)

impl Solution { pub fn can_three_parts_equal_sum(arr: Vec<i32>) -> bool { let sum: i32 = arr.iter().sum(); let s = sum / 3; let mod_val = sum % 3; if mod_val != 0 { return false; } let mut cnt = 0; let mut t = 0; for &x in &arr { t += x; if t == s { cnt += 1; t = 0; } } cnt >= 3 } }(code-box)