• 0

    The question can be tackled by multiple approaches. I am gonna shed light on all the approaches one by one .

    The First Approach is by using a balanced binary search tree and calculating maximum by inserting and deleting elements from the range. In c++ there is a cool implementation of BST called set . You can perform insert/delete operations in set in logn and that is what we want. So coming to the final solution what we will do is , first we will push all the elements in range [0, w-1] in set and find the maximum in set using *s.rbegin() , now for each range ahead our initial range we will delete the start and insert the end+1 and find maximum for updated set . The total complexity of this algorithm will come out to nlogk .

    here is the code in c++ - -

    vector<int> Solution::slidingMaximum(const vector<int> &A, int B) {
        multiset<int> s;
        multiset<int>::iterator it;
        int st = 0;
        int en = st+B-1;
        for(int i = st; i <= en; i++){
        int max1 = *s.rbegin();
        vector<int> v;
        while(en+1 < A.size()){
            it = s.find(A[st]);
            st = st+1;
            en = en+1;
            max1 = *s.rbegin();
        return v;

    Another approach is O(n) by using a Dequeue . We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.

    here is the code in c++ -

    class Solution {
            vector<int> slidingMaximum(vector<int> &A, int w) {
                int n = A.size();
                vector<int> B;
                if (n < w) return B;
                B.resize(n - w + 1);
                deque<int> Q;
                for (int i = 0; i < w; i++) {
                    while (!Q.empty() && A[i] >= A[Q.back()])
                for (int i = w; i < n; i++) {
                    B[i - w] = A[Q.front()];
                    while (!Q.empty() && A[i] >= A[Q.back()])
                    while (!Q.empty() && Q.front() <= i - w)
                B[n - w] = A[Q.front()];
                return B;

  • 0

    @terminated doesn't Qi contain the elements that are greater than all other elements on the right side of the element in the current window?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.