Minimum Size Subarray Sum Problem (C++, Java, Python)

 

One of the difficult topics in programming is the Sliding Window. It helps you to solve problems in a lower time complexity. This method is useful when we are solving problems related to subarrays or substrings. In this article, we will discuss the problem “Minimum Size Subarray Sum,” which is based on a sliding window.

“Minimum Size Subarray Sum” Problem

In the Minimum Size Subarray problem, you are given an array of integers. You have also been given a target integer. You have to find the minimum length subarray such that the sum of elements present in the subarray is equal to or greater than the target element.

Let’s understand this with an example:

Input:

array = [ 2, 3, 1, 4, 2, 1], target = 6.

Output:

2

Explanation: Shown are different ways in which we can form 6 and the minimum length among them is 2. So the answer is 2.

Brute Force Approach

The basic approach is to create all the subarrays of the given array. Check whose subarray sum is greater than the target element. If it is greater than the target element,t find the minimum length among them. Let’s understand this step by step.

1. Create a loop that traverses from 1 to n. Where n is the size of the array.
2. Create a variable ‘sum’ that stores the total subarray sum.
3. Create a nested loop that traverses from i to n. Now we get the subarray of size (j – i +1).
4. Check if the subarray sum is greater than the target element or not. If it is, then compare its size with our resultant variable.
5. If a resultant variable is greater than the size of the subarray. Update the resultant with this size.
6. After iterating over all the subarrays. Return the resultant variable.

The time complexity for the above code is O(n^2). Where n is the size of the array. We are using two nested loops whose time complexity is O(n^2). The space complexity for the above code is O(1) as we are not using any extra space.

Binary Search Approach

In the above approach, we see we are using O(n^2) time complexity, which is huge. In this approach, we will calculate the subarray sum for index 1 and store it in a vector. Now we will go at each index and check for their lower bound using binary search. If the size of the lower bound is less than the resultant variable,e, we will update it. 

Let’s examine this approach step by step.

• First, create a vector of size array. Next, calculate the subarray sum for index 1.
• Now, iterate over each index and find the subarray that has a greater sum than the target element using binary search.
• Compare the length of this subarray with the resultant variable. If it is smaller than the resultant variable, then update it.

The time complexity for the above code is O(n log(n)). We first find the subarray sum for index 1, which took O(n) time complexity. Then, we find the subarray sum using a binary search whose time complexity is O( n log(n)). So, the overall time complexity is O( n log(n)).

Optimized Approach: Sliding Window 

In the above approaches, we are either using extra time or space. To reduce both of them, we will use the sliding window technique. In this, we will create two variables: start and current. Start to current define a subarray. We will iterate over the array and check if the subarray sum is less than the target or not. If not, we will keep on updating our start index with start +1 and subtracting that element from our sum.

Let’s examine this approach step by step:

1. First, create two variables: start and current. Initialize start and current with 0.
2. Create an answer and a sum variable that stores the minimum length and the total subarray sum. Now iterate over the array and check if the subarray sum is greater than the target or not.
3. If it is greater than the target, keep on iterating over the loop till v[current] – v[start] >= target. Inside that loop, subtract arr[start] from our sum and update start = start + 1.
4. Once the iteration is over, check if the v[current] – v[start] > = target. If it is update our answer with min(answer, length (subarray)).
5. At last return the answer.

C++ Code

Here is the Sliding Window Approach implemented in C++:

#include <bits/stdc++.h>

using namespace std;

int find_min_subarray(vector<int>& arr, int target){

    int sum=0, answer=INT_MAX, start=0;

    for(int i=0;i<arr.size();i++){

        sum+= arr[i];

        while(sum-arr[start]>=target){

            sum-= arr[start];

            start++;

        }

        if(sum>=target) answer = min(answer, i - start + 1);

    }

    if( answer!=INT_MAX ) return answer;

    return 0;

}

int main(){

    vector<int> arr = {2, 3, 1, 4, 2, 1};

    int target = 6;

    int answer = find_min_subarray(arr, target);

    cout<< answer <<endl;

    return 0;

}

Java Code

Here is the solution in Java:

import java.util.ArrayList;

public class Main {

    public static int findMinSubarray(ArrayList<Integer> arr, int target) {

        int sum = 0, answer = Integer.MAX_VALUE, start = 0;

        for (int i = 0; i < arr.size(); i++) {

            sum += arr.get(i);

            while (sum - arr.get(start) >= target) {

                sum -= arr.get(start);

                start++;

            }

            if (sum >= target) {

                answer = Math.min(answer, i - start + 1);

            }

        }

        if (answer != Integer.MAX_VALUE) {

            return answer;

        }

        return 0;

    }

    public static void main(String[] args) {

        ArrayList<Integer> arr = new ArrayList<>();

        arr.add(2);

        arr.add(3);

        arr.add(1);

        arr.add(4);

        arr.add(2);

        arr.add(1);

        int target = 6;

        int answer = findMinSubarray(arr, target);

        System.out.println(answer);

    }

}

Python Code

Same approach done in Python

def find_min_subarray(arr, target):

    sum_val = 0

    answer = float('inf')

    start = 0

    for i in range(len(arr)):

        sum_val += arr[i]

        while sum_val - arr[start] >= target:

            sum_val -= arr[start]

            start += 1

        if sum_val >= target:

            answer = min(answer, i - start + 1)

    if answer != float('inf'):

        return answer

    return 0

if __name__ == "__main__":

    arr = [2, 3, 1, 4, 2, 1]

    target = 6

    answer = find_min_subarray(arr, target)

    print(answer)

Output:

2

The time complexity for the above approach is O(n). We are just iterating the loop once. The space complexity is O(1) as we are not using any extra space.

Conclusion

In this article, we see various approaches for solving the Minimum Size Subarray Sum problem. It is one of the most interesting questions on LeetCode. We have seen that the Sliding Window technique is the most effective method for solving.