8. Contains Duplicate

EasyArray Hash Table Sorting

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

Example 1

Input: nums = [4,9,2,4]
Output: true

Explanation: 4 appears at index 0 and again at index 3.

Example 2

Input: nums = [8,3,5,1]
Output: false

Explanation: All four values are different.

Example 3

Input: nums = [6,6,2,2,6,1]
Output: true

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

💡 Hint 1

Comparing every pair works but is O(n²). What would let you answer "have I seen this before?" instantly?

💡 Hint 2

Insert values into a hash set as you scan; the first value already in the set is a duplicate.

💡 Hint 3

Alternatively, sort the array: equal values end up next to each other.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Scan the array once while keeping a hash set of the values seen so far. If the current value is already in the set, a duplicate exists and you can stop early; if the scan finishes, every value was distinct. Sorting and comparing neighbours also works in O(n log n) time with no extra set.

Time O(n)Space O(n)

function containsDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) return true;
        }
        return false;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function containsDuplicate(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit