30. Smallest subarray with sum greater than x

30. Smallest subarray with sum greater than x

Problem link :- click here

package programs;

import java.util.*;

public class Array__30
{

	/*
	     1)we will go on adding the elements until the sum becomes > given_sum
	     2)once sum reach the  given_sum then 
	                we will subtract elements one by one from first element of the sub-array
	     3)while subtracting if the sum < given_sum then we will again add elements(as in step-1)
	     this keeps repeating 
	     NOTE :- we will update the variable which holds the minimum elements of the sub-array
	                    when ever the sum > given_sum (in step-2)
	*/
	static int smallestSubArray(int arr[], int n, int given_sum)
	{
		int min_length = Integer.MAX_VALUE;   //our result
		int sum = 0;
		int length = 0;        //to maintain the     size of the sub-array
		int j = 0;                //to hold the           index of the first element
		
		for(int i=0; i<n;)
		{
			if(sum <= given_sum)
			{
				sum = sum + arr[i];
				length++;
				i++;
			}
			else if(sum > given_sum)
			{
				//updating the min_length as sum > given_sum
				min_length = Math.min(min_length, length) ;
				
				//we already discussed this 
				//we also have to update, pointer to first element of the sub-array i.e., 'j'
				sum = sum - arr[j];
				j++;
				length--;
				//we are not updating min_length here because 
				//we don't know whether the sum > given_sum after subtracting an element
			}
		}
		return min_length;
	}
	
	
	public static void main(String[] args)
	{
		int i, n, sum, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] =new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.print("Enter the sum : ");
		sum = s.nextInt();
		
		System.out.println("Given array : ");
		print_array(array);

		ans = smallestSubArray(array, n, sum);
		System.out.println("\n\nMinimum length subarray is : " + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)