Find the Subarray of given length with Least Average

Difficulty Level Easy
Frequently asked in Accenture Accolite Amazon Factset Fourkites Paytm Zoho
ArrayViews 2801

Problem Statement

In the “Find the Subarray of given length with Least Average” problem we have given an array and an input integer X. Write a program to find the subarray of length X with least/minimum average. Prints the starting and ending indexes of the subarray which has the least average.

Input Format

The first line containing an integer value n.

Second-line containing n space-separated integers.

The third line containing an integer value X.

Output Format

The first and only one line containing two integer values with space-separated. The first integer represents the starting and the second integer represents the ending indexes of the subarray which has the least average.

Constraints

  • 1<=N<=10^5
  • 1<=a[i]<=10^9
  • 1<=X<=N

Example

5
3 5 1 7 6
2
1 2

Explanation: The subarray is between index 1 and 2. We can see clearly that the sum of 5 and  1 is the least.

Algorithm to Find the Subarray of given length with Least Average

In this method, we use the idea of the sliding window of size X.

1. Initialize index =0, which is the starting index of the subarray with the least average

2. Find the sum of the first X elements and store it in sum variable

3. Initialize least_sum to the above sum variable

4. Traverse the array from (X+1)th index till the end of the array

  • For every element arr[i], calculate sum = sum + arr[i] -arr[i-X]
  • If sum < least_sum, then make index = (i-X+1) and least_sum =sum.

5. Print the index and the index + X -1 as the starting and ending of the subarray with least average.

Implementation

C++ Program to Find the Subarray of given length with Least Average

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int k;
  cin>>k;
  if(n>=k)
  {
      int ans = 0; 
    	int sum = 0; 
    	for(int i=0;i<k;i++) 
    	{
    		sum+=a[i];
    	}
    	int min_sum=sum; 
    	for (int i=k;i<n;i++) 
    	{ 
    		sum+=a[i]-a[i-k]; 
    		if(sum<min_sum) 
    		{ 
    			min_sum = sum; 
    			ans = (i-k+1); 
    		} 
    	} 
    	cout<<ans<<" "<<ans+k-1<<endl;
  }
  else
  {
     cout<<-1<<endl;
  }
  return 0; 
}

Java Program to Find the Subarray of given length with Least Average

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        int k = sr.nextInt();
        if(n>=k)
        {
            int ans = 0; 
            int sum = 0; 
            for(int i=0;i<k;i++) 
            {
                    sum+=a[i];
            }
            int min_sum=sum; 
            for (int i=k;i<n;i++) 
            { 
                    sum+=a[i]-a[i-k]; 
                    if(sum<min_sum) 
                    { 
                            min_sum = sum; 
                            ans = (i-k+1); 
                    } 
            } 
            System.out.println(ans +" "+(ans+k-1));
        }
        else
        {
            System.out.println(-1);
        } 
    }
}

10
1 4 3 6 23 76 43 1 2 89
4
0 3

Complexity Analysis to Find the Subarray of given length with Least Average

Time Complexity

O(n) where n is the size of the given array a[]. Here we use the concept of the sliding window which take linear time.

Space Complexity

O(1) because we don’t use any auxiliary space at here.

Translate »