Skip to content

1013. Partition Array Into Three Parts With Equal Sum 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
};

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

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