Why run time exceeded using priority queue?


#1

The outer loop runs atmost n-B+1 times and the inner loop runs 3 times and for each time the inner loop runs the insertion operation in the priority queue takes O(logB) time worst case . Hence the total worst complexity of the code must be (n-B+1)Blog(B).

public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH “final” PREFIX. IT IS READ ONLY
public int[] slidingMaximum(final int[] A, int B) {
int[] result = new int[A.length-B + 1];

            for(int i = 0 ; i < A.length - B + 1 ; i ++){
                PriorityQueue<Integer> S1 = new PriorityQueue<Integer>(Collections.reverseOrder());
                for(int j = i ; j  < i + B ; j++){
                    S1.add(A[j]);
                }
                result[i] = S1.poll();
            }
            return result;
        }
    }