# Concise inplace quick select Java code

• For a detailed explanation of Quick Select, see here

``````public class Solution {
/**
* Randomized quick select.
* Using random chosen pivot to partition the arrray.
* Average case and best case O(n), worst case O(n^2)
* In place swap, O(1) space.
*/
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return Integer.MIN_VALUE;
}

int len = nums.length;

return quickSelect(nums, k, 0, len - 1);
}

private int quickSelect(int[] nums, int k, int start, int end) {

//Choose a pivot randomly
Random rand = new Random();
int index = rand.nextInt(end - start + 1) + start;
int pivot = nums[index];
swap(nums, index, end);

int left = start, right = end;

while(left < right) {
if (nums[left++] > pivot) {
swap(nums, --left, --right);
}
}
//left is pointing to the first number that is greater than pivot

//m is the number of numbers that is greater than pivot
int m = end - left;

if (m == k - 1) { //in order to find the kth largest number, there must be k - 1 number greater than it
return pivot;
}
else if (k < m + 1) { //target is in the right subarray
return quickSelect(nums, k, left, end);
}
else { //target is in the left subarray, but need to update k since we have discarded m + 1 numbers greater than it which is in the right subarray
return quickSelect(nums, k - m - 1, start, left - 1);
}
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.