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
arrwith length between 3 and 50,000. - Each element in the array can range from -10,000 to 10,000.
Outputs:
- A boolean value (
trueorfalse) 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
- Calculate Total Sum: Compute the total sum of the array.
- Check Divisibility by 3: If the total sum is not divisible by 3, return
false. - Initialize Variables: Set a target sum to one-third of the total sum and initialize a counter for parts found.
- 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.
- 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.