package com.interview.array;

/**
 * Kth largest element in an array.
 * Use quickselect of quicksort to find the solution in hopefully O(nlogn) time.
 * Test cases
 * Sorted array
 * Reverse sorted array
 */
public class KthElementInArray {
    
    public int kthElement(int arr[],int k){
        int low = 0;
        int high = arr.length-1;
        int pos =0;
        while(true){
            pos = quickSelect(arr,low,high);
            if(pos == (k+low)){
                return arr[pos];
            }
            if(pos > k){
                high = pos-1;
            }else{
                low = pos+1;
                k = k - low;
            }
        }
    }
    
    private int quickSelect(int arr[],int low,int high){
        int pivot = low;
        low++;
        while(low <= high){
            if(arr[pivot] > arr[low]){
                low++;
                continue;
            }
            if(arr[pivot] <= arr[high]){
                high--;
                continue;
            }
            swap(arr,low,high);
        }
        if(arr[high] < arr[pivot]){
            swap(arr,pivot,high);
        }
        return high;
    }
    
    private void swap(int arr[],int low,int high){
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
    
    public static void main(String args[]){
        int arr[] = {3,6,9,1,2};
        KthElementInArray kthElement = new KthElementInArray();
        System.out.print(kthElement.kthElement(arr, 0));
    }
    
}

@@ -23,16 +23,42 @@
 array;%0A%0A
+import java.util.Arrays;%0A%0A
 /**%0A * K
@@ -551,16 +551,22 @@
 (pos %3E k
+ + low
 )%7B%0A     
@@ -629,19 +629,31 @@
     
-low = pos+1
+k = k - (pos - low + 1)
 ;%0A  
@@ -670,19 +670,19 @@
     
-k = k - low
+low = pos+1
 ;%0A  
@@ -1416,17 +1416,27 @@
  = %7B
-3,6,9,1,2
+6, 2, 1, 6, 8, 9, 6
 %7D;%0A 
@@ -1550,17 +1550,76 @@
 nt(arr, 
-0
+arr.length/2));%0A        System.out.print(Arrays.toString(arr
 ));%0A    

update kth element logic