JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP11 Sliding Window Maximum

You are given an array of integers nums, 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: 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
                    

Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length

Notes

Note: Zoom for Better Understanding

Always start with the BruteForce Approch and then moved on the Optimal Approch

Now can we say that I start with Iteration from 0 and finding the all the possible subarray with the length ok k

Code Zone!

Time Complexity:O(N ^ 2) Becouse we used a nested Loop thats why
Space Complexity:O(N) for the Answer

Optimized Approch

Now here again we used the concept of the Next Greatest Element that we learned pevesolly in this Concept we store the element into the Increasing Fassion

In this problem we store the element into the Desciring order Fassion we required the deque data structure

we start Iteration from the Index = 0

And maintain the deque prpoperty that is decresing order and put that Index into the deque

Maintain Property

check if the deque is Empty() then put the Index into the deque

and check if the exisiting element is the < then arr[i] then removed all the element from the deque and then put Index into the deque

otherwise put Index into the deque

Code Zone!

Time Complexity:O(N) + O(N) ~ O(N) for the linear Iteration, and for the checking the Window Size That is the Amotized Time Complexcity
Space Complexity:O(K) for the Answer of window size