Find minimum sum of a subarray of size k

By | November 17, 2021
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

Vamware
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:

Vamware
Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.