Contains Duplicate

Problem Statement

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1

Input: nums = [1, 2, 3, 3]
Output: True

Example 2

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

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every element against every other element in the array. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Is there a way to check if an element is a duplicate without comparing it to every other element? Maybe there’s a data structure that is useful here.

Hint 3

We can use a hash data structure like a hash set or hash map to store elements we’ve already seen. This will allow us to check if an element is a duplicate in constant time.

Solution

Brute Force

def has_duplicate(nums: List[int]) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Time complexity: O(n^2) Space complexity: O(1)