Problem Statement
You are given an integer array arr of size n and an integer k. You must perform exactly k sign-flip operations. Each operation:
- Selects a single element and flips its sign (
x→-x).
The same element may be flipped multiple times, as long as the total number of flips across all elements is exactly k.
Return the maximum possible sum of the array after performing exactly k sign flips.
Constraints
1 <= n <= 2 * 10^5-10^9 <= arr[i] <= 10^91 <= k <= 10^9- The sum can exceed 32-bit range — use 64-bit (long)
Example
Input: arr = [-5, -2, -3, 6, 7], k = 3
Output: 23
Explanation: Flip -5, -2, and -3 → [5, 2, 3, 6, 7]. Sum = 23.
Input: arr = [4, 2, 1, 9], k = 1
Output: 14
Explanation: No negatives to fix. Flip the smallest absolute value (1) → [4, 2, -1, 9]. Sum = 14.
What the Interviewer Expects
This is a greedy problem with a clever parity twist at the end.
-
Greedy phase — fix the negatives first: Sort (or use a min-heap). Flip the most negative numbers to positive, one flip each, while you still have flips left AND there are negatives. Each such flip increases the sum the most.
-
The parity insight (the "gotcha"): After handling negatives (or if flips remain), you still might have leftover flips. Since flipping the SAME element twice returns it to the original (net zero effect):
- If remaining flips is even → flip any element back and forth; net effect is zero. Sum stays as is.
- If remaining flips is odd → you're forced to leave one element flipped. To lose the least, flip the element with the smallest absolute value (that costs you
2 * min_abs).
-
Key realization: "Exactly k" (not "at most k") is what forces the parity reasoning. With "at most k," you'd just stop once all negatives are fixed.
-
Complexity — O(n log n) with sorting, or O(n) using a single pass to find min absolute value + counting.
Follow-ups
- Why does "exactly k" force the parity check, while "at most k" wouldn't?
- Why do you flip the smallest-absolute-value element when a single flip is left over?
- Can you solve it in O(n) without fully sorting? (track min abs value during the greedy pass)
- What if a
0exists in the array — how does that simplify the odd-leftover case? - What if each element could only be flipped once (at most)? How does the problem change?