22. Sliding Window & 2 pointer

Conditions for Sliding Window-

  1. Monotonic condition
  2. Subarray sum problems with positive numbers
  3. Window validity behave predictably upon expand / shrink
If, above conditions gets violated in a subarray problem, we go with below methods-
1. prefix sum + hashmap
2. DP
3. Binary Search
---------------------------------------------------------------------------------------------------------------------------

4 Patterns in Sliding Window-
(striver)

1. Fix window-

❄️ Build 1st window of size k => slide window (L++, R++) => update state =>update ans
-----------------------------------------------------
2. Variable window-1
- (Find longest subarray satisfying a condition )
- for each R, smallest index L, which keeps window valid, is chosen.

❄️expand R => while window invalid: (shrink L) => now, update answer
---------------------------------------------------

3. Variable window-2
- (Count subarrays satisfying a condition )
- (current window invalid => all larger windows are invalid)
- (current window valid => all smaller windows are valid)
- for each R, smallest L which keeps window valid is chosen

❄️expand R => while window invalid: (shrink L) => now, update cnt += (R-L+1)
------------------------------------------------

4. Shortest window⭐
- (find smallest subarray with a given condition )
- (current window invalid => all larger windows are invalid)
- expand till current window is invalid => once valid, now shrink it to make it as small as possible => when it becomes invalid, stop shrinking => continue expanding

❄️ expand R => while window is valid (update ans & shrink L ) => repeat
---------------------------------------------------------------------------------------------------------------------------

4 Patterns in Sliding Window-
(me)
1. Fixed window
2. At most K bad elements
3. Exactly K elements (via, at most K - at most K-1)
4. Shortest Valid window
--------------------------------------------------------------------------------------------------------------------------

1. Find length of longest substring-
 (with all distinct characters)
----------------------------
Brute- time: O(n^2)   space: O(n)

go through all substrings and check if they contain unique characters or not using a map
------------------------------------------------------
Optimal- time: O(n)  space: O(n)

use sliding window with hashmap storing character, index of appearance

1. if character at j-th index already appeared in current window, then shift i accordingly
2. update the map with current character and its index of appearance
3. update answer with max length of substring
4. move j
----------------------------------------------------------------------------------------------------------------------------
2. Max Consecutive 1s- (III)
(with at most K zeros)
Brute- time: O(n^3)

1. Try every subarray
2. For every (i,j): count how many zeros are in v[i..j]
3. If zeros ≤ k, update answer
-----------------------------------------------
Better- time: O(n^2)
instead of using a for loop to count no. of zeros in i to j, we use prefix array to store at every index how many zeros are from 0 to i, thus-

no. of zeros from i...j = ( pref [j] - pref [i-1] )
---------------------------------------------
Optimal- time: O(n)

use sliding window pattern-3
---------------------------------------------------------------------------------------------------------------------------

3. Fruits into Baskets-
( Longest subarray with at most 2 distinct elements )

Brute- time: O(n^2)    space: O(n)

using 2 for loops & a set

----------------------------------------------------
Optimal- time: O(2n)   space: O(n)

use, sliding window + hashmap
here, k = 2

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

4. Longest repeating character replacement⭐

Longest substring that needs at most k changes to become all same characters. ---------------
Brute-  
count in each substring ki jitne char change krne vo number k se chota hai kya
-------------------------------------------------------------
Optimal- 


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

5. Count binary subarrays with sum=K 

Optimal- time: O(n)

using my sliding window pattern-3 of :
count(=k) = count( <= k) - count( <= k-1)

-----------------------------------------------------------------------------------------------------------------------------
6.  Count nice subarrays-
(i.e., with k odd numbers)

Brute- time: O(n^3)     space: O(1)
use 2 loops to generate all subarrays and for each subarray from i to j, run another loop to count number of odd numbers in this subarray

-----------
Better- time: O(n^2)   space: O(n)

instead of running a third loop in brute force, we would use a prefix array storing number of odd numbers from 0 to index i at pref[i] , thus now we can find number of odd numbers in i to j, as 
pref [j] - pref [i-1]

-----------
Optimal- time:O(n)

use sliding window pattern 3 of mine-
count(=k) = count(<=k) - count(<= k-1)
-----------------------------------------------------------------------------------------------------------------------------

7. Substring containing all 3 characters-⭐

Brute- time: O(n^2)   space: O(1)

generate all substrings, keep a track of frequencies of all 3 characters, when frequencies of all three characters in a substring is non zero, then do cnt ++ 

----------------------------------------------------------------
Better- ⭐

instead of doing cnt++
we will do cnt += (n-j)
since when a first substring containing all 3 characters is found, then all later substrings also counted, hence we do (n-j) to count all later substrings (which are extension of current substring) at once.
----------------------------------------------------------

Optimal- time: O(n)⭐

using minimal valid window concept

for every i, we will find first valid substring starting from i-th index, and then cnt all valid substrings starting from this index...
-----------------------------------------------------------------------------------------------------------------------------

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

10. Subarrays with K different integers-

Brute-

--------------------------------------------------
Better-
?
-----------------------------------------------------------------------------------------------------------------------------

11. Minimum window substring-

Brute-


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

Better-



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

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

19. Strings (LB)

Image
Character Array- 1. We use  1d character array  to simulate strings, e.g., char ch[10]; cin>>ch; 2. string ends with '\0' 3. cin with string works only if till space, tab or new line is absent in input... 4. work with character array just like a normal array, here only datatype is changed to char, else wise it is just an array -------------------------------------------- 5. In-Built functions- - int n = strlen(ch)   - strcmp(s1,s2)            // gives 0 if both strings are equal  - strcpy(dest,source)   // copies a string from dest to source -------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- It is a C++ STL 1. has dynamic size (can dynamically increase size when needed) 2. null terminator (\0) NOT required 3. Has built-in functions : - return s.size() - return s == "hello" - return s + "wor...
Read more

32. Binary Trees-2 (bfs/dfs med problems)

Image
Medium problems- more imp---------------------- height            ✅ diameter        ✅ max path sum✅⭐ Height Balanced BT check✅ identical BT check✅ Symmetric BT check✅⭐ medium imp------------------- Zig Zag traversal✅ Boundary Traversal✅ Vertical order Traversal✅⭐ less imp---------------------------- Top view ✅⭐ Bottom view✅ Right/ Left view✅ ----------------------------------------------------------------------------------------------------------------------------- 1. Max Depth of BT- height(tree)  =    n(nodes) in longest path from top to bottom time-N          space-N ----------------------------------------------------------------------------------------------------------------------------- 2. Balanced BT check- it means for every   node:      [ H(left) - H(right) ] <=1 Brute-          time: O(n^2) -------------------------------------------...
Read more