Simple O(n) time complexity solution with O(k) auxiliary space using array.


  • 0
    A

    Firstly calculate the length of the auxiliary array required.
    Then we need to compute a logical -code solution that satisfies O(n) time complexity which mean we shall just use a single lop in the worst case.
    For this we shall think of a logic in manipulating index "i" each time. for this we need to keep track of the traversals or the window size which is 'k', we keep an additional variable 'j' which is incremented each time in the traversal and gets reset ones the window gets exhausted.
    '''
    class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length==0)return new int[0];
    int[] res = new int[nums.length-k+1];
    int key=0;
    int max =Integer.MIN_VALUE;
    for(int i=key,j=0;(i<nums.length&&(key+k)<=nums.length);i++){
    max = max>nums[i]?max:nums[i];
    j++;
    if(j==k){
    res[key++]=max;
    j=0;
    i=key-1;
    max=Integer.MIN_VALUE;
    }
    }
    return res;
    }
    }
    '''


Log in to reply
 

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