algoadvance

Leetcode 1013. Partition Array Into Three Parts With Equal Sum

Problem Statement

Given an array of integers arr, determine if it’s possible to partition the array into three non-empty parts with equal sums.

Example

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: The array can be partitioned as follows:
[0, 2, 1], [-6, 6, -7, 9], [1, 2, 0, 1], which gives three parts with equal sums of 3.

Clarifying Questions

  1. Can the elements in the array be negative?
    • Yes, the array can contain negative elements.
  2. What is the allowable range of the array length?
    • The length of the array could vary significantly. Typical constraints go anywhere from having a few elements up to thousands of elements.
  3. Is there a constraint on the values of the integers within the array?
    • Typically, values might be constrained to fit within standard integer sizes, but it is safe to check for typical integer constraints, like -10^4 to 10^4.

Strategy

Here is the step-by-step approach to solve this problem:

  1. Calculate the Total Sum: First, we find the total sum of the array. If the total sum is not divisible by 3, it’s impossible to partition the array as required.
  2. Set Target Sum for Each Part: If the total sum is divisible by 3, each part must have a sum equal to total_sum / 3.
  3. Iterate and Sum Segments: Iterate through the array while maintaining a running sum. Count the segments where the running sum equals the target partition sum. We need to find exactly 3 such segments.
  4. Check for Valid Partitioning: Ensure we have found exactly three segments that equal the target partition sum.

Code

#include <vector>
#include <numeric> // for std::accumulate

bool canThreePartsEqualSum(std::vector<int>& arr) {
    int totalSum = std::accumulate(arr.begin(), arr.end(), 0);
    
    // If the total sum is not divisible by 3, it is not possible to partition into 3 parts with equal sum.
    if (totalSum % 3 != 0) return false;
    
    int targetSum = totalSum / 3;
    int currentSum = 0, count = 0;
    
    for (int num : arr) {
        currentSum += num;
        // When sum reaches the target, reset it and increase the count of partitions found
        if (currentSum == targetSum) {
            count++;
            currentSum = 0;
        }
    }
    
    // We need exactly three partitions
    return count >= 3;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI