Maximum Subarray Sum After at Most K Swaps solution and explanation
Google
The problem
You are given an integer array nums and an integer k.
You are allowed to perform at most k swap operations on the array.
In one swap operation, you may choose any two indices i and j and swap nums[i] and nums[j].
Return an integer denoting the maximum possible subarray sum after performing the swaps.
Example 1:
Input: nums = [1,-1,0,2], k = 1
Output: 3
Explanation:
- We can swap on indices 1 and 3, resulting in the array
[1, 2, 0, -1]. - The subarray
[1, 2]has a sum of 3, which is the maximum possible subarray sum after at mostk = 1 swap.
Example 2:
Input: nums = [4,3,2,4], k = 2
Output: 13
Explanation:
The maximum possible subarray sum after at most k = 2 swaps is the sum of the entire array, which is 13.
Example 3:
Input: nums = [-1,-2], k = 0
Output: -1
Explanation:
k = 0swaps are allowed.- The possible subarrays are
[-1],[-2], and[-1, -2], with sums -1, -2, and -3 respectively. - Among these sums, the maximum is -1.
Constraints:
1 <= nums.length <= 1500-105 <= nums[i] <= 1050 <= k <= nums.length
Approach overview
Problem Overview: Given an integer array and an integer k, choose a subarray and perform at most k swaps between elements inside the subarray and elements outside it. The goal is to maximize the final sum of the chosen subarray.
Approach 1: Brute Force Subarray Enumeration (O(n2 log n) time, O(n) space)
Enumerate every possible subarray using two pointers. For each subarray, collect its elements and the elements outside the subarray. Sort the subarray in ascending order and the outside elements in descending order. Greedily perform up to k swaps where an outside element is larger than the smallest element currently inside the subarray. Each swap increases the sum. This approach directly models the optimal swap decision but becomes expensive because every subarray requires sorting or heap operations.
Approach 2: Greedy with Heaps for Each Subarray (O(n2 log n) time, O(n) space)
Instead of sorting every time, maintain two heaps while expanding the subarray: a min-heap for elements inside the window and a max-heap for elements outside it. The smallest inside element represents the best candidate to swap out, while the largest outside element represents the best candidate to swap in. Perform up to k beneficial swaps where the outside value is greater. Heap operations reduce repeated sorting overhead and model the greedy insight: always replace the worst element in the subarray with the best available outside value.
Approach 3: Sliding Window with Dynamic Candidate Heaps (O(n log n) time, O(n) space)
The optimal strategy maintains the current window and dynamically tracks swap candidates using priority queues. Keep a min-heap of the smallest elements inside the window and a max-heap of the largest elements outside. As the window expands or shrinks, update heap membership using lazy deletion. For the current window, compute the best improvement by selecting up to k profitable swaps between the two heaps. This avoids rebuilding structures for every subarray and reduces the complexity to roughly O(n log n). The core idea is greedy replacement combined with efficient window maintenance.
Conceptually this problem combines greedy decisions with heap-based candidate tracking from priority queues. Efficient window traversal also resembles patterns used in sliding window problems.
Recommended for interviews: Start by explaining the brute force idea of checking every subarray and swapping the smallest inside elements with the largest outside elements. Then move to the heap-based optimization. Interviewers expect you to recognize the greedy swap rule and use heaps to efficiently track candidates, bringing the solution down to roughly O(n log n).
Solution
Thinking
A swap helps the chosen subarray only when it brings in a larger value from outside. With
n \le 1500every segment can be enumerated; sorting the inside and the outside of each one would add anotherO(n log n)and push the total toO(n^3 log n).Once the inside is ordered ascending and the outside descending, the gains are monotone. If the
t-th pair still has the smaller value inside, the firsttpairs are all worth swapping; once a pair does not increase the sum, later pairs do not either. How many swaps to take can be found by binary search.After coordinate compression, two Fenwick trees store the counts and sums inside and outside the segment, so the smallest or largest values can be read by rank. With the left end fixed, extending the right end moves the current value from the outside tree into the inside tree.
Deduplicate and sort the values in nums, and use that list as the compressed value domain. Two Fenwick trees keep, for the inside and the outside, how many times each value occurs and what those occurrences sum to. Either tree can report the k-th smallest value, or the sum of the smallest or largest several values, in O(log n).
Enumerate the left end l. Every element starts outside the segment. The right end r runs from l to n - 1: move nums[r] from the outside tree into the inside tree and add it to the segment sum s.
Let c be the number of elements inside. At most t = min(k, c, n - c) swaps are possible. Binary search the largest mid in [1, t] such that the mid-th smallest inside value is strictly smaller than the mid-th largest outside value, and call it best. If best > 0, a candidate is s plus the sum of the best largest outside values, minus the sum of the best smallest inside values. The answer is the maximum candidate over all segments.
The time complexity is O(n^2 log^2 n) and the space complexity is O(n), where n is the length of nums.
class Fenwick {
int n;
int[] count;
long[] sum;
Fenwick(int n) {
this.n = n;
count = new int[n + 1];
sum = new long[n + 1];
}
void add(int idx, int cnt, long val) {
++idx;
while (idx <= n) {
count[idx] += cnt;
sum[idx] += val;
idx += idx & -idx;
}
}
int prefixCount(int idx) {
int res = 0;
while (idx > 0) {
res += count[idx];
idx -= idx & -idx;
}
return res;
}
long prefixSum(int idx) {
long res = 0;
while (idx > 0) {
res += sum[idx];
idx -= idx & -idx;
}
return res;
}
int kth(int k) {
int idx = 0;
for (int bit = Integer.highestOneBit(n); bit > 0; bit >>= 1) {
int next = idx + bit;
if (next <= n && count[next] < k) {
idx = next;
k -= count[next];
}
}
return idx;
}
long sumSmallest(int k, int[] values) {
if (k <= 0) {
return 0;
}
int pos = kth(k);
int before = prefixCount(pos);
return prefixSum(pos) + (long) (k - before) * values[pos];
}
long sumLargest(int k, int[] values) {
int total = prefixCount(n);
if (k <= 0) {
return 0;
}
if (k >= total) {
return prefixSum(n);
}
return prefixSum(n) - sumSmallest(total - k, values);
}
}
class Solution {
public long maxSum(int[] nums, int k) {
int n = nums.length;
int[] sorted = nums.clone();
Arrays.sort(sorted);
int m = 0;
for (int i = 0; i < n; ++i) {
if (i == 0 || sorted[i] != sorted[i - 1]) {
sorted[m++] = sorted[i];
}
}
int[] values = Arrays.copyOf(sorted, m);
int[] idx = new int[n];
for (int i = 0; i < n; ++i) {
idx[i] = Arrays.binarySearch(values, nums[i]);
}
long ans = Long.MIN_VALUE;
for (int l = 0; l < n; ++l) {
Fenwick inside = new Fenwick(m);
Fenwick outside = new Fenwick(m);
for (int i = 0; i < n; ++i) {
outside.add(idx[i], 1, nums[i]);
}
long window = 0;
for (int r = l; r < n; ++r) {
outside.add(idx[r], -1, -nums[r]);
inside.add(idx[r], 1, nums[r]);
window += nums[r];
int inCnt = r - l + 1;
int outCnt = n - inCnt;
int limit = Math.min(k, Math.min(inCnt, outCnt));
if (limit == 0) {
ans = Math.max(ans, window);
continue;
}
int lo = 1;
int hi = limit;
int best = 0;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
int small = inside.kth(mid);
int large = outside.kth(outCnt - mid + 1);
if (values[small] < values[large]) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if (best == 0) {
ans = Math.max(ans, window);
} else {
long cand = window + outside.sumLargest(best, values)
- inside.sumSmallest(best, values);
ans = Math.max(ans, cand);
}
}
}
return ans;
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2 log n) | O(n) | Useful for reasoning about the swap strategy and validating correctness |
| Greedy with Heaps per Subarray | O(n^2 log n) | O(n) | Better brute force where repeated sorting is replaced by heap operations |
| Sliding Window + Candidate Heaps | O(n log n) | O(n) | Best general solution for large arrays where rebuilding structures per subarray is too slow |
Frequently asked questions
Is Maximum Subarray Sum After at Most K Swaps easy or hard?
Maximum Subarray Sum After at Most K Swaps is classified as Hard because it combines multiple concepts: subarray enumeration, greedy replacement logic, and heap-based candidate tracking. Efficiently managing swap candidates across many possible subarrays is the main challenge.
Maximum Subarray Sum After at Most K Swaps Python/Java solution
Most implementations use heaps or priority queues available in standard libraries. Python typically uses heapq with sign inversion for max-heaps, while Java uses PriorityQueue with custom comparators. The algorithm greedily performs up to k profitable swaps while maintaining heap structures.
How to solve Maximum Subarray Sum After at Most K Swaps in O(n)?
Pure O(n) is difficult because selecting the best swap candidates requires ordered comparisons. Most practical solutions use heaps or balanced structures to track the smallest inside elements and largest outside elements, leading to O(n log n) time. The greedy insight is to always replace the smallest element inside the subarray with the largest available outside value.
What is the best approach for Maximum Subarray Sum After at Most K Swaps?
The most efficient approach combines greedy swapping with priority queues. Maintain the smallest elements inside the chosen subarray and the largest elements outside using heaps, then perform up to k beneficial swaps. This allows selecting the best improvements without sorting repeatedly and typically runs in O(n log n) time.
Is Maximum Subarray Sum After at Most K Swaps asked at Google/Amazon/Meta?
Problems combining maximum subarray logic with greedy swaps and heaps appear in interviews at large tech companies including Google, Amazon, and Meta. Variants test your ability to combine sliding window techniques with priority queues and greedy optimization.
What data structure is used in Maximum Subarray Sum After at Most K Swaps?
Priority queues (min-heap and max-heap) are the key data structures. A min-heap tracks the smallest elements inside the current subarray while a max-heap tracks the largest elements outside. These structures allow efficient selection of the best swap candidates.
What is the time complexity of Maximum Subarray Sum After at Most K Swaps?
The optimized heap-based approach runs in O(n log n) time with O(n) space. A brute force method that checks every subarray and sorts candidates requires O(n^2 log n) time. The heap optimization avoids repeated sorting and tracks swap candidates efficiently.