Contains Duplicate LeetCode 217 Deep Dive

LeetCode 217 — Contains Duplicate — gives you an integer array nums and asks you to return true if any value appears at least twice in the array, and false if every element is distinct. For example, nums = [1, 2, 3, 1] returns true because 1 appears at indices 0 and 3. But nums = [1, 2, 3, 4] returns false because all four values are distinct. The problem is rated Easy and is typically the first problem assigned in LeetCode study plans.

Despite its Easy rating, Contains Duplicate is the perfect vehicle for introducing two fundamental algorithmic patterns: HashSet membership checking and sort-then-scan. These two approaches embody the classic space-vs-time trade-off: HashSet gives O(n) time at the cost of O(n) extra space, while sorting gives O(n log n) time but only O(1) extra space if done in-place. Understanding both and being able to discuss the trade-off is what interviewers look for when they assign this problem.

The constraints are generous: 1 <= nums.length <= 10^5 and the values can be any 32-bit signed integer. This means a brute force O(n^2) approach will time out — with n up to 100,000, comparing all pairs gives up to 5 * 10^9 operations, far exceeding what can run in 1-2 seconds. An efficient approach is required.

The brute force approach checks all pairs (i, j) where i < j and returns true if nums[i] == nums[j] for any pair. Two nested loops iterate over all combinations: the outer loop runs from index 0 to n-2 and the inner loop runs from i+1 to n-1. If a matching pair is found, return true immediately; if no match is found after all pairs are checked, return false.

This approach is correct but has O(n^2) time complexity — with n = 10^5, this means up to 5 * 10^9 comparisons, which will exceed the time limit. The space complexity is O(1) since no extra data structures are used. The brute force is useful only for very small inputs or for establishing correctness before optimizing.

In an interview, mentioning the brute force first is fine — it shows you understand the problem and can verify correctness. But always follow up immediately with the optimized approach. Saying "the brute force is O(n^2) and will time out; here are two better approaches with different trade-offs" is exactly the right framing to show algorithmic maturity.

The sorting approach exploits the property that sorting brings equal elements adjacent to each other. Sort nums in-place, then do a single pass comparing each element to its neighbor: if nums[i] == nums[i-1] for any i from 1 to n-1, a duplicate exists and you return true. If the entire array is traversed without finding adjacent equals, return false.

The time complexity is O(n log n) dominated by the sort. If the sort is done in-place (as in Python's list.sort() or Java's Arrays.sort()), the space complexity is O(1) — no extra data structure proportional to n is needed. This makes sorting attractive in memory-constrained environments where the O(n) HashSet space is unacceptable.

The sorting approach is slightly more verbose than the HashSet approach and has worse time complexity, but its O(1) space usage is a genuine advantage in certain contexts. In an interview, presenting both approaches and explaining when you would choose each (HashSet for speed, sorting for memory) demonstrates the depth interviewers are looking for on this problem.

The HashSet approach iterates through the array and adds each element to a set. Before adding, check if the element is already in the set: if it is, a duplicate has been found and you return true immediately. If the element is not yet in the set, add it and continue. If you reach the end of the array without finding a duplicate, return false.

This is O(n) time because each element is processed exactly once and HashSet membership checks and insertions are O(1) on average. The space complexity is O(n) in the worst case — if all elements are distinct, every element is added to the set. In the best case (duplicate found immediately), the set holds only one or two elements.

In Java, HashSet.add(element) returns false if the element was already in the set, which allows a particularly clean implementation: for each element, if add returns false, return true. In Python, the check is explicit: if num in seen: return True; seen.add(num). Both are idiomatic for their respective languages and both have the same O(n) time and O(n) space complexity.

The HashSet approach with early exit returns true as soon as the first duplicate is detected, without processing any remaining elements. In the best case — when duplicates appear at the very beginning of the array — the algorithm terminates in O(1) time after examining just two elements. This is a significant practical advantage over approaches that always process the entire array.

Consider an array where the first two elements are the same: [5, 5, 1, 2, 3, ...]. The early exit HashSet finds the duplicate immediately and returns. The sorting approach must still sort the entire array before discovering the adjacent duplicate. The Python one-liner set(nums) also processes the entire array before comparing lengths. For duplicate-heavy inputs, early exit can be dramatically faster in practice.

Even the worst-case scenario — all elements distinct — processes each element exactly once, maintaining the O(n) theoretical bound. The early exit is a pure optimization with no downside: it never makes the algorithm slower and can make it arbitrarily faster. Always implement early exit in the HashSet approach; there is no reason not to.

Python — one-liner: def containsDuplicate(nums): return len(nums) != len(set(nums)). This builds the full set before comparing lengths; it is correct and minimal but does not exit early. Python — explicit loop with early exit: def containsDuplicate(nums): seen = set(); [return True for num in nums if num in seen or seen.add(num)]; return False. More idiomatically: seen = set() then for num in nums: if num in seen: return True; seen.add(num). Then return False outside the loop. O(n) time, O(n) space, with early exit.

Java — HashSet.add() returns false on duplicate: public boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (!seen.add(num)) return true; } return false; }. The add() method of HashSet returns false if the element was already present, so !seen.add(num) is true when a duplicate is found. This is idiomatic Java and avoids a separate contains() call, making the code slightly more efficient. O(n) time, O(n) space.

Both Python and Java implementations handle all edge cases: a single-element array (always returns false), an array of all identical elements (returns true on the second element), and an array where the duplicate is the last pair encountered. The Java solution benefits from HashSet's O(1) amortized add() and contains() backed by a hash table, giving consistent performance across all integer values including negative numbers and Integer.MIN_VALUE.

Valid Anagram (LeetCode 242) uses the same HashSet/frequency-map pattern applied to character membership: instead of checking if an integer appears twice, you check if character frequencies match between two strings. Contains Duplicate and Valid Anagram together form the foundation of the HashSet membership problem family — mastering one makes the other straightforward.

Two Sum (LeetCode 1) extends the HashSet pattern: instead of checking if the current element has been seen before, you check if the complement (target - current) has been seen. The data structure is the same (a hash map), but the lookup key changes from the element itself to its complement. Longest Consecutive Sequence (LeetCode 128) uses a HashSet to achieve O(n) by checking if each element is the start of a sequence: only begin counting from elements where element - 1 is not in the set.

The set membership family includes: Contains Duplicate II (LeetCode 219, within k distance), Contains Duplicate III (LeetCode 220, within k distance and t value difference), Find the Duplicate Number (LeetCode 287, with the constraint of no extra space using Floyd's cycle detection), and Happy Number (LeetCode 202, detecting a cycle in the sequence using a HashSet). All of these build directly on the core pattern introduced in LeetCode 217.