Wednesday, August 16th

 Sliding Window Maximums

Given an array of numbers and a sliding window, return a vector with the maximum value in each window

An English pub's sliding window via Wikipedia, courtesy of Stephen Lea, shared under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made.

I came up with a solution that uses a hashmap and priority queue that solves the problem within the given time constraints.

The idea is to maintain a priority queue of size k that contains all elements within a given window.  Whenever the window slides to the next element, the new element is pushed onto the queue, while the old element is removed.

The only problem is that there are no deletions in a priority queue.  To solve that problem, we maintain a hashmap that stores an element's frequency within the given window.  When the window slides, the frequency of the dropped element is reduced.  That way, if the new maximum value at the top of the priority queue has a frequency of zero, this top element can be removed.

While this works, one drawback is that, since elements are only removed from the front of the priority queue, the priority queue may contain more elements than the size of the window.

Learning from other solutions, a multiset is a data structure that can accomplish this task, which acts as a priority queue while also supporting deletions.

As for the code, begin by initializing data structures:

    vector<int> ans;

    int n=nums.size();

    priority_queue<int> pq;

    unordered_map<int,int> hashmap;

Then fill the data structures for the first window.  For each element in the first window, set its frequency in the hashmap and push each element onto the priority queue.  Put the maximum into the answer vector

    int num;

    for(int i=0; i<k; i++) {

        num=nums[i];

        hashmap[num]+=1;

        pq.push(num);

    }

    ans.push_back(pq.top());

Now iterate over the remaining values, for each window tracking the value to be dropped and the value being added

    add, subtract;

    for(int i=1; i<=n-k; i++) {           

        subtract=nums[i-1];

        add=nums[k+i-1];

        ...

    }

Reduce the frequency of the dropped by 1, and increment the added value by 1.  Then push the new value onto the priority queue

    hashmap[subtract]-=1;            

    hashmap[add]+=1;

    pq.push(add);

Before adding the top of the priority queue to the answer, make sure the top of the priority queue doesn't contain any subtracted elements.  This is because we cannot remove elements directly from the priority queue.  Instead, we can only remove old elements when they are at the top of the queue, but have no frequency in the hashmap

    while( hashmap[pq.top()]==0 ) {

       pq.pop();

    }

Finally, add the top of the queue to the answer vector, and return the solution

    for(int i=1; i<=n-k; i++) {           

        ...

        ans.push_back(pq.top());

    }

    return ans; 

Kind of sloppy with not deleting nodes from the priority queue, but it works.  Each insertion, since we're not deleting elements, could take up to log n time, and is performed n-k times, so I calculate O(n log n).  But I thought that in practice the runtime would be much lower, and indeed it passes all the test cases.  

Learned about the capabilities of a multi set and look forward to utilizing their capabilities in the future.

Reveiwing other solutions, there is a linear time solution using a deque, but I did not come up with the solution myself and my own code worked.

Full code below 

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> ans;

        int n=nums.size();

        priority_queue<int> pq;

        unordered_map<int,int> hashmap;

       

        int num;

        for(int i=0; i<k; i++) {

            num=nums[i];

            hashmap[num]+=1;

            pq.push(num);

        }

        ans.push_back(pq.top());

       

        int add, subtract;

        for(int i=1; i<=n-k; i++) {

            subtract=nums[i-1];

            add=nums[k+i-1];

            hashmap[subtract]-=1;            

            hashmap[add]+=1;

            pq.push(add);

            while( hashmap[pq.top()]==0 ) {

                pq.pop();

            }

            ans.push_back(pq.top());

        }

        return ans;

    }