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 anotherMax 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
Pair with given xor in O(n) Need to Update it
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
Triplet sum Four elements sort the array
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 waterfor 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
