The Problem
Given an integer array nums
, return true
if any value appears at least twice in the array, and return false
if every element is distinct.
Example
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at indices 0 and 3.
Follow-up: Can you come up with an algorithm that has less than O(NlogN) time complexity?
Brute Force Solution
func containsDuplicate(_ nums: [Int]) -> Bool {
var nums = nums
let N = nums.count
if N == 0 {
return false
}
nums.sort()
var prev = nums[0]
for i in 1 ..< N {
let num = nums[i]
if num == prev {
return true
} else {
prev = num
}
}
return false
}
Explanation
The brute force solution for this problem uses sorting to allow us to quickly detect duplicates since identical elements will be adjacent. After sorting, it iterates through all elements, checking if the current element is equal to the previous one; if it is, it returns true
immediately. If not, it updates prev
. If no duplicates are detected, it returns false
.
Time/Space Complexity
- Time complexity: O(NlogN) or O(N^2) depending on the sorting algorithm.
- Space complexity: O(1) or O(N) depending on the sorting algorithm; some sorting algorithms may use additional space.
Solution - 2
func containsDuplicate(_ nums: [Int]) -> Bool {
var seen: Set<Int> = []
for num in nums {
if seen.contains(num) {
return true
} else {
seen.insert(num)
}
}
return false
}
Explanation
Solution - 2 is more optimized than brute force, trading memory for faster execution time.
- It uses a
seen
set and iterates overnums
. - It checks if
num
has already been seen; if it has, it returnstrue
; if not, it insertsnum
into theseen
set. - When iteration is completed, it returns
false
because no duplicates were found.
Time/Space Complexity
- Time complexity: O(N) - in the worst case, the algorithm iterates over all
nums
. - Space complexity: O(N) - extra space is needed to store
seen
values in a set.