NeetCode 150: Contains Duplicate

Table of contents

The 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.

The Approach

The goal is to ensure that every element in nums appears only once (i.e. each element is unique).

A Set data structure fulfills such a criteria as it has no duplicate elements. By using the boolean add(E e) method, we can check if an already inserted element is inserted again, which returns false.

My Solution

class Solution {
    public boolean containsDuplicate(int[] nums) {
        // Use a HashSet as it requires the least memory.
        Set<Integer> numsSet = new HashSet<Integer>();

        // Keep adding it to numsSet, & if it returns true, a duplicate
        // is present. Sets do not allow any duplicate elements.
        for (int i = 0; i < nums.length; i++) {
            if (!(numsSet.add(nums[i]))) {
                return true;
            }
        }
        return false;
    }
}

Firstly, we initialize a HashSet. We then loop over all the elements in nums, checking the return value of numsSet.add(nums[i]).

If numsSet.add(nums[i]) returns false, a duplicate element is present & true is returned. Else, it means that no duplicate elements were present after looping through nums & false is returned.

// Comparator that is used for qsort().
int intComparator(int* a, int* b) {
    return (*a - *b);
}

// Sorts the array & then checks consecutively that each 
// number is different than the previous.
bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), intComparator);
    
    int prev = nums[0];
    for (int i = 1; i < numsSize; i++) {
        int current = nums[i];

        if (current == prev) {
            return true;
        }
        prev = current;
    }
    return false;
}