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, max value of nums[i] can be 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

# Reduce 2 pass mapping solution to 1 pass, if we 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 are sure that something is monotonic, which may be a count, sum, etc.
(example: longest subarray with sum K)
--------------------------------------------------------

-----------------------------------------------------------
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 - I
-------------------------------------------------------

17. Transposing a given matrix:

swap all off diagonal elements where i>j
------------------------------------------------------

18. Optimisation in subarrays problems:-

check the constraint in the following order and apply corresponding technique

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

19. Divide & 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 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 .

-------------------------------------------------------
22. 

------------------------------------------------------------
23. Count paths with some optimal property:

Run the optimiser (here, Dijkstra) & carry a count[] array, alongside dist[],
update counts whenever you find equal-cost paths.
------------------------------------------------------------
24. For n length sequence,
we have ceil(n/2) = (n+1)/2 even positions
& floor(n/2) odd positions
-------
25. vector:   fill VS assign VS resize

-------------------------
26.

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

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

INT_MAX is (2^31) - 1
INT_MIN is (-2^31)

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