Find minimum sum of a subarray of size k

Problem

Given an array of integers and a number k , find the minimum sum of a subarray of size k .

Brute Force approach

A simple solution is to construct all subarrays of size k , compute their sums, and ultimately return the sum with the lowest value. This solution has a time complexity of O(N* k ). Let’s look at one more approach.

Efficient approach

A more efficient solution is based on the fact that the total of a subarray of size k may be achieved in O(1) time by utilizing the preceding subarray sum of size k . With the exception of the first subarray, the total is computed by deleting the first element of the previous subarray and adding the next element to the new subarray and keep updating the result. This approach takes O(N) time and O(1) auxiliary space.

C++ Programming

#include <iostream>
using namespace std;
int minSum(int arr[], int n, int k)
{
    
    // Compute sum of first subarray of size k
    int ans = 0;
    for (int i=0; i<k; i++)
    ans += arr[i];

    // Compute sums of remaining subarrays by
    // removing first element of previous
    // subarray and adding last element of
    // current subarray.
    int sum = ans;
    for (int i=k; i<n; i++)
    {
    sum += arr[i] - arr[i-k];
    ans = min(ans, sum);
    }

    return ans;
}
int main(){
    int arr[]={1, 2, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout<<minSum(arr, n, k);
}

Output

3

Python Programming

def minSum(arr, n, k):
    
    # Compute sum of first
    # subarray of size k
    ans = 0
    for i in range(k):
        ans += arr[i]

    # Compute sums of remaining subarrays by
    # removing first element of previous
    # subarray and adding last element of
    # current subarray.
    sum = ans
    for i in range(k, n):
    
        sum += arr[i] - arr[i-k]
        ans = min(ans, sum)

    return ans

l = [1, 2, 3, 4]
n=len(l)
k=2
print(minSum(l, n, k))

Output

3

C Programming

#include <stdio.h>
int min(int a, int b){
    return a>=b?b:a;
}
int minSum(int arr[], int n, int k)
{
    
    // Compute sum of first subarray of size k
    int ans = 0;
    for (int i=0; i<k; i++)
    ans += arr[i];

    // Compute sums of remaining subarrays by
    // removing first element of previous
    // subarray and adding last element of
    // current subarray.
    int sum = ans;
    for (int i=k; i<n; i++)
    {
    sum += arr[i] - arr[i-k];
    ans = min(ans, sum);
    }

    return ans;
}
int main(){
    int arr[]={1, 2, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    printf("%d", minSum(arr, n, k));
}

Output

3

People are also reading:

• Decode an array constructed from another array
• Find equilibrium index of the array
• Reverse every consecutive m-elements of a subarray
• Find maximum sum path involving elements of given arrays
• Longest Subarray with Contiguous Elements
• Find equilibrium index of the array
• Python Numpy Array Tutorial
• Find the smallest window in an array sorting which will make the entire array sorted
• C++ Arrays
• Python Arrays