JAVA beats 99% O(n*k) solution


  • 0
    O
    public class Solution {
        //O(n*k)
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length == 0) return new int[0];
            int n =  nums.length + 1 - k;
            int[] maxs = new int[n];
            int max = Integer.MIN_VALUE;
            int maxIndex = 0;
            int i = 0;
            for(i = 0; i < k; i++){
                if(nums[i] > max) {
                    max = nums[i];
                    maxIndex = i; // track the index for the max element
                }
            }
            int windowIndex = 0;
            maxs[windowIndex] = max;
            windowIndex++;
            int left = 0; //the index of the element we want to move out of the window
            // O(n)
            while(i < nums.length){ // i will always be window end index
                if(left != maxIndex){
                    if(nums[i] >= max){
                        max = nums[i];
                        maxIndex = i;
                    }
                }else{ // if max element is going to be moved out of the window, find the next max element and update maxIndex
                    if(nums[i] >= nums[left]){
                        max = nums[i];
                        maxIndex = i;
                    }else{
                        max = nums[left+1];
                        for(int j = left+1; j <= i; j++){ // O(k) k is constant
                            if(nums[j] >= max){
                                max = nums[j];
                                maxIndex = j;
                            }
                        }
                    }
                }
                maxs[windowIndex] = max;
                windowIndex++;
                
                //sliding the window
                left++;
                i++;
            }
            return maxs;
        }
    }
    

Log in to reply
 

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