Possible solutions.


  • 185
    J

    This problem seems trivial, so lets try different approaches to solve it:

    Starting from worst time complexity to the best one:


    Time complexity: O(N^2), memory: O(1)

    The naive approach would be to run a iteration for each element and see whether a duplicate value can be found: this results in O(N^2) time complexity.


    public boolean containsDuplicate(int[] nums) {
    
            for(int i = 0; i < nums.length; i++) {
                for(int j = i + 1; j < nums.length; j++) {
                    if(nums[i] == nums[j]) {
                        return true;
                    }
                }
            }
            return false;
        }
    

    Time complexity: O(N lg N), memory: O(1) - not counting the memory used by sort

    Since it is trivial task to find duplicates in sorted array, we can sort it as the first step of the algorithm and then search for consecutive duplicates.


        public boolean containsDuplicate(int[] nums) {
    
            Arrays.sort(nums);
            for(int ind = 1; ind < nums.length; ind++) {
                if(nums[ind] == nums[ind - 1]) {
                    return true;
                }
            }
            return false;
        }
    

    Time complexity: O(N), memory: O(N)

    Finally we can used a well known data structure hash table that will help us to identify whether an element has been previously encountered in the array.


    public boolean containsDuplicate(int[] nums) {
    
        final Set<Integer> distinct = new HashSet<Integer>();
        for(int num : nums) {
            if(distinct.contains(num)) {
                return true;
            }
            distinct.add(num);
        }
        return false;
    }
    

    This is trivial but quite nice example of space-time tradeoff.


  • 17
    J

    As a bonus here is a functional equivalent in Java:


    public boolean containsDuplicate(int[] nums) {
    
            return nums.length != Arrays.stream(nums)
                    .distinct()
                    .count();
        }
    

    Sadly this does not pass the judge - with time limit exceeded as a result ...


  • 0

    nice sharing for different approaches to solve it.


  • 0
    M

    Reminds me of Apache Spark - functional programming!


  • 0
    P

    What about using a bitmap set if the array is huge?


  • 0
    J

    Yes I like this idea. Maybe you could provide an example source code?

    Although I've begun thinking, isn't BitSet a bit vulnerable to the value ranges?

    For instance lets say that your array does not store consecutive values i.e. array of N integers of values from <0, N - 1> and instead stores N integers of range <0, M>

    So what is going to happen if you use as a input an array [Integer.MAX_VALUE]?

    or create

    BitSet bitSet = new BitSet();
    bitSet.set(Integer.MAX_VALUE);

    I think that in some corner cases BitSet would not help you to save memory.


  • 1
    A

    one more: Time complexity: O(N lg N), memory: O(N lg N); create a BST(AVL or R-B T), which is basically the same as sort.


  • 0
    I

    Using BitSet must be converting negative numbers in binary to decimal.


  • 0
    J

    OMG, the naive approach is submitted error "Time Limit Exceeded"


  • 0
    S

    Is there anybetter but clever solution to this problem?
    Using hash table is also very trivial, as it seems to experienced progammers.


  • 4
    W

    As a bonus a Java 8 version using streams that is O(n)

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        return Arrays.stream(nums).anyMatch(num -> !seen.add(num));
    }
    

    It's just a syntactic sugar over standard iteration but it looks nice.


  • 0
    W

    add function on set, return true or false if element is added.

    So you can write :

    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            final Set<Integer> distinct = new HashSet<Integer>();
            for(int num : nums) {
                if(!distinct.add(num)) {
                    return true;
                }
            }
            return false;
        }
    }

  • 2
    L

    Would you explain why you use final here?


  • 2
    J

    I don't know why, but I noticed that without final, this solution is TLE.


  • 0
    G

    I don't think "distinct.contains(num)" is O(1). I guess it should be O(log n). Therefore, the last method is O(nlogn) not O(n).


  • 2
    J

    @gjybear If you use TreeSet instead, it would be O(log n). Here it uses HashSet. Hope you know the difference between them.


  • 0
    C

    @jmnarloch the first and the third are all "Time Limit Exceeded".


  • 0
    E

    @jmnarloch
    I use the BitSet, it is O(n), but with large constant. Because, I need to convert the negative value to non-negative, and find the large value to initialize the bitset capacity. Maybe this approach will save some space as the array is large.

    import java.util.*;
    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            int max = 0;
            int min = 0;
            for (int i = 0; i < nums.length; i++) {
                max = max > nums[i]? max: nums[i];
                min = min < nums[i]? min: nums[i];
            }
           if (min < 0 ) {
                for (int i =0; i< nums.length; i++) {
                    nums[i] -= min;
                }
                max -= min;
            }
            if (max < nums.length-1) return true;
            
            BitSet bitset = new BitSet(max);
            for (int i = 0; i < nums.length; i++) {
                if (bitset.get(nums[i])) return true;
                else bitset.set(nums[i]);
            }
            return false;
            
        }
    }
    

  • 2
    S

    In the third method, why use 'final' on the Set<Integer>?


  • 2

    Is "final" keyword able to reduce the workload of compiler such that the running time could be diminished ? Anyone knows the answer ?


Log in to reply
 

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