We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Array Into Three Parts With Equal Sum

Number: 1062

Difficulty: Easy

Paid? No

Companies: Turing, Meta, Microsoft

Problem 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 need to check if there exist indices i and j such that: (arr[0] + arr[1] + ... + arr[i]) == (arr[i+1] + ... + arr[j-1]) == (arr[j] + ... + arr[arr.length-1]) with the condition that i+1 < j.

Key Insights

  • The total sum of the array must be divisible by 3.
  • If the total sum is divisible by 3, the target sum for each partition is total_sum / 3.
  • Traverse the array once, accumulating the sum. When the cumulative sum equals target, reset it and count a partition.
  • Ensure that two partitions are found before the end of the array so that the third partition is non-empty.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

First, compute the total sum of the array. If the total sum is not divisible by 3, return false immediately since it's impossible to partition appropriately. Otherwise, the target sum for each partition is total_sum / 3.
Iterate through the array accumulating a running sum. When the running sum equals the target, increment a partition counter and reset the running sum to zero.
If two such partitions are identified before reaching the end of the array, the remainder of the array will form a valid third partition. This approach uses a single pass and minimal extra space, making it efficient for large arrays.

Code Solutions

# Python solution with line-by-line comments
def canThreePartsEqualSum(arr):
    # Calculate total sum of the array
    total_sum = sum(arr)
    # Check if total sum is divisible by 3
    if total_sum % 3 != 0:
        return False
    target = total_sum // 3
    cumulative_sum = 0
    partitions_found = 0
    # Iterate through the array elements
    for i in range(len(arr)):
        cumulative_sum += arr[i]
        # When cumulative_sum equals target, count a partition and reset cumulative_sum
        if cumulative_sum == target:
            partitions_found += 1
            cumulative_sum = 0
            # If two partitions are found and index is not at the end, return true
            if partitions_found == 2 and i < len(arr) - 1:
                return True
    return False

# Example usage:
print(canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]))  # Expected output: True
print(canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1]))  # Expected output: False
← Back to All Questions