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 
• 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);
-----------------------------------------------------------

----------------------------------------------------------
# The 7 Optimisation techniques- (PHP bsG)

1. 2-pointer, 3-pointer, 4-pointer ( n2 to n )
2. hashing ( n to 1 )
3. prefix sum (pre-computation for repeated queries) 
4. monotonicity: 
1. binary search 
2. sliding window (n2 to n)
3. stack
4. greedy

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

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:

use when you are sure that something is monotonic (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 a given n length sequence,
we have [ ceil(n/2) = (n+1)/2 ] number of even positions
& floor(n/2) number of 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)

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