Find the smallest sub array with a sum greater than a given number.

You are given an array of integers and a particular number, you need to find the smallest subarray possible with a sum greater than the given Number. The requirement is to write an algorithm that calculates in Time Complexity of O(n).

Java Solution of the given problem is :

import java.util.LinkedList;
import java.util.Queue;

public class SmallestSubArrayWithSumGreaterThanNumber {
	public static void main(String[] args) {
		 int arr[] = {1, 4, 45, 6, 10, 19};
	 int x = 51;
	 
	 long startTime = System.nanoTime();
	 
	 int res = FindSmallestSubArrayWithSumGreater(arr,x);
	 if(res == arr.length + 1)
	 	 System.out.println("Not Available");
	 else
	 	 System.out.println(res);
	 
	 long endTime = System.nanoTime();
		long totalTime = endTime - startTime;
		System.out.println("Total Time (nanoseconds) : " + (totalTime));
	}

	private static int FindSmallestSubArrayWithSumGreater(int[] arr, int x) {
		
		Queue<Integer> queue = new LinkedList<Integer>();
		int sum = 0;
		int min_len = arr.length + 1;
		for(int i=0;i<arr.length;i++)
		{
			if(x < sum && min_len > queue.size()) {
				min_len = queue.size();
				sum -= (Integer) queue.remove();
			}
			else {
				sum += arr[i];
				queue.add(arr[i]);
			}
		}
		return min_len;
	}
}

Output:

3
Total Time (nanoseconds) : 665298