2025. Maximum Number of Ways to Partition an Array
Problem Description
You are given an array nums
with n
integers. We want to determine the maximum number of ways we can partition this array into two non-empty parts by choosing a pivot
index so that the sum of elements to the left of the pivot is equal to the sum of elements to the right of the pivot. You can also change one element in the array to another integer k
to increase the number of such partitions.
Partitioning an array means picking an index pivot
such that 1 <= pivot < n
and ensuring the following condition is met: the sum of elements from nums[0]
to nums[pivot - 1]
should be equal to the sum of elements from nums[pivot]
to nums[n - 1]
.
You are permitted to change at most one element in nums
to k
or you can choose to keep the array as it is. The goal is to find the maximum number of partitions that satisfy the condition described above after making at most one such change.
Intuition
To arrive at the solution, we need to think about how changing one element to k
could affect the number of valid partitions. When we don't change any element, any pivot
that splits the array into two equal sums is a valid partition. We can calculate the total sum of the array first and then iterate through the array while keeping track of the cumulative sum. This helps us to determine if a pivot
is a valid partition for the unchanged array.
However, when considering the change of one element to k
, we need to think about where this operation would be most beneficial. Changing an element affects the sums of the elements to the left and to the right of that element. It's helpful to keep track of cumulative sums from the left and the right, and update these sums as if the change to k
has been made.
We use two dictionaries: left
to count the frequency of the left sums and right
for the right sums. For each element x
in the array, if we replace x
with k
, we calculate the difference d = k - x
. We then update our counters based on this difference to reflect the new sums if the element were replaced.
Finally, we iterate over each element, consider replacing it with k
, and count how many times the left and right sums across the pivot will then be equal. We update the answer with this count whenever it results in more valid partitions. The idea is to maximize this count, which gives us the maximum possible number of ways to partition the array after changing at most one element.
Learn more about Prefix Sum patterns.
Solution Approach
The solution leverages the defaultdict
from the collections
module, a subclass of the built-in dict
class. It's used to store key-value pairs where the keys represent sums of elements and the values count how many times each sum occurs.
Here's a step-by-step explanation of the implementation:
-
Initialize the cumulative sum list
s
containing the same valuenums[0]
. This list will help us keep track of the sum from the beginning of the array up to each index. -
Create two dictionaries,
right
andleft
, using thedefaultdict
with integer default types. Theright
dictionary will keep track of sums from the right side of the array, andleft
will do so for the left side. -
Iterate through the array, starting from index 1, to create the cumulative sum array
s
and populate theright
dictionary where each sum prior to the current index will be used as a key, and its frequency as the value. -
Set
ans
to 0. This variable will hold the count of the maximum number of ways to partition the array. -
Check if the total sum
s[-1]
is even. If yes, setans
to the number of ways to partition the array without changing an element. This can be found directly from theright
dictionary for half of the total sum, since that would mean the array can be bisected into two equal halves. -
Iterate over each element and the values from the cumulative sum list together. In each iteration, calculate the difference
d = k - x
, which represents how the sum would change if we replaced an element withk
. -
For each value
v
in the cumulative sum list and eachx
in thenums
, check if the total sum of the array after the change, which iss[-1] + d
, is even. If it is, compute the countt
as the sum of the values from theleft
andright
dictionaries at the respective adjusted sums, which would represent a valid midpoint after the change. Compare this with our currentans
and updateans
ift
is larger. -
Increment the count of the current sum in the
left
dictionary by 1, and decrement the count of the current sum in theright
dictionary by 1, reflecting that we are moving from right to left in terms of possible pivots. -
Finally, return the value stored in
ans
, which represents the maximum ways we can partition the array after making at most one change.
The algorithm efficiently counts the number of ways to partition the array by maintaining cumulative sums and dynamically adjusting the counts when considering the impact of one element change.
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 consider an example array nums
as [1, 2, 3, 4, 6]
and suppose we want to change one element to k = 5
. We want to calculate the maximum number of ways we can partition the array such that the sum of elements on either side of the pivot is equal.
-
Initialize the cumulative sum list
s
. After iterating overnums
,s
will be[1, 3, 6, 10, 16]
. -
Create two dictionaries,
right
andleft
, using thedefaultdict(int)
. -
Populate the
right
dictionary, recording the frequence of sums to the right side of the array so that it looks like this:{16: 1, 15: 1, 13: 1, 10: 1, 6: 1}
before any changes, signifying that the sum 16 occurs once, 15 occurs once, and so on. -
Set
ans
to 0, ready to hold the maximum number of partitions. -
The total sum
s[-1]
is 16, which is not even, so we cannot initially partition the array without changing an element. -
Now, iterate over
nums
ands
:- At index 0,
x = 1
, the differenced = k - x = 5 - 1 = 4
. The total sum after the change would be16 + 4 = 20
, which is even. - At index 1,
x = 2
,d = 5 - 2 = 3
. The total sum would be16 + 3 = 19
, which is not even, so no partition is possible here. - Continuing this process, we find that for index 2,
x = 3
,d = 5 - 3 = 2
, and the total sum is even at18
, suggesting a potential partition.
- At index 0,
-
When
x = 3
andv = 6
at index 2, check for potential partitions:- The left sum would be
6 + 2 = 8
, and the right sum (excluding the current element) would also need to be 8 for a valid partition. - We add
1
toleft[8]
as this sum has now occurred once. - We decrease
right[10]
to0
since we have used that partition possibility. - We find that the partition could occur at index 3, since the sums on either side would then be equal.
- The left sum would be
-
Increment the left dictionary and decrement the right dictionary as we move along the array and continue checking for partitions after each element.
-
Return the value stored in
ans
, which is the maximum ways we can partition the array. In this case,ans
would be updated to1
as we found a valid partition when we considered changing the third element to5
, which would make the sums on either side of the pivot equal.
This walkthrough demonstrates how the algorithm works in a practical example, changing one element to k
and finding the maximum number of partitions where the sums on either side of the pivot are equal.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def waysToPartition(self, nums: List[int], k: int) -> int:
5 # Determine the number of elements in the list.
6 num_elements = len(nums)
7
8 # Initialize the prefix sum array.
9 prefix_sums = [nums[0]] * num_elements
10
11 # Create a defaultdict for counting right partitions.
12 right_partitions_counts = defaultdict(int)
13
14 # Calculate the prefix sums and populate the right partitions.
15 for i in range(1, num_elements):
16 prefix_sums[i] = prefix_sums[i - 1] + nums[i]
17 right_partitions_counts[prefix_sums[i - 1]] += 1
18
19 # Initialize the answer to 0.
20 max_possible_ways = 0
21
22 # Check if the total sum is even and set the initial maximum possible ways if true.
23 if prefix_sums[-1] % 2 == 0:
24 max_possible_ways = right_partitions_counts[prefix_sums[-1] // 2]
25
26 # Create a defaultdict for counting left partitions.
27 left_partitions_counts = defaultdict(int)
28
29 # Iterate over the list to find the number of ways we can partition.
30 for prefix_sum, num in zip(prefix_sums, nums):
31 diff = k - num
32
33 # Check if the adjusted total sum is even and update the maximum possible ways.
34 if (prefix_sums[-1] + diff) % 2 == 0:
35 total_ways = left_partitions_counts[(prefix_sums[-1] + diff) // 2] \
36 + right_partitions_counts[(prefix_sums[-1] - diff) // 2]
37 max_possible_ways = max(max_possible_ways, total_ways)
38
39 # Update the left and right partitions counts.
40 left_partitions_counts[prefix_sum] += 1
41 right_partitions_counts[prefix_sum] -= 1
42
43 # Return the maximum number of ways to partition the list.
44 return max_possible_ways
45
1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5 public int waysToPartition(int[] nums, int k) {
6 // Initialize the length of the input array.
7 int length = nums.length;
8 // Prefix sum array to keep track of the sums.
9 int[] prefixSums = new int[length];
10 // Initializing the prefix sum array with the first element.
11 prefixSums[0] = nums[0];
12 // A map to store count of prefix sums to the right of a partition.
13 Map<Integer, Integer> rightPartitions = new HashMap<>();
14 // Calculate the prefix sums and populate the right partitions map.
15 for (int i = 0; i < length - 1; ++i) {
16 rightPartitions.merge(prefixSums[i], 1, Integer::sum);
17 prefixSums[i + 1] = prefixSums[i] + nums[i + 1];
18 }
19 // Initialize the max number of ways to partition.
20 int maxWays = 0;
21 // Check if the total sum is even. If yes, there could exist a partition.
22 if (prefixSums[length - 1] % 2 == 0) {
23 maxWays = rightPartitions.getOrDefault(prefixSums[length - 1] / 2, 0);
24 }
25 // A map to store count of prefix sums to the left of a partition.
26 Map<Integer, Integer> leftPartitions = new HashMap<>();
27 // Evaluating each possible partition.
28 for (int i = 0; i < length; ++i) {
29 // Calculate the difference between the target and the current element.
30 int difference = k - nums[i];
31 // Check if after replacing nums[i] with k makes the sum even.
32 if ((prefixSums[length - 1] + difference) % 2 == 0) {
33 int t = leftPartitions.getOrDefault((prefixSums[length - 1] + difference) / 2, 0)
34 + rightPartitions.getOrDefault((prefixSums[length - 1] - difference) / 2, 0);
35 // Update the max ways to the larger of the current max ways and the temporary count.
36 maxWays = Math.max(maxWays, t);
37 }
38 // Update the maps for the next iteration.
39 leftPartitions.merge(prefixSums[i], 1, Integer::sum);
40 rightPartitions.merge(prefixSums[i], -1, Integer::sum);
41 }
42 // Return the maximum number of ways we can partition.
43 return maxWays;
44 }
45}
46
1class Solution {
2public:
3 int waysToPartition(vector<int>& nums, int k) {
4 int totalNumbers = nums.size(); // Renamed for clarity.
5
6 // This array will hold the cumulative sum from index 0 to 'i'.
7 vector<long long> cumulativeSum(totalNumbers, 0);
8 cumulativeSum[0] = nums[0];
9
10 // Maps to keep track of number of ways to partition on the right, and on the left.
11 unordered_map<long long, int> rightPartitions;
12
13 // Initialize the right partitions map and populate cumulative sum array.
14 for (int i = 0; i < totalNumbers - 1; ++i) {
15 rightPartitions[cumulativeSum[i]]++;
16 cumulativeSum[i + 1] = cumulativeSum[i] + nums[i + 1];
17 }
18
19 // Will hold the maximum number of ways to partition array.
20 int maxWays = 0;
21
22 // Check if the total sum is even and update ways accordingly.
23 if (cumulativeSum[totalNumbers - 1] % 2 == 0) {
24 maxWays = rightPartitions[cumulativeSum[totalNumbers - 1] / 2];
25 }
26
27 unordered_map<long long, int> leftPartitions; // For partitions on the left.
28
29 // Iterate over each number to consider it as the partition point.
30 for (int i = 0; i < totalNumbers; ++i) {
31 // Check if by replacing nums[i] with k, whether we can increase the number of ways.
32 int difference = k - nums[i];
33 if ((cumulativeSum[totalNumbers - 1] + difference) % 2 == 0) {
34 int currentWays =
35 leftPartitions[(cumulativeSum[totalNumbers - 1] + difference) / 2] +
36 rightPartitions[(cumulativeSum[totalNumbers - 1] - difference) / 2];
37 maxWays = max(maxWays, currentWays);
38 }
39
40 // Update the maps to reflect the change in partition position.
41 leftPartitions[cumulativeSum[i]]++;
42 rightPartitions[cumulativeSum[i]]--;
43 }
44 return maxWays; // Return the maximum number of ways found.
45 }
46};
47
1// Function to calculate the number of ways to partition a given array
2function waysToPartition(nums: number[], k: number): number {
3 let totalNumbers: number = nums.length; // Renaming for clarity
4
5 // This array will hold the cumulative sum from index 0 to 'i'.
6 let cumulativeSum: number[] = new Array(totalNumbers).fill(0);
7 cumulativeSum[0] = nums[0];
8
9 // Maps to keep track of number of ways to partition on the right, and on the left.
10 let rightPartitions: Map<number, number> = new Map<number, number>();
11
12 // Initialize the right partitions map and populate cumulative sum array.
13 for (let i: number = 0; i < totalNumbers - 1; ++i) {
14 rightPartitions.set(cumulativeSum[i], (rightPartitions.get(cumulativeSum[i]) || 0) + 1);
15 cumulativeSum[i + 1] = cumulativeSum[i] + nums[i + 1];
16 }
17
18 // Will hold the maximum number of ways to partition array.
19 let maxWays: number = 0;
20
21 // Check if the total sum is even and update ways accordingly.
22 if (cumulativeSum[totalNumbers - 1] % 2 === 0) {
23 maxWays = rightPartitions.get(cumulativeSum[totalNumbers - 1] / 2) || 0;
24 }
25
26 let leftPartitions: Map<number, number> = new Map<number, number>(); // For partitions on the left.
27
28 // Iterate over each number to consider it as the partition point.
29 for (let i: number = 0; i < totalNumbers; ++i) {
30 // Check if by replacing nums[i] with k, whether we can increase the number of ways.
31 let difference: number = k - nums[i];
32 if ((cumulativeSum[totalNumbers - 1] + difference) % 2 === 0) {
33 let currentWays: number =
34 (leftPartitions.get((cumulativeSum[totalNumbers - 1] + difference) / 2) || 0) +
35 (rightPartitions.get((cumulativeSum[totalNumbers - 1] - difference) / 2) || 0);
36 maxWays = Math.max(maxWays, currentWays);
37 }
38
39 // Update the maps to reflect the change in partition position.
40 leftPartitions.set(cumulativeSum[i], (leftPartitions.get(cumulativeSum[i]) || 0) + 1);
41 rightPartitions.set(cumulativeSum[i], (rightPartitions.get(cumulativeSum[i]) || 1) - 1);
42 }
43 return maxWays; // Return the maximum number of ways found.
44}
45
Time and Space Complexity
Time Complexity
The given Python function waysToPartition
performs a series of operations on an array to determine the number of ways it can be partitioned such that the sums of the elements on either side of the partition are equal, with the option of changing one element to k
.
First, the function creates an accumulated sum array s
of the input array nums
. This operation traverses the array once and has a time complexity of O(n)
, where n
is the length of the input array.
Next, the function initializes a right
dictionary (from the collections.defaultdict
class) to count the occurrences of each prefix sum as we iterate from the end to the beginning of the accumulated sum array. Filling this dictionary also takes O(n)
.
The function then checks a special case where the total sum of the array is even, and a partition is possible without any change. Checking and updating the count takes constant time O(1)
.
Following this, the function iterates through nums
and its accumulated sum s
simultaneously and updates two dictionaries: left
and right
. Each iteration involves a constant amount of work - updating dictionaries and a few arithmetic operations. Since the iteration happens n
times, we get O(n)
.
Within the same loop, the partition count is updated based on whether it's possible to create an equal partition by changing the current number to k
. The checks and updates are performed in constant time for each iteration.
Considering all these operations together, since they are sequential, the total time complexity is O(n)
+ O(n)
+ O(1)
+ O(n)
= O(n)
.
Space Complexity
The space complexity of the function involves the space taken by the input nums
, the accumulated sum array s
, and the left
and right
dictionaries.
The accumulated sum array s
has the same length as nums
, contributing O(n)
space complexity.
Both left
and right
dictionaries could, in the worst case, store a distinct sum for every prefix and suffix, which also contributes up to O(n)
space complexity.
Therefore, the total space complexity is the sum of the space complexities of these data structures, O(n)
+ O(n)
+ O(n)
= O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
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