Sliding Window Maximum LeetCode Solution


Frequently asked in Adobe Amazon American Express Apple ByteDance Citadel Google Intel LinkedIn Mathworks Microsoft Oracle PayPal Quora Salesforce Splunk Tesla Twilio Twitter Two Sigma Uber VMware Yelp
Bookin.com Categories - Hard Cruise Automatiin instacart tiktokViews 1

Problem Statement

Sliding Window Maximum LeetCode Solution Says that – You are given an array of integers nums, and there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input:

 nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:

 [3,3,5,5,6,7]

Explanation:

 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7

3

 1 [3  -1  -3] 5  3  6  7

3

 1  3 [-1  -3  5] 3  6  7

5

 1  3  -1 [-3  5  3] 6  7

5

 1  3  -1  -3 [5  3  6] 7

6

 1  3  -1  -3  5 [3  6  7]

7

Example 2:

Input:

 nums = [1], k = 1

Output:

 [1]

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

ALGORITHM –

IDEA –

    • In order to Find Sliding Window Maximum. First, we will focus on the Given range i.e K and the maximum element lie within that range. Basically What we will do is make one Deque and Answer list which return the answer.
    • Then will traverse through the array and Check for the condition if the top of the deque is less than the current value then pop out the element from the queue else push the element index into the deque.
    • Then again we will Check for two conditions if the maximum element does not lie within the range if it will not lie then pop it out from the deque and one more condition i.e. if the index is greater than or equal to K-1 then we will start filling our answer list and append dequeue of the first element into it and at last return answer.

APPROACH –

  • At first, we will create one Deque and one answer list and at last, we will return the answer.
  • After that, we will traverse through the whole array, and with the help of the while condition, we will check if q[-1] < current val if this condition satisfies then will pop out the last element from q. Else push the element index into q.
  • Then we will check if the maximum element lies within range or not by using index – K == q[0]. if the condition satisfies then will pop the element from q using q.popleft().
  • Again check if the index is equal to K-1 or greater than K-1 then simply add the maximum element into the answer list and return the answer.
  • Hence we will find the Sliding Window Maximum.

IMAGE OF SOLUTION –

Sliding Window Maximum LeetCode SolutionPin Sliding Window Maximum LeetCode SolutionPin Sliding Window Maximum LeetCode SolutionPin Sliding Window Maximum LeetCode SolutionPin

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        
        for i,v in enumerate(nums):
            
              while(q and nums[q[-1]] <= v):
                    q.pop()
              
              q.append(i)
                
              
              if q[0] == i-k:
                    q.popleft()
              
            
              if i >= k-1:
                    ans.append(nums[q[0]])
        return ans
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return nums;
        }
        int[] ans = new int[n - k + 1];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            q.offer(i);
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[q.peek()];
            }
        }
        return ans;
    }
}

Time Complexity: O(N), As we have traversed the whole array only once.

Space Complexity: O(N), as we have created one Deque.

SIMILAR QUESTIONS – https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

Top sliding-window-maxi interview questions

Translate »