# Median of Median - Worst case linear time O(n) - 8ms

• ``````public class Solution {
public int findMedian(int [] arr,int l,int r){
Arrays.sort(arr,l,r);
return arr[l+(r-l)/2];
}

public void swap(int [] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] =temp;
}
public int partition(int [] arr,int l,int r,int key){
int i = l;
for(i=l;i<r;i++){
if(arr[i] == key)
break;
}
swap(arr,i,r);
i=l;
for(int j=l;j<r;j++){
if(arr[j]>key){

swap(arr,i,j);
i++;
}
}
swap(arr,i,r);
return i;
}
public  int kthlargest(int [] arr,int l,int r,int k){
if(k>0 && k<=(r-l+1)){
int n = r-l+1;
int [] median = new int[(n+4)/5];
int i=0;
for(i=0;i<n/5;i++){
median[i] = findMedian(arr,l+i*5,l+i*5+5);
}

if(n%5!=0){
median[i] = findMedian(arr,l+i*5,l+i*5+n%5);
i++;
}
int medofmed = (i==1)?median[0]:kthlargest(median,0,i-1,i/2);
int pos = partition(arr,l,r,medofmed);
if(pos-l == k-1)
return arr[pos];
if(k-1 < pos-l){
return kthlargest(arr,l,pos-1,k);
}
else
return kthlargest(arr,pos+1,r,k-pos+l-1);
}
return Integer.MAX_VALUE;
}

public int findKthLargest(int[] nums, int k) {

if(nums.length==1 && k==1)
return nums[0];

return kthlargest(nums,0,nums.length-1,k);

}
}
``````

Similar to quick select but selects pivot in a balanced way.

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