Contains Duplicate

easyFREEArrays & HashingBlind 75

Given an integer array nums, return True if any value appears at least twice in the array, and False if every element is distinct.

Example

Input

1,2,3,1

Output

True

Reasoning

Input: nums is a list of integers; the sample 1,2,3,1 means nums $= [1, 2, 3, 1]$ , so $n = 4$ and the positions are $0, 1, 2, 3$ .
The question: do two different positions $i \neq j$ hold the same value, i.e. is there a pair with $\text{nums}_i = \text{nums}_j$ ?
Checking the pairs: positions $0$ and $3$ both hold $1$ , so $\text{nums}_0 = \text{nums}_3 = 1$ with $0 \neq 3$ . One such pair is enough, and the answer is True.
Contrast with $[1, 2, 3, 4]$ : all four values differ, so no pair of positions matches and the answer is False.
Output: a single boolean, not a count and not the repeated value. In $[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]$ several values repeat, sometimes three times, yet the output is still just True.
Notice that the two equal values need not be adjacent and order is irrelevant: the two $1$ s here sit at opposite ends of the list.

Constraints

1 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Contains Duplicate" problem falls under the category of Arrays & Hashing, which involves using data structures like arrays and hash tables to solve problems efficiently. In this context, understanding how to iterate through arrays and use hash tables (such as sets or dictionaries in Python) is crucial. The problem requires checking for duplicate elements, which can be approached by considering the properties of sets. A set in mathematics is a collection of unique elements, meaning it does not allow duplicates. This concept can be leveraged to solve the problem.

Understanding the trade-offs between different data structures is also important. For instance, arrays allow for efficient indexing and are suitable for problems that require frequent access to elements by their index. On the other hand, hash tables offer fast lookup, insertion, and deletion operations, making them ideal for problems that involve checking for the existence of elements or counting frequencies. In the context of this problem, recognizing when to use a hash table can significantly simplify the solution.

The problem statement involves a simple yet fundamental concept in computer science: iteration and lookup. Being able to iterate through each element in the array and perform a lookup to check for duplicates is key. This involves understanding how to use loops (like for loops) and conditional statements (if statements) to control the flow of the program based on the presence or absence of duplicate elements.

Algorithm/Approach

The general approach to solving this type of problem involves using a hashing technique. The idea is to iterate through the array and use a hash table to keep track of the elements encountered so far. Since hash tables allow for constant time complexity lookup, this approach enables efficient checking for duplicates. The algorithm pattern typically involves initializing an empty hash table, then iterating through the array. For each element, it checks if the element is already present in the hash table. If it is, the algorithm returns True because a duplicate has been found. If the element is not in the hash table, it is added.

Step-by-Step Strategy

Initialize an empty hash table (like a set in Python).
Iterate through each element in the input array.
For each element, check if it is already present in the hash table.
If the element is found in the hash table, immediately return True because a duplicate has been found.
If the element is not in the hash table, add it to the hash table.
If the iteration completes without finding any duplicates, return False, indicating all elements are distinct.

Common Pitfalls

Failing to initialize the hash table correctly.
Incorrectly checking for the presence of an element in the hash table.
Not handling the case where the input array is empty.
Using the wrong data structure for the problem, leading to inefficient solutions.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of elements in the input array, because each element is processed once. The space complexity is also $O(n)$ because in the worst-case scenario (all elements are unique), the size of the hash table will be equal to the size of the input array.

solution.py

Python 3.13

Test results