My O(n) time & O(sqrt n) space solution


  • 2
    M

    I understand that the problem explicitly asks for a constant space solution, however I found this algorithm that allows you to find duplicates in linear time using just sqrt(n) memory.

    One of the advantages of this algorithm is that is also decides if there are no duplicates in the array (in this case I returned -1).

    Explanation

    Split the numbers from 1 to n in sqrt(n) ranges so that range i corresponds to [sqrt(n) * i .. sqrt(n) * (i + 1)).

    Do one pass through the stream of numbers and figure out how many numbers fall in each of the ranges.

    At least one of the ranges will contain more than sqrt(n) elements.

    Do another pass and process just those elements in the oversubscribed range.

    Using a hash table to keep frequencies, you’ll find a repeated element.

    This is O(sqrt(n)) memory and 2 sequential passes through the stream.

    public class Solution {
        public int findDuplicate(int[] a) {
                int bucketLen = (int)Math.sqrt(a.length);
    	    int[] freq = new int[bucketLen + 1];
    	    for(Integer i : a) {
    	        freq[Math.min(i/bucketLen - (i%bucketLen == 0?1:0), bucketLen)]++;
    	    }
    	    
    	    int i = 0;
    	    while(i < bucketLen && freq[i] <= bucketLen) i++;
    	    
    	    Set<Integer> found = new HashSet<Integer>();
    	    for(Integer v : a) {
    	        if(i*bucketLen < v && (i==freq.length-1 || v <= (i+1)*bucketLen)) {
    	            if(found.contains(v)) return v;
    	            found.add(v);
    	        }
    	    }
    
    	    return -1;
        }
    }
    

    Hope you find this helpful :)


Log in to reply
 

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