type
status
date
slug
summary
tags
category
icon
password
Problem Statement
Given an integer array
nums, return true if any value appears at least twice, and false if all elements are distinct.Difficulty: Easy
Example
Input: nums = [1, 2, 3, 3]
Output: true
Input: nums = [1, 2, 3, 4]
Output: false
Solutions
1. Brute Force Approach
Core Idea: Compare every element with every other element in the array. This is the most direct, albeit inefficient, way to find a match.
Compare each element with every other element.
Time complexity: O(n²), Space complexity: O(1).
2. Sorting Method
Core Idea: If an array is sorted, any duplicate elements will become adjacent to each other.
Sort the array and check adjacent elements.
Time complexity: O(n log n), Space complexity: O(1).
3. Hash Set Solution
Core Idea: Use a hash set for its incredibly fast lookup capabilities to keep track of elements you've already seen.
Use a hash set for O(1) lookups.
Time complexity: O(n), Space complexity: O(n).
4. Hash Set Length
Core Idea: A set, by definition, only stores unique elements. Therefore, if we convert our input array into a set, any duplicates will be discarded. If the resulting set's size is smaller than the original array's length, it means duplicates must have existed.
Time complexity: O(n), Space complexity: O(n).
Comparison
Solution | Time Complexity | Space Complexity |
Brute Force | O(n²) | O(1) |
Sorting | O(n log n) | O(1) |
Hash Set | O(n) | O(n) |
Best Practice
The hash set solution is generally the most efficient approach, providing a good balance between time and space complexity. Use it unless memory constraints are very strict.