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

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

The 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.


Program to Find the Longest Subarray having average greater than or equal to k

For example,

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


Brute Force approach:

An easy approach is to consider each subarray one by one and find its average. If the average value is greater than or equal to k, then compare the length of the subarray with the 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 average greater than or equal to k

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

@@coding::1@@


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

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

@@coding::2@@


Time complexity: O (n log n)



Recommended Programs









Program to Find the Longest Subarray having average greater than or equal to k

c