Clear Linear Time Java Solution without additional Data structures. Beats 98.56%.


  • 0
    H

    Solution is to update the present Maximum if the new element in the window is more than current maximum.

    We need to iterate over the window and find maximum again only if the present maximum is the element that has just passed out of the window and the new element in the window is not greater than the present Maximum.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums==null||nums.length==1||nums.length==0){
                return nums;
            }
            
            int[] ans = new int[nums.length-k+1];
            int kMin = 0;
            int kMax = k-1;
            int presMax = findMaxInK(nums,0,k-1);
            ans[kMin] = presMax;
            
            for(int index = kMax;index<nums.length-1;index++){
                kMin++; kMax++;
                if(presMax<nums[kMax]){
                    presMax = nums[kMax];
                    ans[kMin] = presMax;
                }
                else{
                    if(nums[kMin-1]==presMax){
                        presMax = findMaxInK(nums,kMin,kMax);
                        ans[kMin] = presMax;
                    }
                    else{
                        ans[kMin] = presMax;
                    }
                }
            }
            
            return ans;
        }
        
        public int findMaxInK(int[] nums,int kMin,int kMax){
            int ans = nums[kMin];
            
            for(int index = kMin+1;index<=kMax;index++){
                if(nums[index]>ans){
                    ans = nums[index];
                }
            }
            return ans;
        }
    }
    
    

  • 1

    To quote myself from earlier today:

    Ah, it's just another solution advertised as being especially good but actually being especially bad. It's not linear time but only O(n2). Consider cases like nums = [70000, 69999, ..., 2, 1] and k = 35000. The previous max value always drops out and thus you always scan the entire window. That case btw takes you way over a second and gets you Time Limit Exceeded.

    Yours is a bit faster, but for nums = [130000, 129999..., 2, 1] and k = 65000 you get TLE as well.


  • 0
    H

    @StefanPochmann
    Point Taken. Could you say how to do this in linear time?


  • 0
    T

    @hemanth.pinaka
    check out other solutions using deque or dynamic programming techniques, they are all O(n) solutions, your solution won't get that good percentage if they add test cases with nums in descending order


Log in to reply
 

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