Domain 1EasyCORE

Partition Array Into Three Parts With Equal Sum

The problem asks us to determine if an array can be divided into three non-empty contiguous subarrays such that the sum of elements in each subarray is equal. The input is an array of integers, and the output should be a boolean indicating whether such a partitioning is possible.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1013. Partition Array Into Three Parts With Equal Sum

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 48.2%


Problem Breakdown

The problem asks us to determine if an array can be divided into three non-empty contiguous subarrays such that the sum of elements in each subarray is equal. The input is an array of integers, and the output should be a boolean indicating whether such a partitioning is possible.

Inputs:

  • An array of integers arr with length between 3 and 50,000.
  • Each element in the array can range from -10,000 to 10,000.

Outputs:

  • A boolean value (true or false) indicating whether the array can be partitioned into three parts with equal sums.

Implicit Constraints and Edge Cases:

  • The array must have at least three elements.
  • If the total sum of the array is not divisible by 3, it’s impossible to partition it into three parts with equal sums.
  • Negative numbers in the array complicate the sum calculation but do not inherently prevent a valid partition.

Intuition

A brute-force approach would involve checking all possible partitions of the array, which would be computationally expensive (O(n^2) time complexity). Instead, we can leverage the fact that if the total sum of the array is divisible by 3, each part must sum to one-third of this total. We then iterate through the array while maintaining a running sum and count how many times this running sum equals one-third of the total sum.

Approach

  1. Calculate Total Sum: Compute the total sum of the array.
  2. Check Divisibility by 3: If the total sum is not divisible by 3, return false.
  3. Initialize Variables: Set a target sum to one-third of the total sum and initialize a counter for parts found.
  4. Iterate Through Array: Maintain a running sum as you iterate through the array. Each time the running sum equals the target sum, increment the part counter.
  5. Check Final Condition: After iterating, ensure that exactly three parts were found.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array to calculate the total sum and another pass to check for partitions.
  • Space Complexity: O(1). We use only a few extra variables regardless of the input size.

Solution

def canThreePartsEqualSum(arr):
    # Calculate the total sum of the array
    total_sum = sum(arr)
    
    # If the total sum is not divisible by 3, return False
    if total_sum % 3 != 0:
        return False
    
    # The target sum for each part
    target_sum = total_sum // 3
    current_sum = 0
    parts_found = 0
    
    # Iterate through the array to find partitions
    for num in arr:
        current_sum += num
        if current_sum == target_sum:
            parts_found += 1
            current_sum = 0
    
    # We need exactly three parts with equal sum
    return parts_found == 3

# Example usage:
print(canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]))  # Output: True
print(canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1]))  # Output: False
print(canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4]))   # Output: True

Edge Cases Handled

  • Non-divisible Total Sum: If the total sum is not divisible by 3, the function immediately returns false.
  • Array with Negative Numbers: The algorithm correctly handles negative numbers in the array.
  • Minimum Length Array: The function assumes the input array has at least three elements, as per the problem constraints.