The prompt

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.

Examples

Example	Input	Output
1	[1,2,3,1]	true
2	[1,2,3,4]	false
3	[1,1,1,3,3,4,3,2,4,2]	true

Constraints

1 <= nums.length <= 105

-109 <= nums[i] <= 109

Solution #1: (Worst)

naive.py

def naive_solution(nums: List[int]) -> bool:
    # Loops trough the list
    for i in nums:
        # Loops through the list but starts at the \`i\` element of nums
        for j in nums[i:]:
            if i == j:
                return True
    return False

How does it work?

Let's assume we have nums = [1,2,3,1]

The first loop selects the first element in this case `1`.
Next, the second loops starts after the first element selected in the first loop. In this case `2`
Then the conditional if statement compares the to numbers for equality.
If the numbers are equal True is returned, otherwise we repeat step 1 at the next element.

Time Complexity	Space Complexity
O(n²)	O(1)

O(1)*No new variable was assiged. Thus it's excellent memory wise. It's not consuming extra memory. O(n²)*Quadratic Time. Nested loops. Let's say you have an array with 10 elements, a nested loop would perform a total of 100 Iterations. The more items you have the worst the performance.

Solution #2: (Not So Bad)

sorted_solution.py

def sorted_solution(nums: List[int]) -> bool:
    sorted_array = sorted(nums)
    for n in range(len(sorted_array)):
        if n < len(sorted_array)-1 and sorted_array[n] == sorted_array[n+1]:
            return True
    return False`}

How does it work?

The first thing we do is sort the list. Some programming languages, have array methods to perform sorting.
After we sort the array/list, we need to check all elements using a loop and verifying the adjacent element.
After the array is sorted it would become: [1,1,2,3]
Next, the for loop would go through the first element.
Additionally, we need a conditional if statement to compare the current element and the adjacent element to the left.
If the elements are the same, then we return True, otherwise we continue the loop.
If no elements are found to be duplicate we return False after the loop is done.

Note: O(n log(n)) is slightly better than O²

Time Complexity	Space Complexity
O(n log(n))	O(n)

O(1)*New variable was assiged. Thus it affects memory used. O(n²)*Logarithmic Time.

Solution #3: (Good)

good_solution.py

def set_solution(nums:List[int]) -> bool:
    hash_set = set()
    for n in nums:
        if n in hash_set:
            return True
        # Else can be ignored but it's added for explicitness (easier to read imo)
        else:
            hash_set.add(n)
    return False

How does it work?

First, we need to create a new set variable. This variable will hold a set.
Then, we loop through the array.
If the item is not in set, we added.
Otherwise, the item is already in the set, so we can return True because a duplicate was found.
If none of the items is duplicate we return false after the loop, since no duplicate were found.

Time Complexity	Space Complexity
O(n)	O(n)

O(n)*New variable was assiged to create the set. Thus it affects memory used. O(n)*Linear Time. What this means is that it increases in proportion to the number of inputs.

Solution #4: (Clever Pythonista)

clever_pythonista.py

def clever_solution(nums: List[int]) -> bool:
    return len(set(nums)) != len(nums)`}

How does it work?

In the case of Python we can verify for duplicates by leveraging set()

set() builds a collection of unordered unique elements.

Taking that in consideration we can simply compare the length of the original array, versus the length of the array that we converted to a set.

Because set() drops duplicates, if the arrays are not the same length that means, there were duplicates.

Time Complexity	Space Complexity
O(n)	O(n)

Multiple ways to solve it.

Please note that there are multiple different ways to solve this problem. I just provided a few different solutions.

For more problems like this one be sure to checkout NeetCode.