Skip to main content
Talentd

Maximum Number of Ways to Partition an Array - Solution & Explanation

HardArrayHash TableCountingEnumeration16 min readAsked at: Salesforce, Google
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:

  • 1 <= pivot < n
  • nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.

Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.

 

Example 1:

Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.

Example 2:

Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.

Example 3:

Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.

 

Constraints:

  • n == nums.length
  • 2 <= n <= 105
  • -105 <= k, nums[i] <= 105

Approach Overview

Problem Overview: You are given an integer array and a value k. You may change at most one element to k. After the change, count how many ways the array can be partitioned into two parts with equal sums. The goal is to maximize this count.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

The direct strategy tries every possible modification and checks all partition points. For each index, temporarily replace nums[i] with k, recompute the total sum, then iterate through the array to count indices where the prefix sum equals half of the total. This requires recalculating prefix sums repeatedly, leading to O(n) work per modification and O(n) possible modifications. While conceptually simple, the O(n²) runtime becomes impractical for large inputs. This approach mainly helps you understand how partition points depend on prefix sums and total sum differences.

Approach 2: Prefix Sum Calculation (O(n) time, O(n) space)

The key observation: a partition at index i is valid when the left prefix sum equals the right suffix sum. Let total be the sum of the array and prefix[i] the sum up to index i. The difference diff = prefix[i] - (total - prefix[i]) determines whether a partition is balanced. Using a frequency map of these differences lets you count valid splits quickly. If you change nums[j] to k, the total sum shifts by delta = k - nums[j]. That adjustment affects partitions differently depending on whether they lie to the left or right of j. By precomputing prefix differences and tracking counts in hash maps, you can evaluate the effect of each modification in constant time. This relies heavily on prefix sum computation and hash table frequency tracking.

Approach 3: Two-Pass Solution with Adjustment Maps (O(n) time, O(n) space)

An optimized implementation performs two passes across the array. First pass: compute prefix sums and build a map counting how many partition points produce each difference value. Second pass: simulate changing each index to k. Maintain two maps—one for partition differences to the left of the current index and one for the right. When applying the modification delta, partitions on the left require a difference of delta, while partitions on the right require -delta. A constant-time lookup in both maps gives the number of valid partitions for that modification. Update maps as you move forward. This method combines array traversal with prefix-difference counting to achieve linear time.

Recommended for interviews: Interviewers expect the prefix-sum + hash-map strategy with difference counting. Explaining the brute-force method first shows understanding of how partitions work. Transitioning to the linear-time solution demonstrates algorithmic optimization and familiarity with prefix-sum transformations.

Approach 1: Prefix Sum Calculation

This approach employs prefix sums to quickly determine the sum of any given subarray. By precomputing these sums, we can efficiently check the pivot conditions across the array in linear time.

The idea is to compute prefix sums for the array, then iterate through each potential pivot point to see if the sums match. Also, consider changing one element to the given k and see how many more valid partition points it provides.

The code calculates prefix sums for the array and maintains balances while checking potential pivots. Using a dictionary, we keep track of occurrences of prefix sums to adjust our pivots.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n), where n is the length of the input array, due to a single pass to compute prefix sums and another to adjust with k.
Space Complexity: O(n), as we store prefix sums in a dictionary.

Try this approach in the editor →

Approach 2: Two-Pass Solution with Adjustment

A different perspective on this problem uses a two-pass approach. First, find all valid pivot points without changes, then reassess the adjusted sums by testing each element change to k to find additional valid pivot positions.

This JavaScript solution calculates the prefix sums and potential pivots in two separate loops. It first finds the original maximum partition ways and then tests changes to each element to find additional partitions.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n), as it involves two separate linear passes through the array.
Space Complexity: O(1), since no extra data structures are used apart from primitive accumulators.

Try this approach in the editor →

Approach 3: Prefix Sum + Hash Table

We can preprocess to get the prefix sum array s corresponding to the array nums, where s[i] represents the sum of the array nums[0,...i-1]. Therefore, the sum of all elements in the array is s[n - 1].

If we do not modify the array nums, the condition for the sums of the two subarrays to be equal is that s[n - 1] must be even. If s[n - 1] is even, then we calculate ans = \frac{right[s[n - 1] / 2]}{2}.

If we modify the array nums, we can enumerate each modification position i, change nums[i] to k, then the change in the total sum of the array is d = k - nums[i]. At this time, the sum of the left part of i remains unchanged, so the legal split must satisfy s[i] = s[n - 1] + d - s[i], that is, s[i] = \frac{s[n - 1] + d}{2}. Each prefix sum of the right part has increased by d, so the legal split must satisfy s[i] + d = s[n - 1] + d - (s[i] + d), that is, s[i] = \frac{s[n - 1] - d}{2}. We use hash tables left and right to record the number of times each prefix sum appears in the left and right parts, respectively. Then we can calculate ans = max(ans, left[\frac{s[n - 1] + d}{2}]) + right[\frac{s[n - 1] - d}{2}].

Finally, we return ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Calculation

Time Complexity: O(n), where n is the length of the input array, due to a single pass to compute prefix sums and another to adjust with k.
Space Complexity: O(n), as we store prefix sums in a dictionary.

Two-Pass Solution with Adjustment

Time Complexity: O(n), as it involves two separate linear passes through the array.
Space Complexity: O(1), since no extra data structures are used apart from primitive accumulators.

Prefix Sum + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Understanding the mechanics of partition sums or when constraints are very small
Prefix Sum with Difference CountingO(n)O(n)General optimal solution using prefix sums and hash maps
Two-Pass Adjustment with MapsO(n)O(n)Interview-ready implementation that evaluates each modification in constant time

Video Solution

LeetCode 2025. Maximum Number of Ways to Partition an Array • Happy Coding • 4,070 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Number of Ways to Partition an Array easy or hard?
Maximum Number of Ways to Partition an Array is classified as a Hard problem on LeetCode. The challenge comes from recognizing how a single value change shifts partition sums and designing a prefix-difference counting method to evaluate all possibilities efficiently.
Maximum Number of Ways to Partition an Array Python/Java solution
Most implementations follow the same pattern across languages: compute prefix sums, track difference frequencies in hash maps, and simulate replacing each element with k. The logic translates directly to Python dictionaries, Java HashMap, or C++ unordered_map with O(n) complexity.
How to solve Maximum Number of Ways to Partition an Array in O(n)?
First compute the total sum and prefix sums. For each partition index, store the difference between the left and right sums in a hash map. When considering changing nums[i] to k, calculate the delta and use two maps to count partitions that become balanced on the left and right. Each evaluation takes O(1), producing an O(n) algorithm.
What is the best approach for Maximum Number of Ways to Partition an Array?
The best approach uses prefix sums and hash maps to track partition differences. By computing prefix sums once and storing difference frequencies, you can evaluate the effect of replacing each element with k in constant time. This results in an overall O(n) time and O(n) space solution.
Is Maximum Number of Ways to Partition an Array asked at Google/Amazon/Meta?
This problem pattern appears in interviews at large tech companies including Google, Amazon, and Meta. It tests prefix sums, hash map counting, and the ability to transform a brute-force partition problem into a linear-time solution.
What data structure is used in Maximum Number of Ways to Partition an Array?
The core data structures are prefix sums and hash maps (frequency tables). Prefix sums allow constant-time subarray sum checks, while hash maps store counts of partition differences so the algorithm can quickly determine how many partitions become valid after a modification.
What is the time complexity of Maximum Number of Ways to Partition an Array?
The optimal solution runs in O(n) time with O(n) extra space. The algorithm computes prefix sums, stores difference counts in hash maps, and scans the array once more to evaluate the effect of changing each element to k.

Ready to solve this problem?

Practice Maximum Number of Ways to Partition an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Partition Equal Subset Sum

Next

Partition to K Equal Sum Subsets