Contains Duplicate with less than O(n) time

  • -7
    public class Solution {
        public boolean containsDuplicate(int[] nums) {
         boolean flag=true;
         Set<Integer> numList=new HashSet<Integer>();
         for(int i=0;i<nums.length&&flag;i++){
            flag = numList.add(nums[i]);
         return !flag;

    The add function returns a boolean as to whether there are duplicates or not.If duplicate is present, then false is returned from add.As a result we needn't have to traverse the entire array to find whether duplicates exist.
    Do let me know whether there can be any more improvements done on my code.

  • 5

    Even though for the average case it is faster than traversing the entire array, Its still an O(n) code since the worst case performance is what is used.

Log in to reply

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