Start learning free

LESSON 218 OF 347 · PARTIAL SUMS #2

Remove Min Sum II in C#: Sliding Window on the Part You Keep

Practice O(n) Read the full explanation

Given an input array of integers and a number k, pick exactly k numbers, some from the beginning of the array and some from the end of it, in such a way that their sum is minimized. Return this minimum sum.

Example

Input: nums = [-2, 5, 2, -1, 3, -10, 9, -2], k = 4
Output: -5
Explanation: Pick the first and the last three numbers
             (-2) + (-10) + 9 + (-2) = -5
STEP 1 OF 11
    Ctrl + Enter to check

    C# · PARTIAL SUMS #2

    Remove Min Sum Ii in C#, explained

    Problem overview

    The method RemoveMinSum receives an int[] nums and a number k. You must pick exactly k numbers, some from the beginning of the array and some from the end, so that their sum is as small as possible. The method returns that sum.

    In the example, nums = [-2, 5, 2, -1, 3, -10, 9, -2] and k = 4. Picking the first number and the last three gives -2 + (-10) + 9 + (-2) = -5, which is the minimum.

    Approach: minimise what you pick by maximising what you leave

    The numbers you pick sit at the two ends. The numbers you don't pick form one contiguous block in the middle, and since exactly k numbers are picked, the block has exactly n - k elements. Picked sum plus block sum is always the total of the array. So:

    picked sum = total - block sum

    To make the picked sum as small as possible, make the block sum as large as possible. That turns the problem into one you may already know: find the maximum sum of a window of fixed length n - k. A sliding window does this in a single pass, and the answer is the total minus the best window.

    In the example, the block has 4 elements. The five windows sum to 4, 9, -6, 1 and 0. The best is 9, the window [5, 2, -1, 3]. The array total is 4, and 4 - 9 = -5, which matches.

    Step by step

    1. Reassign k. The code sets k = nums.Length - k, so from now on k is the length of the block you keep. Parameters are ordinary local variables in C#, so assigning to one is fine, and it doesn't affect the caller.
    2. Window sum. rollingSum starts at 0 and holds the sum of the current window.
    3. Total. totalSum starts at 0. Adding to it during the same loop saves a separate pass.
    4. Best window. maxSum starts at int.MinValue, so the first full window replaces it. Starting at 0 would be wrong if every window had a negative sum.
    5. Loop over every index i of nums.
    6. Add the current number to both totalSum and rollingSum.
    7. Wait for a full window. The first window of k elements is complete when i reaches k - 1. Before that, the guard i >= k - 1 is false.
    8. Record and slide. Once the window is full, update maxSum with Math.Max, and then subtract nums[i - k + 1], the oldest element, so that the next iteration's addition leaves a window of exactly k numbers again.
    9. Return totalSum - maxSum.

    Here is the loop on the example, where the window length is 4. At i = 3 the window is -2, 5, 2, -1 with sum 4, so maxSum becomes 4 and -2 is removed, leaving 6. At i = 4 the sum is 6 + 3 = 9, so maxSum becomes 9, and the removal of 5 leaves 4. The remaining windows have sums -6, 1 and 0, which never beat 9. At the end totalSum is 4, and the method returns 4 - 9 = -5.

    The solution in C#

    class Solution {
    public int RemoveMinSum(int[] nums, int k) {
        k = nums.Length - k;
        int rollingSum = 0;
        int totalSum = 0;
        int maxSum = int.MinValue;
        for (int i = 0; i < nums.Length; i++) {
            totalSum += nums[i];
            rollingSum += nums[i];
            if (i >= k - 1) {
                maxSum = Math.Max(maxSum, rollingSum);
                rollingSum -= nums[i - k + 1];
            }
        }
        return totalSum - maxSum;
    }
}

    C# details worth noticing

    • Reusing a parameter. Overwriting k keeps the code short, but the name now means something different from the one the caller passed. In your own code, a new variable such as windowSize would be easier to read.
    • Subtraction after the check. The window slides inside the if. The order matters: the sum is compared while the window is full, and only afterwards is the oldest element removed.
    • Overflow. The totals are int and wrap silently beyond about two billion in magnitude. The lesson's data is small.

    Complexity

    Time: O(n). One pass, with constant work per element.

    Space: O(1). The code uses a few int variables.

    A direct approach would try each split of k into a prefix part and a suffix part and add them up, which is simple but slower. The block view finds the answer in one pass and no extra arrays.

    Edge cases and common mistakes

    • k = 0. Nothing is picked, and the block is the whole array. The only window is the total, so the result is total - total = 0. For the example array, the code returns 0.
    • k = nums.Length - 1. The block has a single element, and the best one is the largest number. For the example with k = 7, the largest is 9, so the result is 4 - 9 = -5.
    • k = nums.Length. The block would be empty. This code isn't written for that case: the window length becomes 0, and the final iteration reads past the end of the array and throws an IndexOutOfRangeException. The code assumes that at least one number stays in the middle.
    • Wrong window size. Using the original k as the window size would find the best block of the picked size, which is a different problem.
    • Starting maxSum at 0. If the array is all negative, every window is negative and 0 would never be replaced.
    • Window start index. A window of k elements ending at i starts at i - k + 1. Writing i - k removes the wrong element.

    Testing

    • [-2, 5, 2, -1, 3, -10, 9, -2] with k = 4 returns -5.
    • The same array with k = 0 returns 0.
    • The same array with k = 7 returns -5.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free