22. Sliding Window & 2 pointer

4 PATTERNS IN SLIDING WINDOW QUESTION-

  • constant window
  • longest subarray
  • no of subarrays
  • shotest window (imp)--when u r not sure of shrinking/ expanding

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

1.) Constant Window-

e.g., subarray with max sum and length 'k'

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

2.) Longest subarray or substring problem with a condition-

go from brute-->better-->optimal

e.g., longest subarray with sum<k

--------

BETTER- [ time- O(2N) ]

1. start with window of size 1

2. expand and shrink window size

3. when condition violated shrink till condition again becomes true

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

OPTIMAL- ( time-O(N) )

shrinking ko khatam krke O(n) me krenge...

shrinking bahut barr krne se acha ek baar krdo bas 

BUT, if asked to print all subarrays then nothing can be done to reduce 2n

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

3.) No.Of Subarrays-(with given cond)

-------------------------------------------------------------------------------------------------------------------------
4.) Finding Shortest / minimum window with a given condition (RARE)

here firstly we will find a possible window and then try to shrink it to get an answer.

---------------------------------------------------------------------------------------------------------------------------
QUESTIONS-

1.) LONGEST  SUBSTRING  WITHOUT  REPEATING  CHARACTERS-

Brute- (n^2 )mein krdo using hash array

Optimal-

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

2.) Consecutive Ones-
Better-
mere submission me while loop lagado instead of a vector use zeros variable

OPTIMAL-









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

3. ) Fruits into Baskets-

Longest subarray with atmost k distinct elements

BRUTE- (n^2)   saare subarrays lelo, i.e., a[0] se bharne start kro ek set m aur len ka count kro jaise hi set m                   2 se jyada elmts aaye ruk jaao aur a[1] se start kro and so on...

BETTER- (2n)--    sliding window


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

4.) Substring containing all 3 characters-

BRUTE-

minor optimisation-

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

finding minimal valid window-


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

5. ) Longest repeating character replacement-

BRUTE-  
count in each substring ki jitne char change krne vo number k se chota hai kya
BETTER- 


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

6.) COUNT no of Binary Subarrays with Sum k-

with sum k wale = (with sum<=k wale) + (with sum <= (k-1) wale)

with sum <=k walo me agar mera sum ni badalra even after r++ and condn of sum<=k is also satisfied then cnt ko utne se badha do jitne subarrays possible hain till the current r, and that is nothing but          r-l+1 like i=2 pe ho toh 3 possible hain...


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

7.) Subarrays with K different integers-

Brute-


Better-

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

8.) Minimum window substring-

BRUTE-








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

BETTER-


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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more