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 < nnums[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.length2 <= n <= 105-105 <= k, nums[i] <= 105The key idea is to analyze valid partition points where the sum of the left subarray equals the sum of the right subarray. Using a prefix sum, we can compute the difference diff = leftSum - rightSum for every possible partition. A partition is valid when diff = 0.
The twist is that we are allowed to replace at most one element with k. Changing an element modifies the total sum by delta = k - nums[i]. This change affects all partitions to the right of that index. To efficiently track how many partitions become valid, we maintain frequency counts of diff values using hash tables for partitions on the left and right.
By iterating through the array and updating these counts, we can evaluate how many partitions become valid if the replacement occurs at each index. This allows us to compute the maximum number of valid partitions in O(n) time using prefix sums and hash maps, while keeping space usage linear.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Hash Map Counting | O(n) | O(n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
A pivot point splits the array into equal prefix and suffix. If no change is made to the array, the goal is to find the number of pivot p such that prefix[p-1] == suffix[p].
Consider how prefix and suffix will change when we change a number nums[i] to k.
When sweeping through each element, can you find the total number of pivots where the difference of prefix and suffix happens to equal to the changes of k-nums[i].
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving prefix sums, hash maps, and partition analysis frequently appear in FAANG-style interviews. This problem tests optimization, counting techniques, and understanding how local changes affect global sums.
Prefix sums allow fast computation of subarray sums and the difference between left and right partitions. This avoids recomputing sums repeatedly and enables efficient evaluation of all partition points.
Hash maps are essential for storing frequencies of partition differences. They allow constant-time lookups when determining how many partitions become valid after adjusting the array with a replacement value.
The optimal approach uses prefix sums combined with hash map counting. By tracking the difference between left and right sums for each partition, we can quickly evaluate how a single value replacement affects valid partitions in linear time.