3ms Java solution beats 98% of the answers


  • 6
    U
    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            int min=Integer.MAX_VALUE;
            int max=Integer.MIN_VALUE;
            for(int b: nums){
                if(b<min){
                    min=b;
                }
                if(b>max){
                    max=b;
                }
            }
            boolean a[] = new boolean[max-min+1];
            for(int b: nums){
                if(a[b-min]){
                    return true;
                }else{
                    a[b-min]=true;
                }
            }
            return false;
        }
    }

  • 4
    R

    Interesting! However, the space complexity is huge depending on the min/max values. Could improve space complexity by using BitSet.


  • 0
    Q

    can someone please explain why this is faster than a Set approach? thanks!


  • 0
    V

    I assume by "a Set approach" you mean while looping thru the nums array, if the Set does not contains the current element --> add it, else return true. The complexity for this approach is O(N^2). The solution above has the complexity of O(2N) --> O(N) but its space complexity could be as big as the gap between max and min values in the array.


  • 0
    D

    A great approach!


  • 1
    B

    said in 3ms Java solution beats 98% of the answers:

       int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        for(int b: nums){
            if(b<min){
                min=b;
            }
            if(b>max){
                max=b;
            }
        }
        boolean a[] = new boolean[max-min+1];
        for(int b: nums){
            if(a[b-min]){
                return true;
            }else{
                a[b-min]=true;
            }
        }
        return false;
    

    This is cheating leetcode without enough test case.
    e.g.
    [-2147483648, 2147483647]


  • 0
    S

    @Bruce True. 1. Space complexity. 2. Overflow.


Log in to reply
 

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