Problem overview
The method removeMinSum receives an array of integers, nums, and a number k. You must pick exactly k numbers, some from the beginning of the array and some from the end, and the method returns the smallest sum you can get this way. Picking all k numbers from one end, or none from one end, is allowed.
In the example, nums = [-2, 5, 2, -1, 3, -10, 9, -2] and k = 4. Taking the first number and the last three gives (-2) + (-10) + 9 + (-2) = -5, and no other split of four numbers does better.
Approach: keep the best block in the middle
The direct way is to try every split: take a numbers from the front and k - a from the back, for a from 0 to k, and add them up. That works, and a prefix-sum table makes each split cost O(1).
This lesson uses a different view. Whatever you pick from the two ends, the numbers you do not pick form one contiguous block in the middle, and that block always has exactly n - k numbers. The picked sum and the block sum add up to the total of the array, so:
picked = total - block
To make picked as small as possible, make block as large as possible. The task becomes: find the contiguous window of n - k numbers with the maximum sum, then subtract that sum from the total.
In the example the total is 4 and the windows of four numbers have sums 4, 9, -6, 1 and 0. The best window is [5, 2, -1, 3] with sum 9, and the answer is 4 - 9 = -5. This matches the picked numbers in the statement: the first number, -2, and the last three.
A window sum doesn't need to be recomputed from scratch. When the window moves one position to the right, one number enters and one leaves, so the sum changes by two additions. That is the sliding window technique, and it makes the whole algorithm one pass over the array.
Step by step
- Compute the window length.
windowisnums.count - k. It is alet, because it never changes. The name must be new: a Swift parameter such askis a constant and can't be reassigned. - Keep the current window's sum in
rollingSum, avarstarting at 0. - Keep the sum of the whole array in
totalSum, also starting at 0. Adding to it inside the main loop saves a second pass. - Track the best window sum in
maxSum. It starts atInt.min, the smallest possibleInt, so that the first full window replaces it. Starting at 0 would give wrong answers when every window has a negative sum. - Loop over every index
iin0..<nums.count, a half-open range that stops before the count. - Add
nums[i]tototalSum. - Add
nums[i]torollingSum. The number atijoins the window. - Wait for a full window. The first
windownumbers have been added whenireacheswindow - 1, so the check isi >= window - 1. - Record the window. Inside the
if,maxSumbecomes the larger of itself androllingSum. - Slide the window. Subtract the oldest number,
nums[i - window + 1], fromrollingSum. The window that ends atistarts ati - window + 1. After this,rollingSumcovers the numbers that precede the next index, and the next iteration adds the new one. - Return
totalSum - maxSumafter the loop.
The solution in Swift
class Solution {
func removeMinSum(_ nums: [Int], _ k: Int) -> Int {
let window = nums.count - k
var rollingSum = 0
var totalSum = 0
var maxSum = Int.min
for i in 0..<nums.count {
totalSum += nums[i]
rollingSum += nums[i]
if i >= window - 1 {
maxSum = max(maxSum, rollingSum)
rollingSum -= nums[i - window + 1]
}
}
return totalSum - maxSum
}
}
Swift details worth knowing:
letversusvar.windowis fixed after it is set, so it is alet. The three running values change in the loop and needvar. The compiler warns when avaris never changed, which helps catch mistakes.- Parameters are constants. Writing
k = nums.count - kinside the method doesn't compile. A new constant is the idiomatic fix. Int.minis a sentinel, not a number to calculate with. It is replaced by the first full window before anything uses it. Adding to it, or negating it, would trap, because Swift stops the program when integer arithmetic overflows.- The global
max.max(maxSum, rollingSum)is the standard library function that returns the larger of two values. - Half-open ranges.
0..<nums.countexcludes the upper bound. An empty array gives the empty range0..<0, which is valid.
Complexity
Time: O(n). The loop visits each index once and does a constant amount of work in each pass. The sliding update replaces the O(window) sum that a naive version would compute for each window.
Space: O(1). Only a few integer variables are used, however large the array is.
Edge cases and common mistakes
k = 0. The window is the whole array. It is full at the last index, somaxSumequalstotalSumand the result is 0, which is the sum of no numbers. For[4, 7, 1]withk = 0the method returns 0.kequal to the array length. The window length is 0, the checki >= window - 1is true from the start, and the slide step readsnums[i + 1], which runs past the end of the array. In Swift an out-of-range index crashes the program. The code is meant forksmaller thannums.count; withk == nums.countthe answer is simply the total sum, so a guard for that case would be needed.- All negative numbers. For
[-5, -3, -4]withk = 2the window has one number, and the best one is-3. The total is-12, so the answer is-9. StartingmaxSumat 0 would pick an empty window and return-12. - Subtracting before checking the window. If the oldest number is removed on every iteration, the window never grows to full size.
- Off-by-one in the oldest index. The oldest number of a window ending at
iisnums[i - window + 1]. Usingi - windowremoves the wrong value. - Taking the wrong side. The loop finds the best block to keep. Returning
maxSumalone gives the kept sum, not the picked sum.
Testing
[-2, 5, 2, -1, 3, -10, 9, -2]withk = 4gives-5.[1, 2, 3]withk = 1gives1.[5, -3, 4]withk = 2gives1.[-5, -3, -4]withk = 2gives-9.[4, 7, 1]withk = 0gives0.
