Sub-arrays

 1.  Find maximum sum of a subarray

Brute- time: O(n^2)
go through each subarray and thus find the maximum sum

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

use Kadane Algorithm
at each element either extend old subarray or start a new one.

Handles negatives as well as positives
-----------------------------------------------------------------------------------------------------------------------------

2. Find maximum sum of subarray of size K

only positives-

use sliding window of fix size K,
and move both pointers simultaneously thus simulating fix window traversing array
 
-----------------------------------------------------------------------------------------------------------------------------

3. Find maximum sum of distinct subarray of size K

Brute-  time: O(nK)    space: O(n)
Use hashing ,
after each expansion and shrinking of sub array, check if this subarray contains duplicates or not.
-----------------------------
Optimal- time: O(n)   space: O(n)
instead of checking each time if subarray contains duplicates or not, we will use a distinct counter
---------------------------------------------------------------------------------------------------------------------------
4. Find length of longest subarray with sum <= K
(array has only non negatives)

we use sliding window
----------------------------------------------------------------------------------------------------------------------------

5. Find length of longest subarray with sum = K

Case-1: both positives & negatives

we use prefix sum + hashing

---------------------------------------------------------------------------------------------------------------------------
Note-
In questions of printing subarrays or subsequences, we have to have to do with brute force, no other option .
---------------------------------------------------------------------------------------------------------------------------

6. Count subarrays with sum = K

Case-1: only positives

use sliding window pattern-3

--------------------------------------------------
Case-2: non negatives

use below identity:
count(sum = k) = count(sum ≤ k) − count(sum ≤ k−1)
--------------------------------------------------

Case-3: both positives & negatives

use prefix sum + hashmap


---------------------------------------------------------------------------------------------------------------
7. Find sum of all subarray minimums

Approach- use contribution technique
instead of finding in each subarray the minimum element, 
we will find for each element in how many subarrays can it act as minimum element
and thus we can find contribution of this element in the final sum



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

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

36. Graphs-2 (grid/traversal problems)

Image
 PROBLEMS ON BFS/ DFS:- no. of provinces          ✅ components rotten oranges            ⭐✅ multi source BFS no. of islands              ✅ BFS/ DFS flood fill                     ✅ BFS/ DFS no. of enclaves           ⭐✅ multi source   BFS/DFS no. of distinct islands ⭐✅ shape storing   BFS/ DFS surrounded regions    ✅ multi source   BFS/DFS 0/1 Matrix                  ⭐⭐✅ multi source BFS word ladder-1 , 2 ---------------------------------------------------------------------------------------------------------------------------- 1. No. of provinces Count total components in a graph time- O(N + V+2E)               space: O(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