Skip to content

1013. Partition Array Into Three Parts With Equal Sum

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

Thinking

Trying every pair of cuts is \(O(n^2)\). Three equal parts exist only when the total is divisible by \(3\) and we can form at least three contiguous pieces each summing to \(s=\textit{sum}/3\).

A left-to-right accumulation that resets at every \(s\) counts such pieces. Extra pieces may be absorbed into the last part, so a count of at least \(3\) is enough.

We reject a nonzero remainder modulo \(3\), then maintain the running part sum and the part count in one pass.

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 \(\textit{false}\).

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

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

Finally, we check if \(\textit{cnt}\) is greater than or equal to 3.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
    }
}

Comments