Contains Duplicate

• LeetCode: Contains Duplicate

• Problem:

Given an array of integers, find if the array contains any duplicates. 

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

• Analysis:

I. Sort

    Sort for the array and find the nums[i] == nums[i + 1]

II. HashMap

    Count the number of each num and return true if count is more than 2.

• Solution Sort:

• Code - Java:

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

• Code - C++:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

• Code - Python:

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        numLen = len(nums)
        nums = sorted(nums)
        for i in range(numLen - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False

• Solution HashMap:

• Code - Java:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int len = nums.length;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++) {
            int count = counts.getOrDefault(nums[i], 0) + 1;
            if (count > 1) {
                return true;
            }
            counts.put(nums[i], count);
        }
        return false;
    }
}

• Code - C++:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int len = nums.size();
        map<int, int> counts;
        for (int i = 0; i < len; i++) {
            if (counts.find(nums[i]) != counts.end()) {
                return true;
            }
            counts.insert(pair<int, int>(nums[i], 1));
        }
        return false;
    }
};

• Code - Python:

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        numLen = len(nums)
        counts = {}
        for num in nums:
            if num in counts:
                return True
            counts[num] = 1
        return False

• Solution Sort:

• Time Complexity: O(NLOGN), N is the length of the input array

• Space Complexity: O(1)

========================================================================================================

• Solution HashMap:

• Time Complexity: O(N), N is the length of the input array

• Space Complexity: O(N), N is the length of the input array