Program to find the longest subarray having average greater than or equal to k

Program to find the longest subarray having an average greater than or equal to k is discussed here. An array and a positive integer (k) are given as input. A subarray from the array has to be found such that the average of this subarray is greater than or equal to x.

For example, consider the array: arr = {-2, 1, 6, -3} and k = 3. The longest subarray is {1, 6} having average 3.5 greater than k = 3.

Brute Force approach:

An easy approach is to consider each sub array one by one and find its average. If the average value is greater than or equal to k, then compare the length of subarray with maximum length found so far in the array. This approach has a time complexity of O(n^2).

Program to find the longest subarray having an average greater than or equal to k 

// C program to find the longest subarray having an average greater than or equal to k

#include <stdio.h>
int subarray_avg(int a[], int k, int len);
int main()
{
int a[20], len, i, k;
printf(“\nEnter the number of elements : “);
scanf(“%d”, &len);
printf(“\nInput the array elements : “);
for(i=0; i<len; i++)
{
scanf(“%d”, &a[i]);
}
printf(“\nInput the k value : “);
scanf(“%d”, &k);
printf(“\nSub-array average : %d\n”,subarray_avg(a, k, len));
return 0;
}
int subarray_avg(int arr[],int x,int n)
{
int length=0 ,temp =0 ;
int max=0,sum=0,i;
for(i=0;i<n;i++)
{
sum = sum+arr[i];
temp++;
if(sum>max && sum/temp>=x && temp>=length)
{
max= sum ;
length =temp;
}
if(sum<0)
{
sum=0;
temp=0;
}
}
return length;
}

// C++ program to find the longest subarray having an average greater than or equal to k

#include <iostream>
using namespace std;

int subarray_avg(int a[], int k, int len);
int main()
{
int a[20], len, i, k;
cout << “\nEnter the number of elements : “;
cin >> len;
cout << “\nInput the array elements : “;
for(i=0; i<len; i++)
{
cin >> a[i];
}
cout << “\nInput the k value : “;
cin >> k;
cout << “\nSub-array average : ” << subarray_avg(a, k, len) << endl;
return 0;
}

int subarray_avg(int arr[],int x,int n)
{
int length=0 ,temp =0 ;
int max=0,sum=0,i;
for(i=0;i<n;i++)
{
sum = sum+arr[i];
temp++;
if(sum>max && sum/temp>=x && temp>=length)
{
max= sum ;
length =temp;
}
if(sum<0)
{
sum=0;
temp=0;
}
}
return length;
}

Time complexity: O(n)

An efficient approach using binary search:

An algorithm using binary search is given as follows:

  • Input the array elements and the value ‘k’ (The output average should be greater than this value ‘k’)
  • The value ‘k’ is subtracted from each element of the array.
  • Create a vector and store the updated sum values during each iteration.
  • Sort this vector and create a variable min_index to store the minimum index of the value stored in the vector.
  • For i = 0 to length of the vector,
  • Calculate the sum of the vectors. If sum >= 0, then return i+1.
  • If sum < 0, find if there is a value in the array (using binary search) which when added to the current sum, the value gets greater than or equal to zero.
  • If yes, compare the length of the updated sub-array with the maximum_length.
  • Return maximum_length.

Program to find the longest subarray having average greater than or equal to k (using binary search)

// C++ program to find the longest subarray having an average greater than or equal to k

#include <bits/stdc++.h>

using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
if (a.first == b.first)
return a.second < b.second;

return a.first < b.first;
}

int findInd(vector<pair<int, int> >& prefix_sum, int n, int val)
{

int l = 0;
int h = n – 1;
int mid;

int ans = -1;

while (l <= h)
{
mid = (l + h) / 2;
if (prefix_sum[mid].first <= val)
{
ans = mid;
l = mid + 1;
}
else
h = mid – 1;
}

return ans;
}

int longest_sub_array(int arr[], int n, int k)
{
int i;

for (i = 0; i < n; i++)
arr[i] -= k;

int max_length = 0;

vector<pair<int, int> > prefix_sum;

int sum = 0;
int min_ind[n];

for (i = 0; i < n; i++)
{
sum = sum + arr[i];
prefix_sum.push_back({ sum, i });
}

sort(prefix_sum.begin(), prefix_sum.end(), compare);

min_ind[0] = prefix_sum[0].second;

for (i = 1; i < n; i++) {
min_ind[i] = min(min_ind[i – 1], prefix_sum[i].second);
}

sum = 0;
for (i = 0; i < n; i++)
{
sum = sum + arr[i];

if (sum >= 0)
max_length = i + 1;

else
{
int ind = findInd(prefix_sum, n, sum);
if (ind != -1 && min_ind[ind] < i)
max_length = max(max_length, i – min_ind[ind]);
}
}

return max_length;
}

int main()
{
int arr[] = { -2, 1, 6, -3 };
int n = sizeof(arr) / sizeof(arr[0]);

int k = 3;

cout << longest_sub_array(arr, n, k);
return 0;
}

Output:

longest subarray average

Time complexity: O (n log n)