Solution 1

This brute-force solution checks for duplicates by comparing every element in the array against every other element using nested loops.

Pseudocode

1. Start an outer loop that iterates through each element of the array with an index i.
2. Start an inner loop that iterates from the element right after i (index i + 1) to the end of the array.
3. In the inner loop, compare the element at index i with the element at the inner loop's current index j.
4. If the two elements are equal, a duplicate has been found, so immediately return True.
5. If the loops finish without finding any matching elements, return False.

Code

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

Complexity Analysis

• Time Complexity: $O(N^2)$, where $N$ is the number of elements in nums. In the worst-case scenario (no duplicates), this approach compares every pair of elements.
• Space Complexity: $O(1)$, as no extra space is used that scales with the input size.

Tricks

• Unique Pair Iteration: The inner loop starting from j = i + 1 is a standard technique to efficiently iterate through all unique pairs of elements in a list without redundant comparisons.
• Early Exit: The function returns True as soon as the first duplicate is found. This is a crucial optimization that prevents unnecessary computations.
• Recognizing Inefficiency: This $O(N^2)$ approach is a classic brute-force solution. The most important "trick" to learn from it is to identify its inefficiency and know that using a Hash Set can solve this problem in $O(N)$ time, which is the preferred solution in an interview context.

Solution 2

This solution finds duplicates by first sorting the array, which groups identical elements together, and then checking for adjacent matches in a single pass.

Pseudocode

1. Sort the input array nums.
2. Iterate through the sorted array from the first element up to the second-to-last element.
3. In each iteration, compare the current element with the next element (nums[i] and nums[i+1]).
4. If any adjacent pair of elements is identical, a duplicate exists, so return True.
5. If the loop finishes without finding any identical adjacent elements, return False.

Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        length = len(nums)
        for i in range(length - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False

Complexity Analysis

• Time Complexity: $O(N\log N)$, where $N$ is the number of elements. The dominant operation is the sorting of the array. The subsequent linear scan takes $O(N)$ time, which is overshadowed by the sort.
• Space Complexity: $O(1)$ or $O(\log N)$. This depends on the specific implementation of the in-place sort algorithm. Python's Timsort can use some auxiliary space, but it's much less than creating a full copy of the array.

Tricks

• Sorting as a Pre-processing Step: The core idea is to use sorting to re-arrange the data into a more useful structure. After sorting, the complex problem of finding any duplicate is simplified to the much easier problem of finding adjacent duplicates.
• Modifying Input: This solution sorts the array in-place, which alters the original input. This is a common trade-off to save space, but it's important to be aware that the caller's original array will be changed.
• Efficiency Comparison: This $O(N\log N)$ approach is significantly more efficient than the $O(N^2)$ brute-force method, but it is generally less time-efficient than an $O(N)$ solution using a Hash Set.

Solution 3

This optimal solution uses a hash set to keep track of numbers encountered, allowing for constant-time duplicate checks in a single pass.

Pseudocode

1. Initialize an empty hash set, seen, to store numbers we have already processed.
2. Iterate through each number n in the input array.
3. For each number, check if it already exists in the seen set.
4. If it exists, we have found a duplicate, so immediately return True.
5. If it does not exist, add the number to the seen set to mark that we have now seen it.
6. If the loop completes without finding any duplicates, return False.

Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for n in nums:
            if n in seen:
                return True
            else:
                seen.add(n)
        return False

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the number of elements in nums. We iterate through the array once, and both hash set insertion and lookup operations take, on average, $O(1)$ time.
• Space Complexity: $O(N)$. In the worst case (an array with no duplicates), the hash set will grow to store all $N$ elements.

Tricks

• Hash Set for Lookups: The core trick is leveraging a hash set for its $O(1)$ average time complexity for lookups (in) and insertions (add). This data structure is perfectly suited for problems involving checking for the existence of an item.
• Time-Space Trade-off: This approach exemplifies a classic time-space trade-off. It sacrifices extra memory (space complexity of $O(N)$) to achieve a faster runtime (time complexity of $O(N)$) compared to other methods.
• Pythonic One-Liner: A very concise, alternative way to solve this in Python is return len(nums) != len(set(nums)). This works by converting the list to a set (which automatically removes duplicates) and then comparing the lengths. While clever, the iterative solution is often more memory-efficient as it allows for an early exit.

Solution 4

This concise, one-line solution leverages the unique property of sets by comparing the length of the original list to the length of a set created from it.

Pseudocode

1. Convert the entire input list nums into a set. This process automatically removes any duplicate elements.
2. Compare the size of the new set with the size of the original list.
3. If the set's size is less than the list's size, it means duplicates were present and removed, so return True. Otherwise, return False.

Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) < len(nums)

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the number of elements in nums. Building the set requires iterating through all $N$ elements of the list.
• Space Complexity: $O(N)$. In the worst case (an array with no duplicates), a new set is created that stores all $N$ elements.

Tricks

• Leveraging Data Structure Properties: The fundamental trick is exploiting the core property of a set data structure, which is that it cannot contain duplicate elements. This transforms the problem from a search into a simple size comparison.
• Pythonic Code: This solution is a prime example of writing "Pythonic" code—using built-in types and their properties to express logic cleanly and compactly.
• Performance Consideration: This method is very readable but not always the absolute fastest. It must process the entire list to build the set, whereas the iterative method with a for loop can exit early as soon as the first duplicate is found, which is more efficient for lists with duplicates near the beginning.