Optimize array algo for finding maximum of j - i subjected to the constraint of A[i] <= A[j]

Question

Given an array A[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of A[i] <= A[j].

Input: The first line contains an integer T, depicting total number of test cases. Then T test case follows. First line of each test case contains an integer N denoting the size of the array. Next line contains N space separated integeres denoting the elements of the array.

Output: Print the maximum difference of the indexes i and j in a separtate line.

Constraints: 1 ≤ T ≤ 1000 1 ≤ N ≤ 107 0 ≤ A[i] ≤ 1018

Example: Input: 1 9 34 8 10 3 2 80 30 33 1

Output: 6

I have written solution for O(n). But I am getting "time limit exceeded" error while submitting this solution.

To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays min[] and max[] such that min[i] holds the smallest element on left side of arr[i] including arr[i], and max[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing min[] and max[] if we see that min[i] is greater than max[j], then we must move ahead in min[] (or do i++) because all elements on left of min[i] are greater than or equal to min[i]. Otherwise we must move ahead in max[j] to look for a greater j – i value

Can we optimize it more?

 import java.util.*;
 import java.lang.*;
 import java.io.*;

 class GFG {
   public static void main (String[] args) {

        Scanner in =new Scanner(System.in);
        int noOfUsecases=in.nextInt();

        for(int i=0;i<noOfUsecases;i++){
        int arrayLength=in.nextInt();
        int[] arr=new int[arrayLength];
        if(in.hasNextInt()){

            for(int j=0;j<arrayLength;j++){
                arr[j]=in.nextInt();
            }

        }
        maximumIndex(arr,arrayLength);
    }
}
public static void maximumIndex(int[] arr,int length){
    int i = 1,j = length-2;
    int maxDiff=0;
    int[] min=new int[length];
    min[0]=arr[0];
    for(;i<length;++i){
        min[i]=arr[i]<min[i-1]?arr[i]:min[i-1];
    }
    int[] max=new int[length];
    max[length-1]=arr[length-1];
    for(;j>=0;--j){
        max[j]=arr[j]>max[j+1]?arr[j]:max[j+1];
    }
    i = 0;j = 0;
    while (j < length && i < length)  
    { 
        if (min[i] <= max[j])  
        { 
            maxDiff = maxDiff>(j - i)?maxDiff:(j-i); 
            j = j + 1; 
        }  
        else 
            i = i + 1; 
    }
    System.out.println(maxDiff);
}}

score 0 · Accepted Answer · answered May 02 '20 at 09:48

This problem obviously can't be solved faster, than O(n) (you need to read input data, at least), but your problem is that you are using the scanner to input your data, and it is very slow. Here you can find multiple solutions to this problem. Pick one that meets your requirements.

Optimize array algo for finding maximum of j - i subjected to the constraint of A[i] <= A[j]

1 Answers1