Given an integer array nums and an integer k, modify the array in the following way:
i and replace nums[i] with -nums[i].You should apply this process exactly k times. You may choose the same index i multiple times.
Return the largest possible sum of the array after modifying it in this way.
Example 1:
Input: nums = [4,2,3], k = 1 Output: 5 Explanation: Choose index 1 and nums becomes [4,-2,3].
Example 2:
Input: nums = [3,-1,0,2], k = 3 Output: 6 Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].
Example 3:
Input: nums = [2,-3,-1,5,-4], k = 2 Output: 13 Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].
Constraints:
1 <= nums.length <= 104-100 <= nums[i] <= 1001 <= k <= 104Problem Overview: You are given an integer array and allowed to negate (multiply by -1) exactly k elements. The same index can be chosen multiple times. The goal is to maximize the final sum of the array after performing these operations.
Approach 1: Sorting and Greedy Negation (O(n log n) time, O(1) extra space)
This approach relies on a greedy observation: negating negative numbers increases the total sum. Start by sorting the array so the most negative values appear first. Iterate from left to right and flip each negative number while k > 0. Each negation turns a loss into a gain. If you still have remaining operations after all negatives are handled, the optimal move depends on whether k is odd. When k is odd, negate the element with the smallest absolute value to minimize the damage. Sorting guarantees that the smallest values are processed first, making the greedy decision straightforward. This solution is simple and deterministic, which makes it the most common interview answer when discussing greedy techniques combined with sorting.
Approach 2: Using Priority Queue (Min-Heap) (O(k log n) time, O(n) space)
A min-heap provides a dynamic way to always access the smallest element in the array. Insert all numbers into a min-heap. For each of the k operations, extract the smallest value, negate it, and push it back into the heap. This guarantees that the currently most harmful value is flipped each time. The heap automatically reorders elements after each insertion, so you always operate on the optimal candidate. After performing k negations, sum all elements in the heap to compute the result. This method is useful when you want the algorithm to adapt after every operation rather than relying on a single sorted order. It highlights how priority queues can repeatedly expose the best greedy choice.
Recommended for interviews: The sorting-based greedy solution is typically expected. It shows that you understand the core insight: flipping negative numbers increases the sum, and a leftover odd operation should affect the smallest absolute value. Mentioning the heap approach demonstrates deeper understanding of greedy selection structures, but the sorted greedy implementation is simpler and runs in O(n log n) time with minimal overhead.
Approach 1: Sorting and Greedy Negation
This approach involves sorting the array first, which helps address the negativity in a prioritized fashion. By sorting, negative numbers are brought to the forefront. The plan is to turn all negative numbers positive for immediate gains. After flipping the necessary negatives or using up the flips, if flips remain, we aim them repeatedly at the smallest number in terms of absolute value to ensure no more productive use of a negation exists.
The C solution uses the standard qsort to sort the array. The core logic emphasizes negating the smallest negative numbers first, iterating through the array until either all negative numbers are converted or k negations are exhausted. Should negations remain post initial conversion, an odd count of k means a further single alteration is advantageous, specifically targeting the smallest number.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in-place.
Approach 2: Using Priority Queue (Min-Heap)
A priority queue (or min-heap) will provide an elegant method to always operate on the smallest element. The process involves inserting all numbers into a heap, then multiple negations individualizing the smallest available value until k operations are exhausted. This method efficiently manages both negation and retrieval of minimal elements.
The C++ implementation uses a min-heap, inserting all numbers initially. We invoke k negations, ensuring to log the negated value back into the heap, thus retaining a valid minimum tracking mechanism. The strategy processes/instruments flipping k times and sums up the remainder through a cumulative heap pop.
Time Complexity: O(n + k log n), where n is for heap initialization and k log n for operations.
Space Complexity: O(n) for the priority queue.
We observe that to maximize the sum of the array, we should try to turn the smallest negative numbers into positive numbers.
Given that the range of elements is [-100, 100], we can use a hash table cnt to count the occurrences of each element in the array nums. Then, starting from -100, we iterate through x. If x exists in the hash table, we take m = min(cnt[x], k) as the number of times to negate the element x. We then subtract m from cnt[x], add m to cnt[-x], and subtract m from k. If k becomes 0, the operation is complete, and we exit the loop.
If k is still odd and cnt[0] = 0, we need to take the smallest positive number x in cnt, subtract 1 from cnt[x], and add 1 to cnt[-x].
Finally, we traverse the hash table cnt and sum the products of x and cnt[x] to get the answer.
The time complexity is O(n + M), and the space complexity is O(M). Here, n and M are the length of the array nums and the size of the data range of nums, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Greedy Negation | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Using Priority Queue (Min-Heap) | Time Complexity: O(n + k log n), where n is for heap initialization and k log n for operations. |
| Greedy + Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Greedy Negation | O(n log n) | O(1) | Best general solution. Simple greedy logic after sorting the array. |
| Priority Queue (Min-Heap) | O(k log n) | O(n) | Useful when repeatedly selecting the smallest element after each operation. |
LeetCode 1005: Maximize Sum Of Array After K Negations - Interview Prep Ep 38 • Fisher Coder • 2,945 views views
Watch 9 more video solutions →Practice Maximize Sum Of Array After K Negations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor