Partition Array Into 3 Parts With Equal Sum [Easy] — Three-Pointer
Sanjeev SharmaAdvertisement
Problem Statement
Return true if we can partition the array into 3 non-empty contiguous parts with equal sum.
Input: [0,2,1,-6,6,-7,9,1,2,0,1] → Output: true (parts: [0,2,1],[-6,6,-7,9,1],[2,0,1])
Intuition
Target = total / 3. If total % 3 != 0, false. Scan and count how many times we've accumulated target and 2*target — if we get 3 parts, true.
Solutions
Python
def canThreePartsEqualSum(arr: list[int]) -> bool:
total = sum(arr)
if total % 3 != 0: return False
target, cur, parts = total // 3, 0, 0
for i, v in enumerate(arr):
cur += v
if cur == target * (parts+1):
parts += 1
if parts == 2 and i < len(arr)-1:
return True
return False
C++
bool canThreePartsEqualSum(vector<int>& arr) {
int total=0; for(int x:arr) total+=x;
if(total%3) return false;
int target=total/3, cur=0, parts=0;
for(int i=0;i<arr.size();i++){
cur+=arr[i];
if(cur==target*(parts+1)){parts++;if(parts==2&&i<(int)arr.size()-1)return true;}
}
return false;
}
Complexity
- Time: O(n), Space: O(1)
Advertisement
