java 2ms beats 96% based on counting sort O(n)

  • 0
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
    		int max=nums[0];
    		int min=nums[0];
    		for(int i=1;i<nums.length;i++){//n
    			if(nums[i]>max) max=nums[i];
    			else if(nums[i]<min) min=nums[i];
    		int[] counts=new int[max-min+1];
    		for(int i=0;i<nums.length;i++){//n
    		int large=0;
    		for(int i=counts.length-1;i>=0;i--){
    			if(k<=0) {
    				large = i+min;
    		return large;

  • 1

    This is a nice solution, actually this is not a strict o(n) solution, if you mean n is num of elements in the array. The counts[] array size will go up to Integer.MAX_VALUE. But this will be efficient when n is very big.

Log in to reply

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