Trang chủ‎ > ‎IT‎ > ‎Programming‎ > ‎Algorithms Design‎ > ‎

### K’th Smallest/Largest Element in Unsorted Array

Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10


We have discussed a similar problem to print k largest elements.

## Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

Method 1 (Simple Solution)
A Simple Solution is to sort the given array using a O(nlogn) sorting algorithm like Merge Sort, Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(nLogn).

## C++

 // Simple C++ program to find k'th smallest element  #include  #include  using namespace std; // Function to return k'th smallest element in a given array  int kthSmallest(int arr[], int n, int k)  {      // Sort the given array      sort(arr, arr+n);         // Return k'th element in the sorted array      return arr[k-1];  }     // Driver program to test above methods  int main()  {      int arr[] = {12, 3, 5, 7, 19};      int n = sizeof(arr)/sizeof(arr[0]), k = 2;      cout << "K'th smallest element is " <<  kthSmallest(arr, n, k);      return 0;  }

K'th smallest element is 5

Method 2 (Using Min Heap – HeapSelect)
We can find k’th smallest element in time complexity better than O(nLogn). A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.
The following is C++ implementation of above method.

 // A C++ program to find k'th smallest element using min heap  #include  #include  using namespace std;     // Prototype of a utility function to swap two integers  void swap(int *x, int *y);     // A class for Min Heap  class MinHeap  {      int *harr; // pointer to array of elements in heap      int capacity; // maximum possible size of min heap      int heap_size; // Current number of elements in min heap  public:      MinHeap(int a[], int size); // Constructor      void MinHeapify(int i);  //To minheapify subtree rooted with index i      int parent(int i) { return (i-1)/2; }      int left(int i) { return (2*i + 1); }      int right(int i) { return (2*i + 2); }         int extractMin();  // extracts root (minimum) element      int getMin() { return harr[0]; } // Returns minimum  };     MinHeap::MinHeap(int a[], int size)  {      heap_size = size;      harr = a;  // store address of array      int i = (heap_size - 1)/2;      while (i >= 0)      {          MinHeapify(i);          i--;      }  }     // Method to remove minimum element (or root) from min heap  int MinHeap::extractMin()  {      if (heap_size == 0)          return INT_MAX;         // Store the minimum vakue.      int root = harr[0];         // If there are more than 1 items, move the last item to root      // and call heapify.      if (heap_size > 1)      {          harr[0] = harr[heap_size-1];          MinHeapify(0);      }      heap_size--;         return root;  }     // A recursive method to heapify a subtree with root at given index  // This method assumes that the subtrees are already heapified  void MinHeap::MinHeapify(int i)  {      int l = left(i);      int r = right(i);      int smallest = i;      if (l < heap_size && harr[l] < harr[i])          smallest = l;      if (r < heap_size && harr[r] < harr[smallest])          smallest = r;      if (smallest != i)      {          swap(&harr[i], &harr[smallest]);          MinHeapify(smallest);      }  }     // A utility function to swap two elements  void swap(int *x, int *y)  {      int temp = *x;      *x = *y;      *y = temp;  }     // Function to return k'th smallest element in a given array  int kthSmallest(int arr[], int n, int k)  {      // Build a heap of n elements: O(n) time      MinHeap mh(arr, n);         // Do extract min (k-1) times      for (int i=0; i

Output:

K'th smallest element is 5 

Time complexity of this solution is O(n + kLogn).

Method 3 (Using Max-Heap)
We can also use Max Heap for finding the k’th smallest element. Following is algorithm.
1) Build a Max-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 k’th element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is less 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, root of the MH is the kth smallest element.

Time complexity of this solution is O(k + (n-k)*Logk)

The following is C++ implementation of above algorithm

 // A C++ program to find k'th smallest element using max heap  #include  #include  using namespace std;     // Prototype of a utility function to swap two integers  void swap(int *x, int *y);     // A class for Max Heap  class MaxHeap  {      int *harr; // pointer to array of elements in heap      int capacity; // maximum possible size of max heap      int heap_size; // Current number of elements in max heap  public:      MaxHeap(int a[], int size); // Constructor      void maxHeapify(int i);  //To maxHeapify subtree rooted with index i      int parent(int i) { return (i-1)/2; }      int left(int i) { return (2*i + 1); }      int right(int i) { return (2*i + 2); }         int extractMax();  // extracts root (maximum) element      int getMax() { return harr[0]; } // Returns maximum         // to replace root with new node x and heapify() new root      void replaceMax(int x) { harr[0] = x;  maxHeapify(0); }  };     MaxHeap::MaxHeap(int a[], int size)  {      heap_size = size;      harr = a;  // store address of array      int i = (heap_size - 1)/2;      while (i >= 0)      {          maxHeapify(i);          i--;      }  }     // Method to remove maximum element (or root) from max heap  int MaxHeap::extractMax()  {      if (heap_size == 0)          return INT_MAX;         // Store the maximum vakue.      int root = harr[0];         // If there are more than 1 items, move the last item to root      // and call heapify.      if (heap_size > 1)      {          harr[0] = harr[heap_size-1];          maxHeapify(0);      }      heap_size--;         return root;  }     // A recursive method to heapify a subtree with root at given index  // This method assumes that the subtrees are already heapified  void MaxHeap::maxHeapify(int i)  {      int l = left(i);      int r = right(i);      int largest = i;      if (l < heap_size && harr[l] > harr[i])          largest = l;      if (r < heap_size && harr[r] > harr[largest])          largest = r;      if (largest != i)      {          swap(&harr[i], &harr[largest]);          maxHeapify(largest);      }  }     // A utility function to swap two elements  void swap(int *x, int *y)  {      int temp = *x;      *x = *y;      *y = temp;  }     // Function to return k'th largest element in a given array  int kthSmallest(int arr[], int n, int k)  {      // Build a heap of first k elements: O(k) time      MaxHeap mh(arr, k);         // Process remaining n-k elements.  If current element is      // smaller than root, replace root with current element      for (int i=k; i

Output:

K'th smallest element is 5

Method 4 (QuickSelect)
This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.

## C++

 #include  #include  using namespace std;     int partition(int arr[], int l, int r);     // This function returns k'th smallest element in arr[l..r] using  // QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT  int kthSmallest(int arr[], int l, int r, int k)  {      // If k is smaller than number of elements in array      if (k > 0 && k <= r - l + 1)      {          // Partition the array around last element and get          // position of pivot element in sorted array          int pos = partition(arr, l, r);             // If position is same as k          if (pos-l == k-1)              return arr[pos];          if (pos-l > k-1)  // If position is more, recur for left subarray              return kthSmallest(arr, l, pos-1, k);             // Else recur for right subarray          return kthSmallest(arr, pos+1, r, k-pos+l-1);      }         // If k is more than number of elements in array      return INT_MAX;  }     void swap(int *a, int *b)  {      int temp = *a;      *a = *b;      *b = temp;  }     // Standard partition process of QuickSort().  It considers the last  // element as pivot and moves all smaller element to left of it  // and greater elements to right  int partition(int arr[], int l, int r)  {      int x = arr[r], i = l;      for (int j = l; j <= r - 1; j++)      {          if (arr[j] <= x)          {              swap(&arr[i], &arr[j]);              i++;          }      }      swap(&arr[i], &arr[r]);      return i;  }     // Driver program to test above methods  int main()  {      int arr[] = {12, 3, 5, 7, 4, 19, 26};      int n = sizeof(arr)/sizeof(arr[0]), k = 3;      cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);      return 0;  } 

Output:
K'th smallest element is 5

There are two more solutions which are better than above discussed ones: One solution is to do randomized version of quickSelect() and other solution is worst case linear time algorithm (see the following posts).

=============================================================================

# K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)

We recommend reading following post as a prerequisite of this post.

K’th Smallest/Largest Element in Unsorted Array | Set 1

Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10

We have discussed three different solutions here.

## Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

In this post method 4 is discussed which is mainly an extension of method 3 (QuickSelect) discussed in the previous post. The idea is to randomly pick a pivot element. To implement randomized partition, we use a random function, rand() to generate index between l and r, swap the element at randomly generated index with the last element, and finally call the standard partition process which uses last element as pivot.

Following is an implementation of above Randomized QuickSelect.

## C/C++

 // C++ implementation of randomized quickSelect  #include  #include  #include  using namespace std;     int randomPartition(int arr[], int l, int r);     // This function returns k'th smallest element in arr[l..r] using  // QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT  int kthSmallest(int arr[], int l, int r, int k)  {      // If k is smaller than number of elements in array      if (k > 0 && k <= r - l + 1)      {          // Partition the array around a random element and          // get position of pivot element in sorted array          int pos = randomPartition(arr, l, r);             // If position is same as k          if (pos-l == k-1)              return arr[pos];          if (pos-l > k-1)  // If position is more, recur for left subarray              return kthSmallest(arr, l, pos-1, k);             // Else recur for right subarray          return kthSmallest(arr, pos+1, r, k-pos+l-1);      }         // If k is more than the number of elements in the array      return INT_MAX;  }     void swap(int *a, int *b)  {      int temp = *a;      *a = *b;      *b = temp;  }     // Standard partition process of QuickSort().  It considers the last  // element as pivot and moves all smaller element to left of it and  // greater elements to right. This function is used by randomPartition()  int partition(int arr[], int l, int r)  {      int x = arr[r], i = l;      for (int j = l; j <= r - 1; j++)      {          if (arr[j] <= x)          {              swap(&arr[i], &arr[j]);              i++;          }      }      swap(&arr[i], &arr[r]);      return i;  }     // Picks a random pivot element between l and r and partitions  // arr[l..r] around the randomly picked element using partition()  int randomPartition(int arr[], int l, int r)  {      int n = r-l+1;      int pivot = rand() % n;      swap(&arr[l + pivot], &arr[r]);      return partition(arr, l, r);  }     // Driver program to test above methods  int main()  {      int arr[] = {12, 3, 5, 7, 4, 19, 26};      int n = sizeof(arr)/sizeof(arr[0]), k = 3;      cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);      return 0;  }

Output:

K'th smallest element is 5

Time Complexity:
The worst case time complexity of the above solution is still O(n2). In worst case, the randomized function may always pick a corner element. The expected time complexity of above randomized QuickSelect is ?(n), see CLRS book or MIT video lecture for proof. The assumption in the analysis is, random number generator is equally likely to generate any number in the input range.

=============================================================================

# K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)

We recommend to read following post as a prerequisite of this post.

K’th Smallest/Largest Element in Unsorted Array | Set 1

Given an array and a number k where k is smaller than size of array, we need to find the k’th largest element in the given array. It is given that ll array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10

We have discussed three different solutions here.

In this post method 4 is discussed which is mainly an extension of method 3 (QuickSelect) discussed in the previous post.

 #include  #include  #include  using namespace std;     int randomPartition(int arr[], int l, int r);     // This function returns k'th smallest element in arr[l..r] using  // QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT  int kthSmallest(int arr[], int l, int r, int k)  {      // If k is smaller than number of elements in array      if (k > 0 && k <= r - l + 1)      {          // Partition the array around last element and get          // position of pivot element in sorted array          int pos = randomPartition(arr, l, r);             // If position is same as k          if (pos-l == k-1)              return arr[pos];          if (pos-l > k-1)  // If position is more, recur for left subarray              return kthSmallest(arr, l, pos-1, k);             // Else recur for right subarray          return kthSmallest(arr, pos+1, r, k-pos+l-1);      }         // If k is more than number of elements in array      return INT_MAX;  }     void swap(int *a, int *b)  {      int temp = *a;      *a = *b;      *b = temp;  }     // Standard partition process of QuickSort().  It considers the last  // element as pivot and moves all smaller element to left of it  // and greater elements to right  int partition(int arr[], int l, int r)  {      int x = arr[r], i = l;      for (int j = l; j <= r - 1; j++)      {          if (arr[j] <= x)          {              swap(&arr[i], &arr[j]);              i++;          }      }      swap(&arr[i], &arr[r]);      return i;  }     int randomPartition(int arr[], int l, int r)  {      int n = r-l+1;      int pivot = rand() % n;      swap(&arr[l + pivot], &arr[r]);      return partition(arr, l, r);  }     // Driver program to test above methods  int main()  {      int arr[] = {12, 3, 5, 7, 4, 19, 26};      int n = sizeof(arr)/sizeof(arr[0]), k = 3;      cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);      return 0;  }

Copy CodeRun on IDE

=============================================================================

# K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)

We recommend reading following posts as a prerequisite of this post.

Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10

## Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

In previous post, we discussed an expected linear time algorithm. In this post, a worst-case linear time method is discussed. The idea in this new method is similar to quickSelect(), we get worst-case linear time by selecting a pivot that divides array in a balanced way (there are not very few elements on one side and many on another side). After the array is divided in a balanced way, we apply the same steps as used in quickSelect() to decide whether to go left or right of the pivot.

Following is complete algorithm.

kthSmallest(arr[0..n-1], k)
1) Divide arr[] into ⌈n/5⌉ groups where size of each group is 5
except possibly the last group which may have less than 5 elements.

2) Sort the above created ⌈n/5⌉ groups and find median
of all groups. Create an auxiliary array 'median[]' and store medians
of all ⌈n/5⌉ groups in this median array.

// Recursively call this method to find median of median[0..⌈n/5⌉-1]
3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4) Partition arr[] around medOfMed and obtain its position.
pos = partition(arr, n, medOfMed)

5) If pos == k return medOfMed
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

In above algorithm, last 3 steps are same as algorithm in previous post. The first four steps are used to obtain a good point for partitioning the array (to make sure that there are not too many elements either side of pivot).

Following is C++ implementation of above algorithm.

 // C++ implementation of worst case linear time algorithm  // to find k'th smallest element  #include  #include  #include     using namespace std;     int partition(int arr[], int l, int r, int k);     // A simple function to find median of arr[].  This is called  // only for an array of size 5 in this program.  int findMedian(int arr[], int n)  {      sort(arr, arr+n);  // Sort the array      return arr[n/2];   // Return middle element  }     // Returns k'th smallest element in arr[l..r] in worst case  // linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT  int kthSmallest(int arr[], int l, int r, int k)  {      // If k is smaller than number of elements in array      if (k > 0 && k <= r - l + 1)      {          int n = r-l+1; // Number of elements in arr[l..r]             // Divide arr[] in groups of size 5, calculate median          // of every group and store it in median[] array.          int i, median[(n+4)/5]; // There will be floor((n+4)/5) groups;          for (i=0; i k-1)  // If position is more, recur for left              return kthSmallest(arr, l, pos-1, k);             // Else recur for right subarray          return kthSmallest(arr, pos+1, r, k-pos+l-1);      }         // If k is more than number of elements in array      return INT_MAX;  }     void swap(int *a, int *b)  {      int temp = *a;      *a = *b;      *b = temp;  }     // It searches for x in arr[l..r], and partitions the array   // around x.  int partition(int arr[], int l, int r, int x)  {      // Search for x in arr[l..r] and move it to end      int i;      for (i=l; i

Copy CodeRun on IDE

Output:

K'th smallest element is 5

Time Complexity:
The worst case time complexity of the above algorithm is O(n). Let us analyze all steps.

The steps 1) and 2) take O(n) time as finding median of an array of size 5 takes O(1) time and there are n/5 arrays of size 5.
The step 3) takes T(n/5) time. The step 4 is standard partition and takes O(n) time.
The interesting steps are 6) and 7). At most, one of them is executed. These are recursive steps. What is the worst case size of these recursive calls. The answer is maximum number of elements greater than medOfMed (obtained in step 3) or maximum number of elements smaller than medOfMed.
How many elements are greater than medOfMed and how many are smaller?
At least half of the medians found in step 2 are greater than or equal to medOfMed. Thus, at least half of the n/5 groups contribute 3 elements that are greater than medOfMed, except for the one group that has fewer than 5 elements. Therefore, the number of elements greater than medOfMed is at least.

Similarly, the number of elements that are less than medOfMed is at least 3n/10 – 6. In the worst case, the function recurs for at most n – (3n/10 – 6) which is 7n/10 + 6 elements.

Note that 7n/10 + 6 < n for n > 20 20 and that any input of 80 or fewer elements requires O(1) time. We can therefore obtain the recurrence

We show that the running time is linear by substitution. Assume that T(n) cn for some constant c and all n > 80. Substituting this inductive hypothesis into the right-hand side of the recurrence yields

T(n)  <= cn/5 + c(7n/10 + 6) + O(n)
<= cn/5 + c + 7cn/10 + 6c + O(n)
<= 9cn/10 + 7c + O(n)
<= cn, 

since we can pick c large enough so that c(n/10 – 7) is larger than the function described by the O(n) term for all n > 80. The worst-case running time of is therefore linear (Source: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10.htm ).

Note that the above algorithm is linear in worst case, but the constants are very high for this algorithm. Therefore, this algorithm doesn’t work well in practical situations, randomized quickSelect works much better and preferred.

=============================================================================

# k largest(or smallest) elements in an array | added Min Heap method

Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.

For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.

## Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

Method 1 (Use Bubble k times)

Thanks to Shailendra for suggesting this approach.
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 2 (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)

Thanks to nesamani1822 for suggesting this method.

Method 3(Use Sorting)
1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).
Following is the implementation of above.

• C++
• Java
• Python

## C++

 // C++ code for k largest elements in an array  #include  using namespace std;     void kLargest(int arr[], int n, int k)  {      // Sort the given array arr in reverse       // order.      sort(arr, arr+n, greater<int>());         // Print the first kth largest elements      for (int i = 0; i < k; i++)          cout << arr[i] << " ";  }     // driver program  int main()  {      int arr[] = {1, 23, 12, 9, 30, 2, 50};      int n = sizeof(arr)/sizeof(arr[0]);      int k = 3;      kLargest(arr, n, k);  }     // This article is contributed by Chhavi 

Copy CodeRun on IDE

## Python

Output:
50 30 23
`

Time complexity: O(nlogn)

Method 4 (Use Max Heap)
1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

Method 5(Use Oder Statistics)
1) Use order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n)
2) Use QuickSort Partition algorithm to partition around the kth largest number O(n).
3) Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)

Thanks to Shilpi for suggesting the first two approaches.

Method 6 (Use Min Heap)
This method is mainly an optimization of method 1. 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.

Please write comments if you find any of the above explanations/algorithms incorrect, or find better ways to solve the same problem.