Contains Duplicate


  • 1

    Click here to see the full article post


  • 0
    C
    class Solution(object):
        def containsDuplicate(self, nums):
            if len(nums) > len(set(nums)):
                return True
            return False
    

  • 1
    P

    Approach #3 (Hash Table) - this is not getting accepted. Please check. Its giving TLE.


  • -1
    Y

    I tried using HashMap and HashSet in Java but its giving TLE for both for the test case ranging from 0, 1, 2.......29999. As the numbers are not given to be sorted, binary search cant be used here. For unsorted array, in worst case O(n) would be required.

    Infact, on pasting this dataset into Eclipse, eclipse is giving error "The code of method main(String[]) is exceeding the 65535 bytes limit"


  • 0
    H

    Sometimes it gives LTE for hashset.......


  • 0

    HashSet executes the time limit error. Agree with @hu26


  • -1
    A

  • 0
    I

    if (set.contains(x)) return true;//Accepted
    if (set.contains(x)) {return true;}//TLE


  • 0
    H

    You may need one line at the begining.
    if(nums.length == 30000) return false;


  • 0
    M

    I tried using an ArrayList and a HashSet as a data structure for holding the values of the array and testing for contains(). Got time limit exceeded for both. I had to remove the else statement after the if (hashset.contains()). When compiled that code shouldn't be any different right?


  • 0
    B

    C(n, 2) = n(n-1)/2


  • 0
    G

    I know it is the easiest question of all , but this is the first time I cracked the right soln to sort under 2 mins and get accepted in 1st try . can you give me tips to solve maximum question with same approach.


  • 0
    P
    \\Example for Contains Duplicate in C
    \\It was able to be accepted but sometime it was fail by TLE
    bool containsDuplicate(int* nums, int numsSize) {
        int i, j;
        for( i=0; i<numsSize; i++)
            for( j=i+1; j<numsSize; j++)
                if(nums[i]==nums[j])
                    return 1;
        return 0;
    }

  • 0
    P

    Is HashSet faster than HashMap? My sol with HashMap failed (TLE), but HashSet passed with flying colors. Could anyone care to explain?

    static public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num: nums){
            if (map.containsKey(num)){
                return true;
            }
            map.put(num, 0);
        }
        return false;
    } // TLE
    
    static public boolean containsDuplicateOptimum(int[] nums) {
        Set<Integer> map = new HashSet<Integer>();
    
        for (int num: nums){
            if (map.contains(num)){
                return true;
            }
            map.add(num);
        }
        return false;
    } // passes

  • 0
    A

    @posts.dir In java HashSet has a HashMap with only keys (same singleton Object as value will be added for any key) under the hood. Here is HashSet.add() method from JDK;

     public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    

    You problem is related to "autoboxing" - java inline conversion from primitive int to Integer.

    In your code this happens 3 times:

    1. first in containsKey();
    2. in put - num to Integer;
    3. int put - 0 to Integer;

    On large sets this performance degradation is significant.

    P.S. autoboxing for 0 is not critical for JVM - because by default settings JVM caches most common (byte type range) of them.


  • 0
    A

    @posts.dir
    This optimization (with only one autoboxing) on my first submission gave me 16 ms vs 23 ms I had before:

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

Log in to reply
 

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