DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

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

SOLUTION:

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        n = len(arr)
        total = sum(arr)
        curr = 0
        f = -1
        s = -1
        for i in range(n):
            curr += arr[i]
            if f < 0 and curr * 3 == total:
                f = i
            if curr * 3 == 2 * total:
                s = i
            if f >= 0 and s >= 0 and f < s and s < n - 1:
                return True
        return False
Enter fullscreen mode Exit fullscreen mode

Top comments (0)