Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go

• class Solution {
      public boolean canThreePartsEqualSum(int[] arr) {
          int s = 0;
          for (int v : arr) {
              s += v;
          }
          if (s % 3 != 0) {
              return false;
          }
          int i = 0, j = arr.length - 1;
          int a = 0, b = 0;
          while (i < arr.length) {
              a += arr[i];
              if (a == s / 3) {
                  break;
              }
              ++i;
          }
          while (j >= 0) {
              b += arr[j];
              if (b == s / 3) {
                  break;
              }
              --j;
          }
          return i < j - 1;
      }
  }
  

• class Solution {
  public:
      bool canThreePartsEqualSum(vector<int>& arr) {
          int s = 0;
          for (int v : arr) s += v;
          if (s % 3) return false;
          int i = 0, j = arr.size() - 1;
          int a = 0, b = 0;
          while (i < arr.size()) {
              a += arr[i];
              if (a == s / 3) {
                  break;
              }
              ++i;
          }
          while (~j) {
              b += arr[j];
              if (b == s / 3) {
                  break;
              }
              --j;
          }
          return i < j - 1;
      }
  };
  

• class Solution:
      def canThreePartsEqualSum(self, arr: List[int]) -> bool:
          s = sum(arr)
          if s % 3 != 0:
              return False
          i, j = 0, len(arr) - 1
          a = b = 0
          while i < len(arr):
              a += arr[i]
              if a == s // 3:
                  break
              i += 1
          while ~j:
              b += arr[j]
              if b == s // 3:
                  break
              j -= 1
          return i < j - 1
  
  

• func canThreePartsEqualSum(arr []int) bool {
  	s := 0
  	for _, v := range arr {
  		s += v
  	}
  	if s%3 != 0 {
  		return false
  	}
  	i, j := 0, len(arr)-1
  	a, b := 0, 0
  	for i < len(arr) {
  		a += arr[i]
  		if a == s/3 {
  			break
  		}
  		i++
  	}
  	for j >= 0 {
  		b += arr[j]
  		if b == s/3 {
  			break
  		}
  		j--
  	}
  	return i < j-1
  }
  

All Problems

All Solutions