Contains Duplicate - Solution & Explanation

Problem Overview: You are given an integer array nums. The task is simple: return true if any value appears at least twice in the array, otherwise return false. The challenge is detecting duplicates efficiently without unnecessary comparisons.

Approach 1: Using a HashSet to Check for Duplicates (Time: O(n), Space: O(n))

The most efficient solution uses a hash table, typically implemented as a HashSet. Iterate through the array once. For each element, check whether it already exists in the set. Hash lookups run in constant time on average, so this check is fast. If the value is already present, a duplicate exists and you can immediately return true. Otherwise, insert the value into the set and continue scanning.

The key insight: a set automatically enforces uniqueness. By checking membership before insertion, duplicates are detected instantly without comparing against every previous element. The algorithm performs one pass through the array, making it linear time O(n). The trade‑off is extra memory because the set may store up to n elements, resulting in O(n) space.

This approach is the standard solution for problems involving fast membership checks in an array. It scales well for large inputs and is usually the first method expected in interviews.

Approach 2: Sorting the Array (Time: O(n log n), Space: O(1) or O(n))

Another method sorts the array first, then checks neighboring elements. After sorting, duplicates become adjacent. Iterate through the sorted array and compare nums[i] with nums[i - 1]. If they match at any point, a duplicate exists.

Sorting takes O(n log n) time using standard algorithms like quicksort or mergesort. The scan afterward is linear O(n), so overall complexity remains O(n log n). Space complexity depends on the sorting implementation: in‑place sorts such as heapsort use O(1) extra space, while mergesort-based implementations may use O(n).

This approach avoids explicit hash structures and can be useful when sorting is already required for later operations. It also appears frequently in problems related to sorting and duplicate detection patterns.

Recommended for interviews: The HashSet approach is the expected optimal answer. It demonstrates understanding of constant-time hash lookups and efficient duplicate detection in linear time. Mentioning the sorting alternative shows awareness of tradeoffs: lower auxiliary structures at the cost of O(n log n) runtime. Strong candidates typically explain both, implement the hash-based solution, and discuss complexity clearly.