Java Solution using next greater element and previous greater element + Binary Search


#1
`public class Solution {
public int[] solve(int[] A, int[] B) {
    int n = A.length;
    int[] next = nextG(A, n);
    int[] prev = nextGRev(A, n);
    Pair[] mat = new Pair[n];
    long mod = (int)1e9+7;
    for(int i=0; i<n; i++){
        int a = A[i];
        long k = a;
        for(int j=2; j<=Math.sqrt(a); j++){
            if(a%j == 0){
                k = ((k%mod)*(j%mod))%mod;
                if(a/j != j)
                    k = ((k%mod)*((a/j)%mod))%mod;
            }
        }
        mat[i] = new Pair(k, (1L*(i-prev[i]))*(next[i]-i));
    }
    Arrays.sort(mat, Collections.reverseOrder());
    
    long[] arr = new long[n];
    arr[0] = mat[0].n;
    for(int i=1; i<n; i++){
        arr[i] = arr[i-1] + mat[i].n;
    }
    
    int[] ans = new int[B.length];
    int m = B.length;
    for(int i=0; i<m; i++){
        int a = Arrays.binarySearch(arr, B[i]);
        if(a<0){
            a = -a;
            a -= 1;
        }
        
        ans[i] = (int)mat[a].pro;
    }
    return ans;
    
}
public class Pair implements Comparable<Pair>{
    long pro;
    long n;
    Pair(long a, long b){
        pro = a;
        n = b;
    }
    public int compareTo(Pair p){
        return (int)(this.pro - p.pro);
    }
}
public int[] nextG(int[] arr, int n) {
    int[] ans = new int[n];
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    for(int i=1; i<n; i++) {
        while(!stack.isEmpty() && arr[stack.peek()]<=arr[i])
            ans[stack.pop()] = i;
        stack.push(i);
    }
    while(!stack.isEmpty())
        ans[stack.pop()] = n;
    return ans;
}

public int[] nextGRev(int[] arr, int n) {
    int[] ans = new int[n];
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(n-1);
    for(int i=n-2; i>=0; i--) {
        while(!stack.isEmpty() && arr[stack.peek()]<arr[i])
            ans[stack.pop()] = i;
        stack.push(i);
    }
    while(!stack.isEmpty())
        ans[stack.pop()] = -1;
    return ans;
}

}`