AC Java solution using counting sort, probably a loophole in test cases ?


  • 0
    R

    I was able to use counting sort to solve this is O(range of numbers in input). Currently none of the tests check for elements > 10 K value. Using this observation my solution got accepted. I think either the range should be clarified in the problem or test cases should be created with much larger rang of values and time limit check.

    public int findKthLargest(int[] nums, int k) {
    
        if (nums == null || nums.length == 0 || nums.length < k) return -1;
    
        int range = 10000;
        Integer[] pos = new Integer[range];
        Integer[] neg = new Integer[range];
    
        for(int i : nums){
            if(i < 0) neg[-i] = neg[-i] == null ? 1 : neg[-i] + 1;
            else  pos[i] = pos[i] == null ? 1 : pos[i] + 1;
        }    
        
        int count = 0;
          
        Integer[] temp = pos;
        for(int i = range - 1; i >= 0; i--) {
            if(temp[i] != null) count += temp[i];
            if(count >= k) return i;
        }
        
        temp = neg;
        for(int i = range - 1; i >= 0; i--) {
            if(temp[i] != null) count += temp[i];
            if(count >= k) return -i;
        }
      
        
        return -1;
    }

Log in to reply
 

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