TLE for O(nlogn) solution using Sparse Table


#1

Algo:

  1. Create sparse table.

  2. for each element a in array, assume it is the middle element.

  3. Query sparse table to find the max Value in left subarray which is less than a and max Value in the right subarray which is greater than a.

  4. In each for such query, q(x,y) : get index of max value in subarray A[x…y]=t.

  5. If A[t]<lowerLimit or A[t]>upperLimit, fire recursive queries q(x,t-1) & q(t+1,y) and get the result.
    Space complexity: O(nlogn)
    Time Complexity: O(nlong)

    public class Solution {

     public int solve(int[] A) {
         int n=A.length,ans=0;
         if(n<=2) return -1;
         int sp[][]=buildSpTable(A);
         for(int i=1;i<n-1;i++){
             int lq=q(A,sp,0,i-1,Integer.MIN_VALUE,A[i]),rq=q(A,sp,i+1,n-1,A[i],Integer.MAX_VALUE),sum=-1;
             if(lq>=0 && lq<n && rq>=0 && rq<n) sum=A[lq]+A[i]+A[rq];
             ans=Math.max(ans,sum);
         }
         return ans;
     }
     int[][] buildSpTable(int A[]){
         int n=A.length,sz=log2(n)+1;
         int sp[][]=new int[sz][n];
         for(int i=0;i<sz;i++){
             for(int j=0;j<n;j++){
                 if(i==0){
                     sp[i][j]=j;
                     continue;
                 }
                 //sp[i][j]=min{sp[i-1][j],sp[i-1][j+2^(i-1)]}
                 sp[i][j]=sp[i-1][j];
                 int r=j+pow2(i-1);
                 //System.out.print(" r="+r);
                 if(r<n && A[sp[i-1][j]]<A[sp[i-1][r]]) 
                     sp[i][j]=sp[i-1][r];
             }
         }
         
         return sp;
     }
     int q(int A[], int sp[][], int x, int y, int lowerLimit, int upperLimit){
         //find the index of max value in A[x....y]<limit
         int n=A.length;
         if(x>y || x>=n || y>=n || x<0 || y<0) return -1;
         
         if(x==y){
             if(A[x]>lowerLimit && A[x]<upperLimit) return x;
             return -1;
         }
         int k=log2(y-x);
         //ans=max{sp[k][x],sp[k][y-pow2(k)+1]}
         int ans=sp[k][x],r=y-pow2(k)+1;
         if(r<n && sp[k][r]<n && sp[k][x]<n && A[sp[k][x]]<A[sp[k][r]]) 
             ans=sp[k][r];
         if(A[ans]>lowerLimit && A[ans]<upperLimit) return ans;
         
         int lq=q(A,sp,x,ans-1,lowerLimit,upperLimit),rq=q(A,sp,ans+1,y,lowerLimit,upperLimit);
         if(lq==-1 && rq==-1) ans=-1;
         else if(lq==-1) ans=rq;
         else if(rq==-1) ans=lq;
         else ans = (A[lq]>=A[rq])?lq:rq;
         return ans;
     }
     int pow2(int n){
         return 1<<n;
     }
     int log2(int n){
         return (int)(Math.log(n)/Math.log(2));
     }
    

    }