Java O(n) Accepted Solution - beats 99.15%


  • 0
    J

    Some of the useful hints

    • The numbers are always positive.
    • Range of numbers in limited 1 ≤ a[i] ≤ n so max number can be length of the array.
      This is typical count sort problem, where we create buckets for each number and each bucket holds the count.

    Java Solution

    	public  static List<Integer> findDuplicates(int[] nums) {
    		int[] bucket = new int[nums.length + 1];
    		for (int i = 0; i < nums.length; i++) {
    			bucket[nums[i]]++; // increment values in bucket
    		}
    		
    		List<Integer> p = new ArrayList<Integer>();
                    // filter number with occurrence >=2 (duplicates) in bucket 
    		for (int i = 0; i < bucket.length; i++) {
    			if(bucket[i] >= 2) {
    				p.add(i);
    			}
    		} 
    		
    		return p;
        }
    
    
    
    

Log in to reply
 

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