Deterministic Selection - Select the i th smallest element

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.

How do we get the best pivot - without using randomization, rather deterministic. So, we have to change choose pivot method.

choosePivot(A,n)
-logically break A into n/5 group of size 5 each,
-sort each group
-copy n/5 medians into new array C
-recursively compute median of C
-return pivot

So, now the deterministic select Pseudocode is:

DSelect(array A, length n, order statistic i)
{
  1. Break A into groups of 5, sort each group;
  2. C = the n/5 "middle elements";
  3. p = Select(C,n/5,n/10); //Recursively computes median of C;
  4. Partition A around p;
  5. if(j==i) return p;
  6. if (j<i) return select(1st part of A, j-1,i);
  7. if (j>i) return Select(2nd part of A, n-j,i-j);
}

So, last 3 steps are same as RandomSelect or RSelect. In DSelect we have 2 recursive calls - one to get the pivot p(line 4), and then in last 2 lines(line 7 and 8), based on the situation.

Warning for DSelect algorithm

• Worse constants in time complexity, though overall time complexity is O(n)
• not in place algorithm as we need array C.

History of DSelect in linear time dates back in 1973, when 5 authors Blum - Floyd - Pratt - Rivest - Tarjan came together and found this algorithm. 4 authors except Pratt got the turing awards for different contributions.

Time complexity of DSelect

Step 1 takes O(n) time and not O(n/log n). We have break the array into group of 5. So, time complexity of sorting each group of 5 is O(5 log5) which is nearly 5*3 = 15. But we have n/5 arrays of this, so the overall step takes O(n) time.

Step 2 takes O(n) time, as for each sub array of 5 elements, it takes O(1) time.

Step 3 will be a recurrence, hence T(n/5)

Step 4 takes O(n) again, as we know partitioning takes O(n) time.

Step 5,Step6 and Step 7 depend on how good the pivot is. Recall that in quicksort and random select, we were not able to make a recurrence, as the algorithm was randomized and we didn't knew where the pivot is. But in deterministic approach we can come with worst case recurrence. It is 7n/10.(Proof of this will come letter)

T(1) = 1, T(n) = cn+T(n/5)+T(7n/10)

Here as the sub-problem size is different, we can't use master method directly. So, here we can get the time complexity using "hope and check".  We will hope that there is O(n) time, and come up with this time once using induction.

Read More

Find kth largest in an Array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/kth-largest-element-in-an-array/.

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. So total time complexity = O(k logn) 
• To understand building MAX heap in O(n) check heap.

Method 3 - Modified bubble sort running k times
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(nk)
Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 4 - Use temporary array
K largest elements from arr[0..n-1]
1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min.
3) For each element x in arr[k] to arr[n-1]
If x is greater than the min then remove min from temp[] and insert x.
4) Print final k elements of temp[]
Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Method 5 - Use Min Heap
This method is mainly an optimization of method 4. Instead of using temp[] array, use Min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
       a) If the element is greater than the root then make it root and call heapify for MH
       b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.
Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)
All of the above methods can also be used to find the kth largest (or smallest) element.


Method 6 - Use Sorting
1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).
Time complexity: O(nlogn)

Method 7 - Use Order Statistics
If you want a true O(n) algorithm, as opposed to O(kn) or something like that, then you should use quickselect (it's basically quicksort where you throw out the partition that you're not interested in). This is called finding the k-th order statistics.

There's a very simple randomized algorithm (called quickselect) taking O(n) average time, and a pretty complicated non-randomized algorithm taking O(n) worst case time. There's some info on Wikipedia, but it's not very good.
Everything you need is in these powerpoint slides. Also, refer quicksort and randomized selection to find introductory help on randomized algorithm.


Just to extract the basic algorithm of the O(n) worst-case algorithm:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

The algorithm is discussed in detail here.

Method 8 - Compare 3 elements if N=3 (like wise for N)

int third_biggest(int *arr, int size)
{
 int first = INT_MIN, second = INT_MIN, third = INT_MIN;
 for(int i=0;i first)
  {
   third = second;
   second = first;
   first = arr[i];
  }
  else if(arr[i] > second)
  {
   third = second;
   second = arr[i];
  }
  else if(arr[i] > third)
  {
   third = arr[i];
  }
 }
 return third;
}

Ofcourse, method 7 is best :)

Read More

Randomized Selection : Selecting the i'th smallest element

Input - array A with n distinct numbers and a number i ∈ {1,2,...,n}

Output : i^th order statistic i.e. i^th smallest element of the input array

O(n log n) algorithm
1) Apply mergesort/quicksort
2) Return the i^th 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 i^th one!" We could use MergeSort or even better yet, QuickSort and have it done in O(nlogn). This is called a reduction of our problem: reducing selecting to sorting and then selecting.

Linear time or O(n) solution
Finding the i^th smallest element may seem difficult at first, but is it possible to find some O(n) or linear time solution.

It turns out that we can actually accomplish this task by slighting changing QuickSort. Recall that after partitioning, the pivot stays in its "rightful" spot and doesn't get moved in any of recursive calls later on.   So let's say we're looking for the i^th element and after the first partition, the pivot is at k.

If k=i, then we know we found the i^th element and we're done! If k>i, then recursively partition the left hand side. Otherwise, recursively partition the right side. So, this can be done in 2 ways - randomized as well as deterministic. Deterministic is not that obvious. So, we will take it in the end.

Randomized selection
1) Choose a pivot. We know that the pivot property is like elements less than pivot, lie on left of it and more than it stay on right.

2) We will recurse on the right side of the array. We will

pseudocode

/**A is the input array
i - is the i'th element we have to select
arrayLength= is the length of the array we are assing.
**/
public int RSelect(int[] A, int arrayLength,int i)
{
  if(n==1) return A[1];
  p = choosePivot();
  //partition A around p
  //Let j = new index of p
  if(j==i)   return p;
  if(j>i) return RSelect(1st part of A, j-1,i);
  if(j<i) return RSelect(2nd part of A, n-j,i-j)
}

Running time
What is the running time of this selection algorithm? Well it depends on quality of chosen pivots.
Worst case
If pivots are chosen in the worst possible way every time, then it will be O(n²). This would be if we chose the smallest or largest element every time, reducing the problem by only one element.

What about the best pivot? To get the best pivot, our problem size should decrease significantly. This would be the median. So, problem size will be n/2, and then we do partitioning which takes O(n) time. Using the master method:
T(n) <= T(n/2)+O(n)
which is case 2, and we get that this will run in O(n).

Summary of random-select
Note that randomness is not in data but in code. Also, we find out that selection is moderate problem when compared to sorting, and and hence it took linear time.

Here is the deterministic algorithm for the same.

 Source

Read More

Find the smallest window in a string containing all characters of another string

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.

Solution
 Method 1 ( Brute force solution )
a) Generate all substrings of string1 (“this is a test string”)
b) For each substring, check whether the substring contains all characters of string2 (“tist”)
c) Finally print the smallest substring containing all characters of string2.

Method 2 - Using 2 hashmaps

The main idea is to maintain two pointers which are called begin and end, then use two HashMap to record current status, one record what char need to find, another used to record what has found.

if the two HashMaps show current substring of S has contain all of the chars in T, then we try to shrink our start and end pointer 

Lets see the example

string1 = "acbbaca" and string2 = "aba".
Here, we also use the term "window", which means a contiguous block of characters from string1 (could be interchanged with the term substring).

1. string1 = "acbbaca" and string2 = "aba".
   
   
   
2. The first minimum window is found. Notice that we cannot advance begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would mean breaking the constraint.
   
   
3. The second window is found. begin pointer still points to the first element 'a'. hasFound['a'] (3) is greater than needToFind['a'] (2). We decrement hasFound['a'] by one and advance begin pointer to the right.
   
   
4. We skip 'c' since it is not found in string2. Begin pointer now points to 'b'. hasFound['b'] (2) is greater than needToFind['b'] (1). We decrement hasFound['b'] by one and advance begin pointer to the right.
   
   
5. Begin pointer now points to the next 'b'. hasFound['b'] (1) is equal to needToFind['b'] (1). We stop immediately and this is our newly found minimum window.
   
   

The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing string1. needToFind stores the total count of a character in string2 and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in string2 that's met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals string2's length, we know a valid window is found.

Each time we advance the end pointer (pointing to an element x), we increment hasFound[x] by one. We also increment count by one if hasFound[x] is less than or equal to needToFind[x]. Why? When the constraint is met (that is, count equals to string2's size), we immediately advance begin pointer as far right as possible while maintaining the constraint.

How do we check if it is maintaining the constraint? Assume that begin points to an element x, we check if hasFound[x] is greater than needToFind[x]. If it is, we can decrement hasFound[x] by one and advancing begin pointer without breaking the constraint. On the other hand, if it is not, we stop immediately as advancing begin pointer breaks the window constraint.

Finally, we check if the minimum window length is less than the current minimum. Update the current minimum if a new minimum is found.
Essentially, the algorithm finds the first window that satisfies the constraint, then continue maintaining the constraint throughout.

Code in java

public String minWindow(String S, String T) {
 if (S == null || T == null) {
  return null;
 }
 if (S.length() == 0 && T.length() == 0) {
  return "";
 }
 if (S.length() < T.length()) {
  return "";
 }
 HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();
 HashMap<Character, Integer> alreadyFind = new HashMap<Character, Integer>();
 for (int i = 0; i < T.length(); i++) {
  alreadyFind.put(T.charAt(i), 0);
  if (needFind.containsKey(T.charAt(i))) {
   needFind.put(T.charAt(i), needFind.get(T.charAt(i)) + 1);
  } else {
   needFind.put(T.charAt(i), 1);
  }
 }
 int minStart = -1;
 int minEnd = S.length();
 int start = 0;
 int len = 0;
 for (int i = 0; i < S.length(); i++) {
  if (alreadyFind.containsKey(S.charAt(i))) {
   alreadyFind.put(S.charAt(i), alreadyFind.get(S.charAt(i)) + 1);
   if (alreadyFind.get(S.charAt(i)) <= needFind.get(S.charAt(i))) {
    len++;
   }
   if (len == T.length()) {
    while (!needFind.containsKey(S.charAt(start))
      || alreadyFind.get(S.charAt(start)) > needFind
        .get(S.charAt(start))) {
     if (needFind.containsKey(S.charAt(start))) {
      alreadyFind.put(S.charAt(start),
        alreadyFind.get(S.charAt(start)) - 1);
     }
     start++;
    }
    if (i - start < minEnd - minStart) {
     minStart = start;
     minEnd = i;
    }
   }
  }
 }
 if (minStart == -1) {
  return "";
 }
 return S.substring(minStart, minEnd + 1);
}

References
http://stackoverflow.com/questions/2459653/how-to-find-smallest-substring-which-contains-all-characters-from-a-given-string
http://rleetcode.blogspot.in/2014/01/minimum-window-substring-java.html

Read More