Longest subarray having average greater than or equal to x | Set-2
Given an array of N integers. The task is to find the longest contiguous subarray so that the average of its elements is greater than or equal to a given number X.
Examples:
Input: arr = {1, 1, 2, -1, -1, 1}, X = 1 Output: 3 Length of longest subarray with average >= 1 is 3 i.e. ((1+1+2)/3)= 1.333 Input: arr[] = {2, -3, 3, 2, 1}, x = 2 Output: 3 Length of Longest subarray is 3 having average 2 which is equal to x.
An approach with time complexity O(Nlogn) has been already discussed here. In this post, an efficient approach with time complexity O(N) will be discussed.
Approach:
- Subtract X from each arr[i] and convert the array into prefix array. Lets call the new array as prefixarr[].
- Now the problem becomes finding max(j-i) in prefixarr[] such that j > i and prefixarr[j] > prefixarr[i] i.e. similar to Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Below is the implementation of above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Utility Function to find the index // with maximum difference int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int LMin[n], RMax[n]; // Construct LMin[] such that LMin[i] // stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); // Construct RMax[] such that RMax[j] // stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); // Traverse both arrays from left to right // to find optimum j - i // This process is similar to merge() // of MergeSort i = 0, j = 0, maxDiff = -1; while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff + 1; } // utility Function which subtracts X from all // the elements in the array void modifyarr( int arr[], int n, int x) { for ( int i = 0; i < n; i++) arr[i] = arr[i] - x; } // Calculating the prefix sum array // of the modified array void calcprefix( int arr[], int n) { int s = 0; for ( int i = 0; i < n; i++) { s += arr[i]; arr[i] = s; } } // Function to find the length of the longest // subarray with average >= x int longestsubarray( int arr[], int n, int x) { modifyarr(arr, n, x); calcprefix(arr, n); return maxIndexDiff(arr, n); } // Driver code int main() { int arr[] = { 1, 1, 2, -1, -1, 1 }; int x = 1; int n = sizeof (arr) / sizeof ( int ); cout << longestsubarray(arr, n, x) << endl; return 0; } |
Java
// Java implementation of // above approach import java.io.*; import java.lang.*; class GFG { // Utility Function to find the // index with maximum difference static int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int LMin[], RMax[]; LMin = new int [n]; RMax = new int [n]; // Construct LMin[] such that // LMin[i] stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[ 0 ] = arr[ 0 ]; for (i = 1 ; i < n; ++i) LMin[i] = Math.min(arr[i], LMin[i - 1 ]); // Construct RMax[] such that // RMax[j] stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1 ] = arr[n - 1 ]; for (j = n - 2 ; j >= 0 ; --j) RMax[j] = Math.max(arr[j], RMax[j + 1 ]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort i = 0 ; j = 0 ; maxDiff = - 1 ; while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = Math.max(maxDiff, j - i); j = j + 1 ; } else i = i + 1 ; } return (maxDiff + 1 ); } // utility Function which subtracts X // from all the elements in the array static void modifyarr( int arr[], int n, int x) { for ( int i = 0 ; i < n; i++) arr[i] = arr[i] - x; } // Calculating the prefix sum // array of the modified array static void calcprefix( int arr[], int n) { int s = 0 ; for ( int i = 0 ; i < n; i++) { s += arr[i]; arr[i] = s; } } // Function to find the length of the // longest subarray with average >= x static int longestsubarray( int arr[], int n, int x) { modifyarr(arr, n, x); calcprefix(arr, n); return maxIndexDiff(arr, n); } // Driver code public static void main(String args[]) { int [] arr ={ 1 , 1 , 2 , - 1 , - 1 , 1 }; int x = 1 ; int n = arr.length; System.out.println(longestsubarray(arr, n, x)); } } // This code is contributed by Subhadeep |
Python 3
# Python 3 implementation # of above approach # Utility Function to find the # index with maximum difference def maxIndexDiff(arr,n): LMin = [ None ] * n RMax = [ None ] * n # Construct LMin[] such that LMin[i] # stores the minimum value # from (arr[0], arr[1], ... arr[i]) LMin[ 0 ] = arr[ 0 ] for i in range ( 1 , n): LMin[i] = min (arr[i], LMin[i - 1 ]) # Construct RMax[] such that RMax[j] # stores the maximum value # from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1 ] = arr[n - 1 ] for j in range (n - 2 , - 1 , - 1 ): RMax[j] = max (arr[j], RMax[j + 1 ]) # Traverse both arrays from left # to right to find optimum j - i # This process is similar to merge() # of MergeSort i = 0 j = 0 maxDiff = - 1 while (j < n and i < n): if (LMin[i] < RMax[j]): maxDiff = max (maxDiff, j - i) j = j + 1 else : i = i + 1 return maxDiff + 1 # utility Function which subtracts X # from all the elements in the array def modifyarr(arr, n, x): for i in range (n): arr[i] = arr[i] - x # Calculating the prefix sum # array of the modified array def calcprefix(arr, n): s = 0 for i in range (n): s + = arr[i] arr[i] = s # Function to find the length of the # longest subarray with average >= x def longestsubarray(arr, n, x): modifyarr(arr, n, x) calcprefix(arr, n) return maxIndexDiff(arr, n) # Driver code if __name__ = = "__main__" : arr = [ 1 , 1 , 2 , - 1 , - 1 , 1 ] x = 1 n = len (arr) print (longestsubarray(arr, n, x)) # This code is contributed by ChitraNayal |
C#
// C# implementation of // above approach using System; class GFG { // Utility Function to find the // index with maximum difference static int maxIndexDiff( int [] arr, int n) { int maxDiff; int i, j; int [] LMin = new int [n]; int [] RMax = new int [n]; // Construct LMin[] such that // LMin[i] stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = Math.Min(arr[i], LMin[i - 1]); // Construct RMax[] such that // RMax[j] stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = Math.Max(arr[j], RMax[j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort i = 0; j = 0; maxDiff = -1; while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = Math.Max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return (maxDiff + 1); } // utility Function which subtracts X // from all the elements in the array static void modifyarr( int [] arr, int n, int x) { for ( int i = 0; i < n; i++) arr[i] = arr[i] - x; } // Calculating the prefix sum // array of the modified array static void calcprefix( int [] arr, int n) { int s = 0; for ( int i = 0; i < n; i++) { s += arr[i]; arr[i] = s; } } // Function to find the length of the // longest subarray with average >= x static int longestsubarray( int [] arr, int n, int x) { modifyarr(arr, n, x); calcprefix(arr, n); return maxIndexDiff(arr, n); } // Driver code public static void Main() { int [] arr ={ 1, 1, 2, -1, -1, 1 }; int x = 1; int n = arr.Length; Console.Write(longestsubarray(arr, n, x)); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP implementation of above approach // Utility Function to find the // index with maximum difference function maxIndexDiff(& $arr , $n ) { $LMin [ $n ] = array (); $RMax [ $n ] = array (); // Construct LMin[] such that LMin[i] // stores the minimum value // from (arr[0], arr[1], ... arr[i]) $LMin [0] = $arr [0]; for ( $i = 1; $i < $n ; ++ $i ) $LMin [ $i ] = min( $arr [ $i ], $LMin [ $i - 1]); // Construct RMax[] such that RMax[j] // stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) $RMax [ $n - 1] = $arr [ $n - 1]; for ( $j = $n - 2; $j >= 0; -- $j ) $RMax [ $j ] = max( $arr [ $j ], $RMax [ $j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort $i = 0; $j = 0; $maxDiff = -1; while ( $j < $n && $i < $n ) { if ( $LMin [ $i ] < $RMax [ $j ]) { $maxDiff = max( $maxDiff , $j - $i ); $j = $j + 1; } else $i = $i + 1; } return $maxDiff + 1; } // utility Function which subtracts X // from all the elements in the array function modifyarr( $arr , $n , $x ) { for ( $i = 0; $i < $n ; $i ++) $arr [ $i ] = $arr [ $i ] - $x ; return calcprefix( $arr , $n ); } // Calculating the prefix sum // array of the modified array function calcprefix(& $arr , $n ) { $s = 0; for ( $i = 0; $i < $n ; $i ++) { $s += $arr [ $i ]; $arr [ $i ] = $s ; } return maxIndexDiff( $arr , $n ); } // Function to find the length of the // longest subarray with average >= x function longestsubarray(& $arr , $n , $x ) { return modifyarr( $arr , $n , $x ); } // Driver code $arr = array ( 1, 1, 2, -1, -1, 1 ); $x = 1; $n = sizeof( $arr ); echo longestsubarray( $arr , $n , $x ) ; // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript implementation of // above approach // Utility Function to find the // index with maximum difference function maxIndexDiff(arr,n) { let maxDiff; let i, j; let LMin, RMax; LMin = new Array(n); RMax = new Array(n); // Construct LMin[] such that // LMin[i] stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = Math.min(arr[i], LMin[i - 1]); // Construct RMax[] such that // RMax[j] stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = Math.max(arr[j], RMax[j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort i = 0; j = 0; maxDiff = -1; while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = Math.max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return (maxDiff + 1); } // utility Function which subtracts X // from all the elements in the array function modifyarr(arr,n,x) { for (let i = 0; i < n; i++) arr[i] = arr[i] - x; } // Calculating the prefix sum // array of the modified array function calcprefix(arr,n) { let s = 0; for (let i = 0; i < n; i++) { s += arr[i]; arr[i] = s; } } // Function to find the length of the // longest subarray with average >= x function longestsubarray(arr,n,x) { modifyarr(arr, n, x); calcprefix(arr, n); return maxIndexDiff(arr, n); } // Driver code let arr=[1, 1, 2, -1, -1, 1 ]; let x = 1; let n = arr.length; document.write(longestsubarray(arr, n, x)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
3
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Contact Us