Given an array and a key element, find the number of continuous elements whose sum is greater than the key element.

Example:

array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
k = 30
Output: 4
This is because the sub array [6, 7, 8, 9]

This problem can be solved with “two pointers with sliding window approach” solution.

Algorithm:

Step 1: Increase right pointer till the sum is greater than or equal to the key.
Step 2: Then increase the left pointer to right pointer till the sum is less than the key.
Step 3: Store the minimum length in a variable.

Solution in C++

#include<iostream>
#include<vector>

using namespace std;


int min_sub_array_len(vector<int>& nums, int key) 
{
	int left = 0;
	int right = 0;
	int length = nums.size();
	int sum = 0;
	int len = INT_MAX;
	
	cout<<"=================start debugging==============="<<endl;
	while (right < length) 
	{
		sum += nums[right++];
		cout<<"Step 1: sum = "<<sum<<" right = "<<right<<" left = "<<left<<endl;
		while (sum >= key) 
		{
			len = min(len, right - left);
			sum -= nums[left++];
			cout<<"Step 2: sum = "<<sum<<" right = "<<right<<" left = "<<left<< " len = min(len, right - left) = "<<min(len, right - left)<<endl;
		}
	}
	cout<<"=================end debugging==============="<<endl;
return len == INT_MAX ? 0 : len;
}

int main()
{
	vector<int> array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	int key = 30;
	int len = min_sub_array_len(array, key);
	cout<<"\n\nThe minimum length of continious sub array is "<<len<<endl;

	return 0;
}

Output:

=================start debugging===============
Step 1: sum = 1 right = 1 left = 0
Step 1: sum = 3 right = 2 left = 0
Step 1: sum = 6 right = 3 left = 0
Step 1: sum = 10 right = 4 left = 0
Step 1: sum = 15 right = 5 left = 0
Step 1: sum = 21 right = 6 left = 0
Step 1: sum = 28 right = 7 left = 0
Step 1: sum = 36 right = 8 left = 0
Step 2: sum = 35 right = 8 left = 1 len = min(len, right – left) = 7
Step 2: sum = 33 right = 8 left = 2 len = min(len, right – left) = 6
Step 2: sum = 30 right = 8 left = 3 len = min(len, right – left) = 5
Step 2: sum = 26 right = 8 left = 4 len = min(len, right – left) = 4
Step 1: sum = 35 right = 9 left = 4
Step 2: sum = 30 right = 9 left = 5 len = min(len, right – left) = 4
Step 2: sum = 24 right = 9 left = 6 len = min(len, right – left) = 3
=================end debugging===============

The minimum length of continious sub array is 4