Java 3 solutions, Deque O(n), Heap O((n-k)k), Heap O((n-k)logn)


  • 4
    M

    I wrote 3 methods I can come up with.

    1. Deque Method: use deque to record the index, remove elements out of window in the head, and remove the smaller elements in the tail which have no change to become max.
        // O(n)
        public int[] maxSlidingWindow_deque(int[] nums, int k) {
            if(nums==null || k>nums.length || k<0) return null;
            if(k==0 || nums.length==0) return new int[0];
            Deque<Integer> dq = new LinkedList<>();
            int[] res = new int[nums.length-k+1];
            int index = 0; // index in r is equal to the left side of window
            for(int i=0; i<nums.length; i++){
                // remove elements out of window
                index = i-k+1;
                while(!dq.isEmpty() && dq.peek()<index){
                    dq.poll();
                }
                // remove smaller elements, which have no change to become max
                while(!dq.isEmpty() && nums[dq.peek()]<nums[i]){
                    dq.pollLast();
                }
                dq.offer(i);
                if(index>=0){
                    res[index] = nums[dq.peek()];
                }
            }
            return res;
        }
    
    1. Max Heap Method: a naive method. Build a max heap for a window, and remove the element out of window.
        //O((n-k)(lgk+k)) = O((n-k)k)
        public int[] maxSlidingWindow_heap1(int[] nums, int k) {
            if(nums==null || k>nums.length || k<0) return null;
            if(k==0 || nums.length==0) return new int[0];
            PriorityQueue<Integer> heap = new PriorityQueue<>( k, Collections.reverseOrder() );
            int[] res = new int[nums.length - k + 1];
            for(int i=0; i<k; i++)
                heap.offer(nums[i]);
            for(int p=0; p<res.length; p++){
                res[p] = heap.peek();
                heap.remove(nums[p]);
                if(p+k < nums.length)
                    heap.offer(nums[p+k]);
            }
            return res;
        }
    
    1. Max Heap Method 2: Using a class Tuple to record index info.
        // worst case O((n-k)logn) increasing order, best case O((n-k)logk) decreasing order
        public int[] maxSlidingWindow_heap2(int[] nums, int k) {
            if(nums==null || k>nums.length || k<0) return null;
            if(k==0 || nums.length==0) return new int[0];
            PriorityQueue<Tuple> heap = new PriorityQueue<>( k, Collections.reverseOrder() );
            int[] res = new int[nums.length - k + 1];
            for(int i=0; i<k; i++)
                heap.offer(new Tuple(nums[i], i));
            Tuple tup = null;
            for(int p=0; p<res.length; p++){
                tup = heap.peek();
                while(tup.idx<p) {
                    heap.poll();
                    tup = heap.peek();
                }
                res[p] = tup.val;
                if(p+k < nums.length)
                    heap.offer(new Tuple(nums[p+k], p+k));
            }
            return res;
        }
        class Tuple implements Comparable<Tuple>{
            int val;
            int idx;
            public Tuple(int value, int index){
                val = value;
                idx = index;
            }
            @Override
            public int compareTo(Tuple tup){
                return (val - tup.val);
            }
        }
    
    

    I came up with the second one first, then the third one. Then I looked at the discuss, and found people used deque with O(n). I did the first one.


  • 0
    Q

    for solution2, why the time complexity is O((n-k)(lgk+k)) = O((n-k)k). My thinking: in the for loop "for(int p=0; p<res.length; p++)"
    res[p] = heap.peek();//O(1) time heap.remove(nums[p]);//update the tree, O(logk) heap.offer(nums[p+k]);//update the tree, O(logk)
    So, I think it should be O((n-k)(lgk+lgk))-->O(n-k)lgk. This is the same result with the solution3 in case the original array is decreasing order
    If there is anything wrong in my statement, please tell me.


  • 0
    M

    @QunWu
    For PriorityQueue, remove() is O(lgn) while remove(element) is O(n) because remove() is to remove the top one while remove(ele) need to scan all the element to find the match one.


  • 0
    Q

    Thanks for your clear answer.


  • 0

    I think you can use hashHeap which is implemented by one max heap and one hash map to record every node's position. Thus, remove() function's complexity is O(logN)


  • 0

    For the second approach, why isn't the time complexity O(nlog(k))?


Log in to reply
 

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