K’th Smallest/Largest Element in Unsorted Array. GFG Algo: Sorting, Min or Max heap K’th Smallest/Largest Element in Unsorted Array (Expected Linear Time). GFG Algo: QuickSelect Find all elements in array which have at-least two greater elements. GFG 1. Sorting. O(n Log n) 2. Finding the second max and printing all elements smaller than it. O(n)… Continue reading Array Set 4 | Order Statistics
Category: Array
Searching Problem List
Interpolation Search. Youtube. GFS. The search works well for uniformly distributed numbers. Formula Calculation - So the formula to estimate the position = pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ] arr[] ==> Array where elements need to be searched x ==> Element to be searched lo ==> Starting index in arr[] hi ==>… Continue reading Searching Problem List
Array Set 3
Array Set 1 Array Set 2 1, 2, 4, 5, 14, 15, *17, *18, *19, *20, *21, 23, 24, 25, 26, 27, 28 Basics - Hash, Sort, XOR, Array element as index, Simple traversal *** Given an array of of size n and a number k, find all elements that appear more than n/k times.… Continue reading Array Set 3
Array – Java
Very basic way to use java array - You can either use array declaration or array literal (but only when you declare and affect the variable right away, array literals cannot be used for re-assigning an array).For primitive types: int[] myIntArray = new int[3]; int[] myIntArray = {1,2,3}; int[] myIntArray = new int[]{1,2,3}; For classes,… Continue reading Array – Java
Array – Set 1
Array - Set 2 Array Set 3 Important -> 1 - 6, 9, 10, 11 -13, 20, 21, 23, 24 Binary Search -> 16, 21, 24, 25, 26, 27 More Array Problems - TR , InterviewBit last set bit = a & ~(a-1) counting number of set bit = while a > 0: a & (a-1)… Continue reading Array – Set 1
Array Set 2
Array Set 1, Array Set 3 Important -> 1, *2, 7, 8, 11, 12, *14, *15, *17, 18 Binary Search -> 6 Prefix Sum -> 17 Basics – Hash, Sort, XOR, Array element as index, Simple traversal ** Find the element that appears once - Given an array where every element occurs three times, except… Continue reading Array Set 2
Lets Code