Important to talk about the solution (Brute Force vs Deque Method) in Java


  • 6
    I

    Perhaps most of the people here are practicing coding skills to land a job. It is fairly important to talk about your process of thought to the interviewer. You can't just jump in and give the best and most optimal solution though , because that seems like you have already seen the problems and memorized it thoroughly. Best approach is to give a brute force solution first, if interviewer asks for further optimization, then only you talk about using deque and other better solution.

    Always start with brute-force method has a good advantage. Most of the time, in a 45 mins technical interview, the interviewer only prepares 1 - 2 coding questions and if you finish too early, they will probably start asking about other trivia questions or knowledge-based questions, which will put you in a disadvantageous position if you are a person who is not very good at talking. So starting with brute force (even though the question is listed as hard problem, but it isn't that hard to solve after all) , then get to optimal part, and bam! You nail a 45 mins technical interview with flying colors !

    Anyway, here is the brute force approach:

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || k <= 0) return new int [0];
        int [] arr = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length - k + 1; i++){
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++)
               max = Math.max(max, nums[j]);
            arr[i] = max;
        }
        return arr;
    }
    

    Using deque :

    The idea is to use deque to hold the index of maximum element and restrict deque size to k. In first while loop, we make sure that we remove the elements which are not longer in the sliding k range. In second loop is we make sure that the elements in the deque is not smaller than the current element. Then we add the element to the deque.

    The if(i >= k - 1) is just to skip the first few elements that is less than k. For example, if k = 3, then we don't want the first two elements added to the array. Also notice that our array is arr = new int[nums.length - k + 1] , as for the fact that when we have k as the size of sliding windows, then the end result of sliding windows array will be nums.length - k + 1.

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || k <= 0) return new int [0];
        int [] arr = new int[nums.length - k + 1];
        int in = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < nums.length; i++){
            while(!dq.isEmpty() && dq.peek() < i - k + 1) dq.poll();
            while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
            dq.offer(i);
            if(i >= k - 1) arr[in++] = nums[dq.peek()];
        }
        return arr;
    }

Log in to reply
 

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