Extra Masala

1. Pass By Pointers:- fn argument mein use (*) 
                                  fn call mein use (&)
------------------------------------------------------------
2. lower and upper bound works only with sorted stuff...
-----------------------------------------------------------

3. in multimap, mpp[k] not used, as keys ain't unique anymore...
Hence, we work with a multimap as follows:

mpp.insert( {1:"apple"} )
auto it = mpp.find(1)
cout << (it → second)
-----------------------------------------------------------

4. Typecast:-

char ch = 'a'     
int y = (int)ch     or    int y = 'a'

-----------------------------------------------------------
5. Observations:-
  • we can use 2 pointer for yes/ no type check wale questions 
  • Subarray- contigous       VS      subsequence- non contigous
  • In arrays questions, notice if array contain 0s or negatives & proceed accordingly with edge cases.
  • For small ranges (upto 1e5), prefer hashing
  • For large ranges, (upto 1e9), prefer mapping
  • For questions involving duplicates, make code for uniques and modify later as required
----------------------------------------------------------------
6.  Some useful built in C++ functions:

  • index = it - v.begin()
  • int summ = accumulate(v.begin(), v.end(), 0);
  • gcd(a, b);    
  • sqrt(x);
  • reverse(arr, arr+n);

------------------------------------------------------------
7. If you are making a function to solve a ques such that it takes 2 things- a & b and u want to solve like ki humesha pehle wala yaani a mera chota ho then u can do-  if[a.size()>b.size()] return fn(b,a);
---------------------------------------------------------
8. 

----------------------------------------------------------
9. Some Optimisation techniques-

  • 2-pointer, 3-pointer, 4-pointer
  • hashing ( hash array or hash map )
  • prefix sum
  • Linear search < hashing < mapping
  • monotonicity:

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

10. No. of subarrays = n(n+1)/2

11.  Important XOR properties:-

  • a ^ a = 0    
  • 0 ^ a = a    
  • xor(a, b, c, d) <= max(a, b, c, d)

12.  matrix is a vector of vectors

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

13. Out of Bounds Fix-

INT_MAX ~  2*(1e9) 

so if in a ques nums[i] <= 2*(10^9)
so we can still store nums[i] in int,
but we need to use long long for smtg like nums[i]+nums[j],

---------------------------------------------------------
14. Important Stuff about maps:

inserting N elements in ordered map: NlogN

inserting N elements in unordered map: N

we can reduce two pass mapping solution to one pass, if are sure that we can do this:
1. check if answer already exists in map
2. if not, then we insert curr element in the map

----------------------------------------------------------------
15. Sliding window condition:

We always use a sliding window approach wherever we have surity that something is monotonic, which may be a count, sum, etc. (For example: finding longest subarray with sum K problem)
--------------------------------------------------------

------------------------------------------------------------
16. Sometimes, if we can't think of a solution in forward way, then we may come up with solution if we start to think in the reverse or the opposite way. E.g., buy & sell stock-1

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

17. Transposing a given matrix:
traverse the matrix and swap( m[i][j] , m[j][i] )
------------------------------------------------------

18. Optimisation in subarrays problems:-
Check the conditions given in brackets below in the given order, and apply whichever technique fits as per problem constraints

---------------------------------------------------------------------------------------------------------------
19. Divide and Conquer Decision Tree:-
     1. if problem is about pairs or relationships
     2. condition depend on relative order of elements
     3. if we can split pairs or array into two halves
     4. Will sorting the halves simplify the condition

If the problem is about counting order-dependent pairs and sorting halves makes counting easy → use merge sort D&C
-------------------------------------------------------------
20. Note-
  • in C++, Instead of ceil (x/y) , we prefer to use: (x+y-1)/y
  • if nums[i] can be upto 1e6, then while calculating sum, use long long instead of int
-------------------------------------------------------------------
21. Median-
  • in an odd sized sorted list of numbers, median is (n/2)th element as per 0-based indexing & (n/2 + 1)th element as per 1-based indexing
  • in 1 based indexing , median is an element which has exactly (n/2 + 1) elements which are <= median .
--------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------
signed => sign waale number => matlab + aur - waale dono
ab negative waalo k liye 32 mein se 1 bit toh sign ki hai toh range hogyi
-2^31 se (2^31)-1
---------------------------------------------------------------------------------------------------------------

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