smallest

We have already seen RSelect or Random Selection here. Now lets focus on DSelect. Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort. [Read More]

**Problem : **  You have an array of numbers; you need to find the k-th largest in the arra Solution ** Method 1 - Tournament principle** We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]

Input - array A with n distinct numbers and a number i ∈ {1,2,…,n} Output : ith order statistic i.e. ith smallest element of the input array O(n log n) algorithm Apply mergesort/quicksort Return the ith element of sorted array So, we used reduction via taking the help of sorting algorithm. So this was the naive way as we would be to say, “Hey let’s sort it and then we can just pick out the ith one! [Read More]

Problem Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example S = “ADOBECODEBANC”, T = “ABC”, Minimum window is “BANC”. Note: If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. [Read More]