0 like 0 dislike
996 views

recategorized | 996 views

0 like 0 dislike

Author of this sheet : https://www.linkedin.com/in/kumark1/

Desi QnA Sliding-Window Sheet (Make sure to go through set A and set B to have a good preparation level for an interview)

------------------------------------------------------------------------------------------------------------------

For the best output , make sure that you are thorough with the concepts of Hashing and Two-Pointers and have done enough practice on the same.

Step - 0 :

Watch this video to understand the concept of sliding window : https://www.youtube.com/watch?v=__guhvzO540

Step - 1 : Solve problems from set-A.

Note : Many problems can have two solutions : 1)Hashing solution or 2)Two-Pointers/Sliding-Window-Based solution , make sure you know both the solutions , Hashing based solution will always used some memory as you will be using a map to store some values. When all integers in an array are positive , mostly Two-Pointers/Sliding Window Method is used , otherwise Hashing as it can handle the case of negative integers too :)

Set - A :

(Very Important to clear up your fundamentals)

P2 : Find maximum sum subarray of size 'K'

https://www.geeksforgeeks.org/window-sliding-technique/

P4 : Find minimum size subarray in an array of positive integers having sum K..

(Hashing solution with O(N) is also possible to this problem so know that too  especially in case negative integers are present.)

Step - 3 : Solve problems from set-B . These problems will involve using a queue/de-queue data structure , so learn how to declare and use them and come back to solving this list..

Set - B : Make your mind flexible and mix up and find different solutions to the same problem using Hashing/Two-Pointers/Sliding-Window :) Most importantly , enjoy the process!!

P1 : https://leetcode.com/problems/sliding-window-maximum/

Solution :

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/

(There are both Hashing and Sliding-Window + Priority-Queue solution)

Step - 4 : If you are aiming for a really expert level , solve the set - C :)

Set-C : Will come soon!

by Expert (38,790 points)
edited