Find minimum sum of a subarray of size k

Posted in /  

Find minimum sum of a subarray of size k

Vinay Khatri
Last updated on September 21, 2022

    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:

    Tags:
    array subarray

    Leave a Comment on this Post

    0 Comments