Working solution, but had to hack scenario to partition array size of 2. Where am I going wrong?


  • 0
    T

    public class KthLargest {

    public int findKthLargest(int[] nums, int k) {
    	if (nums == null || nums.length == 0 || k < 1)
    		return (Integer)null;
    	
    	//this is equivalent to kth smallest
    	 return findKthSmallest(nums, 0, nums.length-1, nums.length + 1 - k);
    	
    
    }
    
    private int findKthSmallest(int[] nums, int start, int end, int k) {
    	if(start>end)
    		return 0;
    	
    	int pivotPos = partition(nums, start, end);
    	if (pivotPos == k - 1)
    		return nums[pivotPos];
    	else if (pivotPos > k - 1)
    		return findKthSmallest(nums, start, pivotPos , k);
    	else
    		return findKthSmallest(nums, pivotPos + 1, end, k);
    }
    
    private int partition(int[] nums, int start, int end) {
    	
    	if (start > end)
    		return -1;
    	
    	//hack for partitioning only 2 elements
    	if (end - start == 1){
    		if (nums[end] >= nums[start])
    			return start;
    		else {
    			int temp = nums[end];
    			nums[end] = nums[start];
    			nums[start] = temp;
    			return end;
    		}
    	}
    	
    	int pivot = start;
    	int i = start+1;
    	int j = end;
    	
    	while (i <j){
    		while (nums[i] <= nums[pivot] && i < end)
    			i++;
    		while (nums[j] >= nums[pivot] && j > start)
    			j--;
    		
    		if (j > i){
    			int temp = nums[i];
    			nums[i] = nums[j];
    			nums[j] = temp;
    		}
    	}
    	
    	int temp = nums[j];
    	nums[j] = nums[pivot];
    	nums[pivot] = temp;
    	
    	return j;
    }
    

    }


Log in to reply
 

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