1013. Partition Array Into Three Parts With Equal Sum
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.
Solution Approach
To implement the solution, the algorithm takes the following steps, leveraging simple iteration and summation:
-
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 returnFalse
. -
To find the partitioning of the array, we maintain two pointers
i
andj
representing the boundaries of the first and last section of the partitioned array, respectively. We also maintain two accumulator variablesa
andb
for the sums of the respective sections. -
We start a while loop that runs as long as
i
has not reached the end of the array. Within this loop, we incrementa
with the current elementarr[i]
and check ifa
has reacheds // 3
. If it has, we break the loop, as we have found the sum for the first part. -
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
whenj
is0
). We incrementb
with the current elementarr[j]
and check ifb
has reacheds // 3
. If it has, we break the loop. -
After finding the two potential cut points
i
andj
, we check ifi < 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 returnTrue
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have the following array of integers:
arr = [1, 3, 4, 2, 2]
Now, let's walk through the solution approach step by step with this example:
-
First, we calculate the sum
s
of all elements in the arrayarr
. We gets = 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 returnFalse
as it would be impossible to partition the array into three parts with an equal sum. -
We then initialize two pointers
i
with the value 0 andj
with the valuelen(arr) - 1
. Also, we initialize two accumulator variablesa
andb
to 0, which we will use to store the sums of the parts as we loop througharr
. -
The target sum for each part is
s // 3
, which is12 // 3 = 4
. We start looping through the array from the start, adding each element toa
untila
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 ati = 1
. -
Similarly, we loop through the array from the end, decrementing
j
and adding each element tob
. Adding the last element 2,b
becomes 2. Decrementingj
, we add the next last element 2,b
becomes 4. We have found the beginning of the third part atj = 3
. -
We then check if
i < j - 1
. In this case,i = 1
, andj = 3
, so1 < 3 - 1
which is1 < 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
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed through its operations step by step.
-
Calculation of the sum - This involves summing all the elements in the array once, which takes
O(N)
time, whereN
is the length of the array. -
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 isO(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.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!