Rahul And Minimum Subarray
Rahul is a programming enthusiast. He is currently learning about arrays/lists. One day his teacher asked him to solve a very difficult problem. The problem was to find the length of the smallest subarray(subarray is a contiguous part of an array/list) in a given array/list ‘ARR’ of size ‘N’ with its sum greater than a given value. If there is no such subarray return 0.

Example: Given an ‘ARR’: [1, 2, 21, 7, 6, 12] and a number ‘X’: 23. The length of the smallest subarray is 2 as the subarray is [21, 7].

Note: Here are multiple subarrays whose sum is greater than ‘X’ such as [1, 2, 21] or [7, 6, 12] but we have to choose the minimum length subarray.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain two integers ‘N’ and ‘X’ that denote the size of the ‘ARR’ and the given value respectively. The second line of each test case contains ‘N’ space-separated integers ‘A[i]’, these are the numbers present in our ‘ARR’.

Output Format:

For each test case, print an integer denoting the length of the minimum subarray whose sum is greater than ‘X’. Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1

Question

Rahul And Minimum Subarray

Rahul is a programming enthusiast. He is currently learning about arrays/lists. One day his teacher asked him to solve a very difficult problem. The problem was to find the length of the smallest subarray(subarray is a contiguous part of an array/list) in a given array/list ‘ARR’ of size ‘N’ with its sum greater than a given value. If there is no such subarray return 0.

Example: Given an ‘ARR’: [1, 2, 21, 7, 6, 12] and a number ‘X’: 23. The length of the smallest subarray is 2 as the subarray is [21, 7].

Note: Here are multiple subarrays whose sum is greater than ‘X’ such as [1, 2, 21] or [7, 6, 12] but we have to choose the minimum length subarray.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two integers ‘N’ and ‘X’ that denote the size of the ‘ARR’ and the given value respectively.

The second line of each test case contains ‘N’ space-separated integers ‘A[i]’, these are the numbers present in our ‘ARR’.

Output Format:

For each test case, print an integer denoting the length of the minimum subarray whose sum is greater than ‘X’.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
1 <= X <= 10^9
0 <= A[i] <= 10^9

Time Limit: 1 sec

Accepted Answer

Approach 1 (Brute Force) :
In this approach, we make use of an idea based on selection sort.

1) Traverse over the given numsnums array choosing the elements nums[i]. For every such element chosen, we try to
determine its correct position in the sorted array. For this, we compare nums[i] with every nums[j], such that i < j < n.

2) If any nums[j] is lesser than nums[i], it means both nums[i] and nums[j] aren't at their correct position for the sorted
array. Thus, we need to swap the two elements to bring them at their correct positions.

3) Instead of swapping, just note the position of nums[i] (given by i) and nums[j] (given by j). These two elements now
mark the boundary of the unsorted subarray(atleast for the time being).

4) Out of all the nums[i] chosen, we determine the leftmost nums[i] which isn't at its correct position. This marks the
left boundary of the smallest unsorted subarray(l).

5) Similarly, Out of all the nums[j] considered for all nums[i] we determine the rightmost nums[j] which isn't at its
correct position. This marks the right boundary of the smallest unsorted subarray(r).

6) Therefore, the length of the smallest unsorted subarray = r−l+1.

TC : O(N^2)
SC : O(1)

Approach 2 (Using Sorting) :

1) We can sort a copy of the given array nums, say given by nums_sorted.

2) Then, if we compare the elements of nums and nums_sorted, we can determine the leftmost and rightmost
elements which mismatch.

3) The subarray lying between them is, then, the required shorted unsorted subarray.

TC : O(N*log(N))
SC : O(N)

Accepted Answer

Brute Force

The basic idea of this approach is to iterate the whole ‘ARR’ from start and find the sum of all the possible subarrays and find out the length of the minimum subarray whose sum is greater than the given value. We will use two loops and calculate the sum for all the possible subarrays and select the subarrays that match our given conditions.

Here is the algorithm:

Declare a variable ‘MIN_LENGTH’ which will contain the length of the minimum subarray.
Run a loop for ‘i’ = 0 to ‘N’:
- Declare a variable ‘CURRENT_SUM’ which will store the sum of all possible subarrays
- Run a loop for ‘j’ = ‘i’ + 1 to ‘N’:
  - Add the current element ‘ARR[j]’ to the sum ‘CURRENT_SUM’.
  - Compare the value of ‘CURRENTSUM’ with ‘TARGET’. If ‘CURRENT_SUM’ is greater than ‘TARGET’:
    - Update ‘MINLENGTH’ if ‘MIN_LENGTH’ is smaller than the length of the current subarray.
Finally, return ‘MIN_LENGTH’.

Space Complexity: O(1)Explanation:

O(1),

Because we are not using any extra space for finding our answer

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of elements in the given ‘ARR’.

Because there are two loops, the outer loop picks a starting element, the inner loop considers all the elements on the right side of the starting elements as the ending element. So, for every starting element, we consider all the other elements as the ending one. Hence the time complexity is O(N^2).

Python (3.5)

'''
    Time Complexity : O(N^2)
    Space Complexity : O(1)

    Where N denotes the size of array.

'''

def minSubArrayLen(arr, target, n):

    # Declaring currentSum and minLength that will store the sum of all the possible subarrays 
    # and the length of the minimum subarray whose currentSum is greater than target.
    currentSum = 0
    minLength = 1000000000

    # Iterating through every element as the starting point of the subarray
    for i in range(len(arr)):

        # Initialize the currentSum with 0..
        currentSum = 0

        # Try different ending points
        for j in range(i, len(arr)):

            # Adding the sum of different ending points
            currentSum += arr[j]

            # Check if the subarray of the current subarray is greater than the target value
            if currentSum > target:
                # If the sum is greater and length of the subarray is smaller than the minimum length then update the minimum length
                minLength = min(minLength, j - i + 1)   

    # Return minimum length subarray whose sum is greater than target
    if minLength == 1000000000:
        return 0

    return minLength

Java (SE 1.8)

/*

    Time Complexity : O(N^2)
    Space Complexity : O(1)

    Where N denotes the size of array.


*/

public class Solution {
    
    public static int minSubArrayLen(int arr[], int target, int n) {
		
        // Declaring currentSum and minLength that will store the sum of all the possible subarrays 
        // and the length of the minimum subarray whose currentSum is greater than target.
        int currentSum = 0;
        int minLength = Integer.MAX_VALUE;
    
        // Iterating through every element as the starting point of the subarray
        for(int i = 0; i < n; i++) {
    
            // Initialize the currentSum with 0..
            currentSum = 0;
    
            // Try different ending points
            for(int j = i; j < n; j++) {
    
            	// Adding thesum of different ending points
                currentSum += arr[j];
    
                // Check if the subarray of the current subarray is greater than the target value
                if(currentSum > target) {
    
                	// If the sum is greater and length of the subarray is smaller than the minimum length then update the minimum length
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }
    
        // return minimum length subarray whose sum is greater than target
        if(minLength == Integer.MAX_VALUE) {
            return 0;
        } 
        return minLength;

    }
}

C++ (g++ 5.4)

/*

    Time Complexity : O(N^2)
    Space Complexity : O(1)

    Where N denotes the size of array.


*/


#include 
#include

int minSubArrayLen(vector& arr, int target, int n) {
		
    // Declaring currentSum and minLength that will store the sum of all the possible subarrays 
    //and the length of the minimum subarray whose currentSum is greater than target.
    int currentSum = 0;
    int minLength = INT_MAX;

    // Iterating through every element as the starting point of the subarray
    for(int i = 0; i < arr.size(); i++) {

        // Initialize the currentSum with 0..
        currentSum = 0;

        // Try different ending points
        for(int j = i; j < arr.size(); j++) {

        	// Adding thesum of different ending points
            currentSum += arr[j];

            // Check if the subarray of the current subarray is greater than the target value
            if(currentSum > target) {

            	// If the sum is greater and length of the subarray is smaller than the minimum length then update the minimum length
                minLength = min(minLength, j - i + 1);
            }
        }
    }

    // return minimum length subarray whose sum is greater than target
    if(minLength == INT_MAX) {
        return 0;
    } 
    return minLength;
}

Accepted Answer

Sliding Window Approach

As all the elements in the ‘ARR’ are positive, if a subarray has a sum greater than ‘TARGET’ then adding other elements to the current subarray will make the sum even greater. The idea is to start with an empty subarray and add elements to it until its sum is greater than ‘TARGET’. As soon as the sum is greater than ‘TARGET’ remove the starting element from the current sum.

Here is the algorithm:

Declare four variables ‘START_INDEX’, ‘END_INDEX’, ‘CURRENT_SUM’, and ‘MIN_LENGTH’ where ‘START_INDEX’ and ‘END_INDEX’ denote the indexes of the current subarray whose sum is stored in ‘CURRENT_SUM’ and ‘MIN_LENGTH’ denotes the length of the minimum subarray.
Run a loop from start to end of the ‘ARR’:
- Update the variable ‘CURRENT_SUM’ as ‘CURRENT_SUM’ = ‘CURRENT_SUM’ + ‘ARR[‘STARTI_NDEX’]’
- If the ‘CURRENT_SUM’ is greater than ‘TARGET’ then:
  - Update ‘MIN_LENGTH’ if ‘MIN_LENGTH’ is greater than the length of the current subarray.
  - Subtract ‘ARR[‘START_INDEX’]’ from ‘SUM’ and increment ‘START_INDEX’ by 1.
- Else:
  - Increment the value of ‘END_INDEX’ by 1.
Finally, return ‘MIN_LENGTH’.

Space Complexity: O(1)Explanation:

O(1),

Because we are not using any extra space for finding our answer

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the ‘ARR’.

Because all the elements of the ‘ARR’ are traversed only once. Hence, the time complexity is O(N).