educative.io

Educative

Heads up simpler solution using TreeMap

This solution uses TreeMap, which comes handy in all sort of problems.
The code is way more compact and easy to understand.

import java.util.*;

public class MaximumInSlidingWindow {
    public static List<Integer> findMaxSlidingWindow(List<Integer> nums, int windowSize) {
        List<Integer> result = new ArrayList<>();
        TreeMap<Integer, Integer> tm = new TreeMap<>((a, b)-> b.compareTo(a));
        Deque<Integer> cache = new LinkedList<>();
        for(int end = 0, start = 0; end < nums.size(); end++) {
            tm.put(nums.get(end), tm.getOrDefault(nums.get(end), 0) + 1);
            cache.add(nums.get(end));
            if (end - start + 1 >= windowSize) {
                result.add(tm.firstKey());
                int first = cache.poll();
                tm.put(first, tm.get(first) - 1);
                if (tm.get(first) == 0) {
                    tm.remove(first);
                }
                start++;
            } else if (windowSize > nums.size() && end == nums.size() - 1) {
                result.add(tm.pollFirstEntry().getKey());
            }
        }
        return result;
    }
    public static void main(String[] args) {
        assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(-4, 5, 4, -4, 4, 6, 7), 2).toArray(), new Integer[]{5, 5, 4, 4, 6, 7});
        assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(-4, 5, 4, -4, 4 , 6, 7), 10).toArray(), new Integer[]{7});
        assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(3, 3, 3, 3, 3, 3), 3).toArray(), new Integer[]{3, 3, 3, 3});
        assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(1, 2, 3, 1, 4, 5, 2, 3, 6), 3).toArray(), new Integer[]{3, 3, 4, 5, 5, 5, 6});

    }
}

Even though the method in TreeMap is called remove, in this case the time complexity is log(n), much better than n which we would have with a PriorityQueue.


Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

Hey, @Davide_Pugliese!
I hope you’re doing great. We appreciate your comment. Dear @Davide_Pugliese Above code is ambiguous and not working efficiently. The Time Complexity: of TreeMap is O(n log k) as the elements are iterated once, and the operations of the BST of size “k” is O(log k).

We hope Educative has inspired you to further your learning. :blush: