**Objective: **Find Kth Smallest or Largest element in an Array

**Example:**

int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Output: The 4th smallest element is : 8

**Approach:**

**Naive Approach: Use Sorting**

Sort the array and return kth element. Time Complexity – O(nlogn).

**Better Approach: Use Quick Sort Technique
**

*Here we are finding the kth smallest element in array. Same approach you can apply to find the kth largest element.*

- In this technique we select a pivot element and after a one round of operation the pivot element takes its correct place in the array.
- Once that is done we check if the pivot element is the kth element in array, if yes then return it.
- But if pivot element is less than the kth element, that clearly means that the kth element is on the right side of the pivot. So make a recursive call from pivot+1 to end.
- Similarly if pivot element is greater than the kth element, that clearly means that the kth element is on the left side of the pivot. So make a recursive call from start to pivot-1.

**Average Time Complexity : O(n)**

**NOTE: **Instead of printing the kth element, you can print all elements from index 0 to k and this will the solution of the problem** “ Print First K smallest or largest elements in an array”.**

**Complete Code:**

public class KthSmallestElement { | |

public int findkthSmallestElement(int[] arrA, int k) { | |

k = k – 1; // since array index starts with 0 | |

return kSmall(arrA, 0, arrA.length – 1, k); | |

} | |

public int kSmall(int[] arrA, int start, int end, int k) { | |

int left = start; | |

int right = end; | |

int pivot = start; | |

while (left <= right) { | |

while (left <= right && arrA[left] <= arrA[pivot]) | |

left++; | |

while (left <= right && arrA[right] >= arrA[pivot]) | |

right—; | |

if (left < right) { | |

swap(arrA, left, right); | |

left++; | |

right—; | |

} | |

} | |

swap(arrA, pivot, right); | |

if (pivot == k) | |

return arrA[pivot];// if pivot is kth element , return | |

else if (pivot < k) | |

// if pivot is less than k, then kth element will be on the right | |

return kSmall(arrA, pivot + 1, end, k); | |

else | |

// if pivot is greater than k, then kth element will be on the right | |

return kSmall(arrA, start, pivot – 1, k); | |

} | |

public void swap(int[] arrA, int a, int b) { | |

int x = arrA[a]; | |

arrA[a] = arrA[b]; | |

arrA[b] = x; | |

} | |

public static void main(String args[]) { | |

int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; | |

KthSmallestElement k = new KthSmallestElement(); | |

int a = 4; | |

int x = k.findkthSmallestElement(arrA, a); | |

System.out.print("The " + a + "th smallest element is : " + x); | |

} | |

} |

**Output:**

The 4th smallest element is : 8

after line swap(arrA, pivot, right), element at index ‘right’ will be at correct position not element at pivot index.

Code need little modification as mentioned below.

if (right == k)

return arrA[right];

else if (right < k)

return kSmall(arrA, right + 1, end, k);

else

return kSmall(arrA, start, right – 1, k);