virat9358/arrays

Efficient Approaches

  Sort 012 in O(1) or 3 way partitioning
   Just traverse through the each and every element 
           i                                    
   l_ _ _ _ _ _ _ _ _ h               if current element is 0 swap (l++,i)
                                      if current element is 1 continue
                                      if current element is 2 swap (i,h--)
                                      
  Cyclic rotate in O(n)
   By using reverse function do  : a=[5 6 7 1 2 3 4]     k=3; Imp condition: k may be any value so use k %= n; 
      reverse entire array:      : a=[4 3 2 1 7 6 5]
      reverse starting k elements: a=[1 2 3 4 7 6 5]
      reverse remaining elements : a=[1 2 3 4 5 6 7] 
      
  Count pairs
   If we are counting pairs we need to take care of 
   1. Do we need to count duplicate or distnict, if duplicates
   2. basic and main condition is arr[i] == sum - arr[i]
   
  Best Time to buy and sell stock   and  Maximum difference between increasing element
  1. Update min each time 
  2. Calculate max diff of elements          In this case max diff = 0(if decreasing order 9 8 7 7 6), so return -1
  
  Buying and selling atmost twice
     Initializing variable valley-peak approach
	   
		                80
		               /
		30            /
	       /  \          25
	      /    15       /
	     /      \      /
	    2        10   /
		       \ /
		        8 
  Longest consecutive sequence: Just map or set to find next element and update leng
  1 2 3 4 100 150 151 400 without sorting we can do that
  
  Min swaps required to bring K elemenst together
  
  Maximum sum path
        arr1: i sum1
        arr2: j sum2
                 if arr1[i] < arr2[j]: s1 += arr1[i++]
                 if arr2[j] < arr1[i]: s2 += arr2[j++]
                 if both elements are equal then update or shifting from 1 to another  
      
  
  Max value: (A[i] - i) - (A[j] - j)
  Treat like max = A[i] - i  Traverse single time find max and min at a time
  		min = A[j] - j 
  			 
  **Remark need to go log n**Sum of middle elements of 2 sorted array  Extension:Median of 2 sorted Array of different size
       using count method find n/2 element if odd 
       find n/2- 1 and n/2 if even bcz array sorted
       need to traverse only (n1+n2)/2 elements 
       
  Maximize the array
  	we need to take max elements from both the array
  	use set for removing duplicated and sorting
  	and push according to priority
  	
  Sorted subsequence of size 3 and Increasing Triplet
	Same conditions but approach is different for sorted frst increasing then index
	for triplet first index any order then increasing

  K difference pairs
  	In this k is >= 0, so always need to check (x + k) present or not only unqiue pairs means
  	no need to consider duplicate elements so use map or set
  	and check k = 0 case, [1, 1, 1, 1] only 1 single pair so k == 0 and x.second > 1: ans++	
  	
  First Missing positive
  	Just need to keep 5 in A[4] consider only non-neg nums, bcz frst +ve
  

XOR Concept

  Pair with given xor in O(n)
  	Need to Update it
  

Subarray concept

  Subarray with sum zero  Extension:Subarray with equal no.of 0's and 1's
  	basic concept 0 + sum = sum - 0 = sum,           Just need to convert 0 to -1 and 
  	so adding any value to zero gives that result    and apply base concept problem
  	so need to keep track of previous sums
    for that we need map approach
   
  Subarray sum divisible by k   Extension:Longest subarray with sum divisible by k
  	divisible means remainder 0                                                Same concept just need to store index and update it
	sum += arr[i]                                                              m[0] = -1 // Imp
  	rem = ((sum % k) + n)) % k; //remainder can be neg also to avoid that
  	apply above problem base logic
  	
  Wiggle sort 2
  	Need to comeup with O(n)solution
  	
  Non Decreasing array
  	Update not satisifying element based on prev elements value, only one time, if more than that return false
  

BASIC

  Triplet sum Four elements
  	sort the array
  

NOTE

  Kadanes Alogrithm
   Make a parallel array as ans array then update as:
        sum=0   ans=INT_MIN
        a: [ 1 -5  4  9  8 -10 6]
      sum: [ 1 -4  4  13 21 11 17]
      ans: [ 1  1  4  13 21 21 21]
   
  Trapping rain water
      for filling part
     we need to know the left and right end for particular bar in O(1)
     so we need to keep track of 2 arrays
  
  Tips:
  When we are searching check possibility for binary search