1 like 0 dislike

retagged

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 :

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..

Solution video :

(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 :

0)

2)

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 (112,910 points)
edited