Jobs

Interviews

Discussions

Partition Array Into Three Parts With Equal Sum

Easy

Partition Array Into Three Parts With Equal Sum

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges and data types of numbers within the array? Can I expect negative numbers, zeros, or floating-point numbers?
What should I return if it is impossible to partition the array into three parts with equal sums?
Are there any constraints on the size of the input array? What is the maximum possible size of the array?
If there are multiple valid ways to partition the array, do I need to return a specific one, or is any valid partition acceptable?
Are there any constraints or expectations regarding the performance or efficiency of my solution?

Brute Force Solution

Approach

The brute force method to split something into three equal parts involves systematically trying every possible combination. It's like exploring every single cut you could make until you find a way to divide it equally. This approach leaves no stone unturned but can be tedious.

Here's how the algorithm would work step-by-step:

First, figure out the total value of all the parts combined.
Calculate what one-third of that total value would be; this is the value each part should have if the split is successful.
Start by guessing where the first split should be, trying every single position from the beginning.
For each of these first split positions, try every possible position for the second split, remembering it has to come after the first split.
For each pair of split positions, calculate the value of the first part, the second part, and the remaining third part.
Check if all three parts have the exact same value which is equal to one-third of the total value.
If you find a pair of split positions where all three parts have equal values, you have found a solution and you're done.
If you go through every single possible combination of split positions and never find three equal parts, then the original thing cannot be split into three equal parts.

Code Implementation

def can_three_parts_equal_sum(arr):
    array_sum = sum(arr)

    # If total sum is not divisible by 3, it cannot be equally partitioned
    if array_sum % 3 != 0:
        return False

    target_sum = array_sum / 3
    array_length = len(arr)

    for first_partition_end in range(array_length - 2):
        first_partition_sum = sum(arr[0:first_partition_end + 1])

        # Check if the first partition equals target sum
        if first_partition_sum == target_sum:

            for second_partition_end in range(first_partition_end + 1, array_length - 1):
                second_partition_sum = sum(arr[first_partition_end + 1:second_partition_end + 1])

                # Check if the second partition equals target sum
                if second_partition_sum == target_sum:

                    third_partition_sum = sum(arr[second_partition_end + 1:])

                    #Checking all partitions are equal to the target.
                    if third_partition_sum == target_sum:
                        return True

    # No valid partitions found
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible pairs of split points in the array of size n. The outer loop considers all potential positions for the first split, which takes O(n) time. The inner loop, for each position of the first split, explores all possible positions for the second split, also taking O(n) time in the worst case. For each pair of split points, calculating the sum of the three subarrays takes constant time, O(1). Thus, the dominant operation is the nested loop structure, resulting in approximately n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(1) – The brute force solution, as described, iterates through possible split positions within the input array. It calculates sums of subarrays directly without creating any auxiliary data structures like temporary arrays or hash maps to store intermediate sums or split positions. The only additional space required is for a few integer variables, such as loop counters, the total sum, the target one-third sum, and potentially variables to hold the sums of the three partitions. The space required for these variables remains constant regardless of the input array's size (N), resulting in constant auxiliary space.

Optimal Solution

Approach

The core idea is to figure out what the target sum for each of the three parts should be and then try to find those parts. We achieve efficiency by summing up the values one by one, stopping as soon as a part adds up to the target sum.

Here's how the algorithm would work step-by-step:

Calculate the total sum of all the numbers.
Check if the total sum is divisible by three. If not, it's impossible to split the array into three equal parts, so stop.
If the total sum is divisible by three, find the target sum for each part by dividing the total sum by three.
Start from the beginning of the list of numbers and keep adding them up to get the current sum.
Each time the current sum equals the target sum, consider that one part is found and reset the current sum back to zero.
Repeat the process of accumulating the current sum and checking against the target sum. Each successful hit implies a potential partition.
Do this until we have found three parts that sum up to the target sum. Then return the result.

Code Implementation

def can_three_parts_equal_sum(array_of_numbers) -> bool:
   total_sum = sum(array_of_numbers)
\
   if total_sum % 3 != 0:
       return False
\
   target_sum = total_sum // 3
   current_sum = 0
   parts_found = 0
\
   for number in array_of_numbers:
       current_sum += number
       # Check if current partition sum matches the target
       if current_sum == target_sum:
           parts_found += 1
           current_sum = 0
\
   # Need to find exactly three parts that match target
   return parts_found >= 3

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n to calculate the total sum. Then it iterates through the array again to find the three partitions with equal sums. Each element is visited at most twice: once to calculate the total sum, and potentially another time to find a partition. Therefore, the overall time complexity is linear with respect to the input size n, resulting in O(n).

Space Complexity

O(1) – The algorithm calculates the total sum and the target sum which are stored in single variables. It uses a current sum variable to accumulate values and count the number of partitions found, all of which use constant space. The space used does not depend on the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as partitioning is impossible.
Array with fewer than 3 elements	Return false because partitioning into three non-empty parts is impossible.
Array sum is not divisible by 3	Return false since equal partitioning is not possible.
Array contains only zeros	The solution should correctly identify two partition points to create three equal zero-sum parts.
Array contains very large positive or negative numbers leading to potential integer overflow during sum calculation	Use long data type for sum calculations to prevent integer overflow.
Array where one part is extremely large compared to the others	Iterate through the array to find two valid partitions which are not necessarily next to each other and may have different sizes, but same sum.
Multiple valid partition points exist; identify any valid solution	Return true as soon as the first valid partition is found; no need to find all possibilities.
Array contains duplicates with negative numbers resulting in the target sum	Iterate through the array until two valid partition points are found considering all negative and duplicate number combinations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges and data types of numbers within the array? Can I expect negative numbers, zeros, or floating-point numbers?
What should I return if it is impossible to partition the array into three parts with equal sums?
Are there any constraints on the size of the input array? What is the maximum possible size of the array?
If there are multiple valid ways to partition the array, do I need to return a specific one, or is any valid partition acceptable?
Are there any constraints or expectations regarding the performance or efficiency of my solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the total value of all the parts combined.
Calculate what one-third of that total value would be; this is the value each part should have if the split is successful.
Start by guessing where the first split should be, trying every single position from the beginning.
For each of these first split positions, try every possible position for the second split, remembering it has to come after the first split.
For each pair of split positions, calculate the value of the first part, the second part, and the remaining third part.
Check if all three parts have the exact same value which is equal to one-third of the total value.
If you find a pair of split positions where all three parts have equal values, you have found a solution and you're done.
If you go through every single possible combination of split positions and never find three equal parts, then the original thing cannot be split into three equal parts.

Code Implementation

def can_three_parts_equal_sum(arr):
    array_sum = sum(arr)

    # If total sum is not divisible by 3, it cannot be equally partitioned
    if array_sum % 3 != 0:
        return False

    target_sum = array_sum / 3
    array_length = len(arr)

    for first_partition_end in range(array_length - 2):
        first_partition_sum = sum(arr[0:first_partition_end + 1])

        # Check if the first partition equals target sum
        if first_partition_sum == target_sum:

            for second_partition_end in range(first_partition_end + 1, array_length - 1):
                second_partition_sum = sum(arr[first_partition_end + 1:second_partition_end + 1])

                # Check if the second partition equals target sum
                if second_partition_sum == target_sum:

                    third_partition_sum = sum(arr[second_partition_end + 1:])

                    #Checking all partitions are equal to the target.
                    if third_partition_sum == target_sum:
                        return True

    # No valid partitions found
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the total sum of all the numbers.
Check if the total sum is divisible by three. If not, it's impossible to split the array into three equal parts, so stop.
If the total sum is divisible by three, find the target sum for each part by dividing the total sum by three.
Start from the beginning of the list of numbers and keep adding them up to get the current sum.
Each time the current sum equals the target sum, consider that one part is found and reset the current sum back to zero.
Repeat the process of accumulating the current sum and checking against the target sum. Each successful hit implies a potential partition.
Do this until we have found three parts that sum up to the target sum. Then return the result.

Code Implementation

def can_three_parts_equal_sum(array_of_numbers) -> bool:
   total_sum = sum(array_of_numbers)
\
   if total_sum % 3 != 0:
       return False
\
   target_sum = total_sum // 3
   current_sum = 0
   parts_found = 0
\
   for number in array_of_numbers:
       current_sum += number
       # Check if current partition sum matches the target
       if current_sum == target_sum:
           parts_found += 1
           current_sum = 0
\
   # Need to find exactly three parts that match target
   return parts_found >= 3

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as partitioning is impossible.
Array with fewer than 3 elements	Return false because partitioning into three non-empty parts is impossible.
Array sum is not divisible by 3	Return false since equal partitioning is not possible.
Array contains only zeros	The solution should correctly identify two partition points to create three equal zero-sum parts.
Array contains very large positive or negative numbers leading to potential integer overflow during sum calculation	Use long data type for sum calculations to prevent integer overflow.
Array where one part is extremely large compared to the others	Iterate through the array to find two valid partitions which are not necessarily next to each other and may have different sizes, but same sum.
Multiple valid partition points exist; identify any valid solution	Return true as soon as the first valid partition is found; no need to find all possibilities.
Array contains duplicates with negative numbers resulting in the target sum	Iterate through the array until two valid partition points are found considering all negative and duplicate number combinations.