Longest subarray having average greater than or equal to x | Set-2

0 0 9 minutes read

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

Complexity Analysis:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!