Question

Best Roadmap to prepare Sliding Window in DSA for coding interviews | 2022 | Kumar K | DesiQnA |

Answer 1

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

Complete DSA Roadmap :- https://www.desiqna.in/4963/roadmap-for-dsa-data-structures-algorithms-kumar-desi-2022 

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. 

Hashing sheet : https://www.desiqna.in/4678/best-roadmap-prepare-hashing-coding-interviews-kumar-desiqna

Two-Pointer sheet : https://www.desiqna.in/4914/best-roadmap-prepare-pointers-coding-interviews-2022-desiqna

Step - 0 : 

Watch this video to understand the concept of sliding window :

Nice write-up : https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66

 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 : 

P1 : https://www.geeksforgeeks.org/sum-of-all-subarrays-of-size-k/

(Very Important to clear up your fundamentals)

P2 : Find maximum sum subarray of size 'K' 

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

P3 : https://www.geeksforgeeks.org/subarray-of-size-k-with-given-sum/

 Solution : https://www.geeksforgeeks.org/find-maximum-minimum-sum-subarray-size-k/

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

P5 : https://leetcode.com/problems/get-equal-substrings-within-budget/

Step - 2 : Read this and expand + broaden your knowledge  - https://leetcode.com/discuss/general-discussion/657507/Sliding-Window-for-Beginners-Problems-or-Template-or-Sample-Solutions

 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)

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

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

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

P3 : https://leetcode.com/problems/minimum-size-subarray-sum/

P4 : https://www.geeksforgeeks.org/maximum-possible-sum-window-array-elements-window-array-unique/

P5 :  https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/

P6 : https://www.geeksforgeeks.org/first-negative-integer-every-window-size-k/

P7 : https://leetcode.com/problems/minimum-window-substring/

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

Set-C : Will come soon!