Contains Duplicate

Hash set membership test — return true on the first repeat.

Easy
Time O(n) Space O(n)
LeetCode
2 min read
hash-set array

Problem#

Return true iff any value appears at least twice in the array.

Examples#

  • [1,2,3,1]true.
  • [1,2,3,4]false; [1,1,1,3,3,4,3,2,4,2]true.

Constraints#

  • 1 <= nums.length <= 10^5.

Approach#

Walk the array, insert into a hash set. If insertion fails (already present), return true.

Solution#

Contains Duplicate
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int v : nums) {
if (!seen.insert(v).second) return true;
}
return false;
}
};

Editorial#

insert returns a pair <iterator, bool> where the bool indicates “newly inserted” — a clean one-shot membership-plus-insert. Sorting and adjacent compare gives O(n log n) without extra space, useful if memory is tight.

Complexity#

  • Time: O(n) average.
  • Space: O(n).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.