1013. Partition Array Into Three Parts With Equal Sum

EasyGreedyArray
Leetcode Link

Problem Description

The problem asks us to determine whether it's possible to partition a given array of integers arr into three contiguous, non-empty parts such that the sum of the numbers in each part is equal. This is akin to cutting the array at two points to create three subarrays, where each subarray sums up to the same value. The constraints are quite simple: we need to find two indices i and j, with i + 1 < j, that satisfy the partitioning condition.

Intuition

To tackle this problem, we need to consider that if we can partition the array into three parts with equal sums, the sum of the whole array must be divisible by 3. That's our starting point. If the entire sum s does not satisfy this condition, we can immediately return False, because no such partitioning will be possible.

If, on the other hand, s is divisible by 3, we then look for the two cut points by trying to find a subarray from the start and from the end that each sum up to s // 3 (which represents one-third of the array's total sum).

We iterate from the start of the array, accumulating a sum a until a equals s // 3. This represents the end of the first part of the array. We do a similar process from the end of the array, accumulating another sum b until b equals s // 3. This loop runs in reverse and represents the start of the third part of the array. If we find such indices i and j where a and b each equal s // 3, and i is strictly less than j - 1 (which ensures that the middle part is non-empty), we can conclude that it is indeed possible to partition the array into three parts with equal sums, and return True. Otherwise, the function returns False.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

To implement the solution, the algorithm takes the following steps, leveraging simple iteration and summation:

  1. Initially, the algorithm calculates the sum s of all elements in the array. Since we aim to partition the array into three parts with equal sum, we first check if the total sum is divisible by 3. If not, we return False.

  2. To find the partitioning of the array, we maintain two pointers i and j representing the boundaries of the first and last section of the partitioned array, respectively. We also maintain two accumulator variables a and b for the sums of the respective sections.

  3. We start a while loop that runs as long as i has not reached the end of the array. Within this loop, we increment a with the current element arr[i] and check if a has reached s // 3. If it has, we break the loop, as we have found the sum for the first part.

  4. Similarly, we start a while loop that runs in reverse as long as j has not reached the start of the array (~j checks for this since ~j will be -1 when j is 0). We increment b with the current element arr[j] and check if b has reached s // 3. If it has, we break the loop.

  5. After finding the two potential cut points i and j, we check if i < j - 1. This ensures that there is at least one element between the two parts that we have found, fulfilling the non-empty middle section requirement. If this condition is true, we return True, indicating that the array can be partitioned into three parts with equal sums.

The algorithm mainly uses two pointers with a linear pass from both ends of the array, making the time complexity O(n), where n is the number of elements in the array. The space complexity is O(1) since it only uses a fixed number of extra variables.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's say we have the following array of integers:

1arr = [1, 3, 4, 2, 2]

Now, let's walk through the solution approach step by step with this example:

  1. First, we calculate the sum s of all elements in the array arr. We get s = 1 + 3 + 4 + 2 + 2 = 12. Since 12 is divisible by 3, we can proceed. If the sum were not divisible by 3, we would return False as it would be impossible to partition the array into three parts with an equal sum.

  2. We then initialize two pointers i with the value 0 and j with the value len(arr) - 1. Also, we initialize two accumulator variables a and b to 0, which we will use to store the sums of the parts as we loop through arr.

  3. The target sum for each part is s // 3, which is 12 // 3 = 4. We start looping through the array from the start, adding each element to a until a equals 4. Adding the first element 1, a becomes 1. Adding the next element 3, a becomes 4. We have found the end of the first part at i = 1.

  4. Similarly, we loop through the array from the end, decrementing j and adding each element to b. Adding the last element 2, b becomes 2. Decrementing j, we add the next last element 2, b becomes 4. We have found the beginning of the third part at j = 3.

  5. We then check if i < j - 1. In this case, i = 1, and j = 3, so 1 < 3 - 1 which is 1 < 2. This inequality holds, meaning there is at least one element for the middle part, and we can confirm that the array can be split into three parts with equal sums [1, 3], [4], and [2, 2].

Since all checks pass, the function would return True for this array, indicating that partitioning into three parts with equal sums is indeed possible.

Solution Implementation

1from typing import List
2
3class Solution:
4    def can_three_parts_equal_sum(self, arr: List[int]) -> bool:
5        # Calculate the total sum of all elements in the array
6        total_sum = sum(arr)
7        # If the total sum is not divisible by 3, it's not possible to partition the array into three parts with equal sums
8        if total_sum % 3 != 0:
9            return False
10      
11        # Initialize pointers for the left and right partitions
12        left_index, right_index = 0, len(arr) - 1
13        left_sum, right_sum = 0, 0
14      
15        # Increase the left partition until we find a partition with a sum that's a third of the total sum
16        while left_index < len(arr):
17            left_sum += arr[left_index]
18            if left_sum == total_sum // 3:
19                break
20            left_index += 1
21      
22        # Similarly, decrease the right partition to find a partition with a sum that's a third of the total sum
23        while right_index >= 0:
24            right_sum += arr[right_index]
25            if right_sum == total_sum // 3:
26                break
27            right_index -= 1
28      
29        # Check if there is at least one element between the two partitions
30        # i + 1 < j ensures there's room for a middle partition
31        return left_index < right_index - 1
32
33# Example usage:
34# solution = Solution()
35# arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
36# print(solution.can_three_parts_equal_sum(arr))  # Output: True
37
1class Solution {
2    public boolean canThreePartsEqualSum(int[] arr) {
3        // Calculate the total sum of the elements in the array
4        int totalSum = 0;
5        for (int num : arr) {
6            totalSum += num;
7        }
8
9        // If the total sum is not divisible by 3, we cannot split the array into 3 parts with equal sum
10        if (totalSum % 3 != 0) {
11            return false;
12        }
13
14        // Initialize two pointers for traversing the array from both ends
15        int start = 0, end = arr.length - 1;
16
17        // Initialize sums for the segments from the start and end of the array
18        int startSum = 0, endSum = 0;
19
20        // Find the first segment from the start that sums up to a third of the total sum
21        while (start < arr.length) {
22            startSum += arr[start];
23            if (startSum == totalSum / 3) {
24                break;
25            }
26            ++start;
27        }
28
29        // Find the first segment from the end that sums up to a third of the total sum
30        while (end >= 0) {
31            endSum += arr[end];
32            if (endSum == totalSum / 3) {
33                break;
34            }
35            --end;
36        }
37
38        // Check if there is a middle segment between the two previously found segments
39        // The condition `start < end - 1` ensures there is at least one element in the middle segment
40        return start < end - 1;
41    }
42}
43
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // This function checks whether we can partition the array into three parts with equal sum
7    bool canThreePartsEqualSum(vector<int>& arr) {
8        int totalSum = 0;
9
10        // Calculate the sum of all elements in the array
11        for (int value : arr) {
12            totalSum += value;
13        }
14
15        // If the total sum is not divisible by 3, we can't partition it into three parts with equal sum
16        if (totalSum % 3 != 0) return false;
17
18        // The target sum for each of the three parts
19        int targetSum = totalSum / 3;
20      
21        // Indices to iterate over the array from start (i) and end (j)
22        int i = 0, j = arr.size() - 1;
23        int sumFromStart = 0, sumFromEnd = 0;
24
25        // Find the partition from the start of the array
26        while (i < arr.size()) {
27            sumFromStart += arr[i];
28            // If we've reached the target sum, stop the loop
29            if (sumFromStart == targetSum) {
30                break;
31            }
32            ++i;
33        }
34
35        // Find the partition from the end of the array
36        while (j >= 0) {
37            sumFromEnd += arr[j];
38            // If we've reached the target sum, stop the loop
39            if (sumFromEnd == targetSum) {
40                break;
41            }
42            --j;
43        }
44
45        // After finding the two partitions, check if there is at least one element between them
46        return i < j - 1;
47    }
48};
49
50// Example usage:
51// int main() {
52//     Solution obj;
53//     vector<int> arr = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
54//     bool result = obj.canThreePartsEqualSum(arr);
55//     // Expected output: true, because the array can be partitioned as [0, 2, 1], [-6, 6, -7, 9, 1], [2, 0, 1] with equal sum of 3.
56// }
57
1function canThreePartsEqualSum(arr: number[]): boolean {
2    let totalSum: number = 0;
3
4    // Calculate the sum of all elements in the array
5    for (let value of arr) {
6        totalSum += value;
7    }
8
9    // If the total sum is not divisible by 3, we can't partition it into three parts with equal sum
10    if (totalSum % 3 !== 0) return false;
11
12    // The target sum for each of the three parts
13    let targetSum: number = totalSum / 3;
14
15    // Indices to iterate over the array from start (i) and end (j)
16    let i: number = 0, j: number = arr.length - 1;
17    let sumFromStart: number = 0, sumFromEnd: number = 0;
18
19    // Find the partition from the start of the array
20    while (i < arr.length) {
21        sumFromStart += arr[i];
22        // If we've reached the target sum, stop the loop
23        if (sumFromStart === targetSum) {
24            break;
25        }
26        ++i;
27    }
28
29    // Find the partition from the end of the array
30    while (j >= 0) {
31        sumFromEnd += arr[j];
32        // If we've reached the target sum, stop the loop
33        if (sumFromEnd === targetSum) {
34            break;
35        }
36        --j;
37    }
38
39    // After finding the two partitions, check if there is at least one element between them
40    return i < j - 1;
41}
42
43// Example usage:
44// const arr: number[] = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1];
45// const result: boolean = canThreePartsEqualSum(arr);
46// This would return true, because the array can be partitioned as [0, 2, 1], [-6, 6, -7, 9, 1], [2, 0, 1] with each part summing up to 3.
47
Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed through its operations step by step.

  1. Calculation of the sum - This involves summing all the elements in the array once, which takes O(N) time, where N is the length of the array.

  2. Two separate while loops to find the partition points:

  • The first while loop iterates at most N times to find the point where the first third of the array sum can be found (a == s // 3). In the worst case, this is O(N).
  • The second while loop is similar, working backwards from the end of the array. This also has a worst-case scenario of O(N).

Since these loops do not overlap and are not nested, the overall time complexity is the sum of these individual components, which would still be O(N).

Space Complexity

The space complexity of the algorithm is quite straightforward:

  • No additional data structures that grow with the input size are introduced.
  • Only a fixed amount of extra variables (s, i, j, a, b) are used regardless of the input size.

Thus, the space complexity of the function is O(1), indicating constant space usage.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫