TLE for O(nlogn) solution using Sparse Table



  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];
         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++){
                 int r=j+pow2(i-1);
                 //System.out.print(" r="+r);
                 if(r<n && A[sp[i-1][j]]<A[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(A[x]>lowerLimit && A[x]<upperLimit) return x;
             return -1;
         int k=log2(y-x);
         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]]) 
         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));