#1013

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Partition Array Into Three Parts With Equal Sum

Determine if an array can be partitioned into three non-empty parts with equal sum using greedy choice and validation.

Problem Statement

You are given an array of integers, and your task is to return true if you can partition the array into three non-empty parts with equal sums. The array can be split into three parts if there exist two indices, i and j, such that the sum of the elements in the segments from 0 to i, i+1 to j-1, and j to the end of the array are all equal.

For example, given the array arr = [0,2,1,-6,6,-7,9,1,2,0,1], you need to determine if you can split it into three parts where each part sums to the same value. This problem tests your ability to recognize the greedy strategy of accumulating sums and validating invariant conditions at each step.

Examples

Example 1

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]

Output: true

0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]

Output: false

Example details omitted.

Example 3

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]

Output: true

3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Constraints

3 <= arr.length <= 5 * 104
-104 <= arr[i] <= 104

Solution Approach

Initial Check of Total Sum

Start by calculating the total sum of the array. If the total sum is not divisible by 3, immediately return false since it is impossible to split the array into three equal parts.

Greedy Choice for First Partition

Iterate through the array, accumulating the sum from the start. Once you find a sum equal to one-third of the total, this can potentially be the first partition. Continue this process for the second partition.

Validation of Second and Third Partitions

After identifying the first partition, continue summing from the next index to find the second partition. If the sum matches one-third of the total, the remainder must match the third partition. If these conditions are met, return true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for summing the array and validating partitions, but typically it is O(n) due to the single pass through the array. Space complexity is O(1) since only a few extra variables are needed for the sums and indices.

What Interviewers Usually Probe

Test candidate's understanding of greedy techniques and how it applies to partitioning problems.
Check if the candidate can efficiently handle large input arrays with O(n) complexity.
Look for the ability to break down the problem into smaller, logical steps with careful validation of invariants.

Common Pitfalls or Variants

Common pitfalls

Failing to check if the total sum of the array is divisible by 3, which is an early termination condition.
Rushing the partitioning step without checking that the sums are being validated after each greedy choice.
Ignoring edge cases where the array length is too small or the elements are too varied to form three equal partitions.

Follow-up variants

Modify the problem to ask for splitting the array into four or more parts with equal sums.
Change the array constraints to allow negative numbers only and test the handling of those scenarios.
Introduce an additional constraint that the partitions must be contiguous, not just non-empty, and evaluate the solution approach.

FAQ

How do I know if partitioning is possible in the "Partition Array Into Three Parts With Equal Sum" problem?

If the total sum of the array is not divisible by 3, partitioning is not possible. Otherwise, use a greedy approach to try and partition the array into three equal sums.

What are the key steps in solving "Partition Array Into Three Parts With Equal Sum"?

The steps include calculating the total sum, checking for divisibility by 3, then using a greedy approach to find the first two partitions while validating the third.

Can this problem be solved in less than linear time?

No, this problem generally requires linear time complexity, O(n), to scan through the array and validate possible partitions.

What is a common mistake when solving this problem?

A common mistake is not checking if the total sum is divisible by 3 before proceeding with the partitioning logic.

What variations can be made to the "Partition Array Into Three Parts With Equal Sum" problem?

Variations include increasing the number of partitions, requiring contiguous segments, or adding new constraints like negative numbers.

terminal

Solution

Solution 1: Traversal and Summation

First, we calculate the sum of the entire array and check if the sum is divisible by 3. If it is not, we directly return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        s, mod = divmod(sum(arr), 3)
        if mod:
            return False
        cnt = t = 0
        for x in arr:
            t += x
            if t == s:
                cnt += 1
                t = 0
        return cnt >= 3

Continue Practicing

#1007 minimum domino rotations for equal row #1005 maximize sum of array after k negations #1024 video stitching