Beats 95% java submission 2MS solution with explanation


  • 0
    K

    The trick is in modified quick sort. Condition is not to sort it further.

    public class Solution {
     private int[] array = null;
     private int K = 0;
     public int findKthLargest(int[] nums, int k) {
            k = nums.length - k;
            int lo = 0;
            int hi = nums.length - 1;
            array = nums;
            K = k;
            quickSort(lo, hi);
            return nums[k];
        }
    
        
        private void quickSort(int lowerIndex, int higherIndex) {
             
            int i = lowerIndex;
            int j = higherIndex;
            // calculate pivot number, I am taking pivot as middle index number
            int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
            // Divide into two arrays
            while (i <= j) {
                /**
                 * In each iteration, we will identify a number from left side which
                 * is greater then the pivot value, and also we will identify a number
                 * from right side which is less then the pivot value. Once the search
                 * is done, then we exchange both numbers.
                 */
                while (array[i] < pivot) {
                    i++;
                }
                while (array[j] > pivot) {
                    j--;
                }
                if (i <= j) {
                    exchangeNumbers(i, j);
                    //move index to next position on both sides
                    i++;
                    j--;
                }
            }
            // call quickSort() method recursively
            if (lowerIndex < j) {
                //if upper bound is in KPosition sort else no sorting needed
                if(K <= j) {
                   quickSort(lowerIndex, j);
                }
            }
            if (i < higherIndex) {
               //if lower bound is in KPosition sort else no sorting needed
               if(K >= i) {
                quickSort(i, higherIndex);
               }
           } 
        }
     
        private void exchangeNumbers(int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    } 
    

Log in to reply
 

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