Leetcode problem#217: Contains Duplicate

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example:
Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

---

Sorting

We can solve this problem by sorting the array. Time complexity for sorting is O(nlogn). After sorting, we loop through the array and match the consecutive numbers to find the duplicate values.

Implementation (Java)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int pointer = 0;
        Arrays.sort(nums);

        while(pointer < nums.length-1){
            if(nums[pointer] == nums[pointer+1]){
                return true;
            }
            pointer++;
        }
       return false;
    }
}

However, this approach has a time complexity of O(nlogn). So we can follow a better way by using HashSet to optimize the time complexity.

HashSet

Java HashSet class implements the Set interface. It stores the elements in the hashtable and only holds the distinct values. For checking duplicate numbers, we can use contains() method.

Implementation (Java)

class Solution {
    public boolean containsDuplicate(int[] nums) {

        int pointer = 0;

        Set<Integer>checkNum = new HashSet<>();

        while(pointer < nums.length){
            if(checkNum.contains(nums[pointer])){
                return true;
            }
            checkNum.add(nums[pointer]);
            pointer++;
        }
        return false;
    }
}

Here we get the time complexity of O(n).