Java Solution using HashMap and PriorityQueue


  • 0
    M

    I got a variation of this question in an interview. Initially I gave O(n^2) solution, then made it better.
    Here is the final solution using hashmap and priorityqueue(this is not the exact solution but the idea is similar).

    The priority queue is used to give the element with the max value. The hashmap is used to keep track of the elements that were not considered. You only have to remove the elements if they pop up on the top of the queue.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums==null || nums.length==0){
                return new int[0];
            }
            int[] res = new int[nums.length-k+1];
            Queue<Integer> q = new PriorityQueue<Integer>((i,j)->j-i);
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            for(int i=0; i<k; i++){
                q.offer(nums[i]);
            }
            int start=0, end=k-1,j=0;
            res[j++]=q.peek();
            while(!q.isEmpty() && end<nums.length-1){
                end++;
                q.offer(nums[end]);
                if(map.containsKey(nums[start])){
                    map.put(nums[start],map.get(nums[start])+1);
                }else{
                    map.put(nums[start],1);
                }
                while(map.containsKey(q.peek()) && map.get(q.peek())>0){
                    map.put(q.peek(),map.get(q.peek())-1);
                    q.poll();
                }
                res[j++]=q.peek();
                start++;
            }
            return res;
        }
    }
    

Log in to reply
 

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