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 1:
Input: nums = [1,2,3,1]
Output: trueExample 2:
Input: nums = [1,2,3,4]
Output: falseExample 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: trueConstraints:
1 <= nums.length <= 105-109<= nums[i] <= 109Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Time complexity: The time complexity of the brute force solution
is \(O(n^2)\), where \(n\) is the number of elements in
nums, because we compare every number to all other numbers
in the array, which can potentially compare up to \(\frac{(n-1)n}{2}\) elements.
Space complexity: The space complexity is \(O(n)\) because we don’t need any extra memory to make the comparison.
Example 1:
Input: nums = [1,2,3,1]
Sort: nums = [1,1,2,3]
Compare: [\(\color{blue}{1}\),\(\color{blue}{1}\),3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Sort: nums = [1,2,3,4]
Compare: [\(\color{blue}{1}\),\(\color{blue}{2}\),3,4] \(\rightarrow\) [\(\color{blue}{1}\),2,\(\color{blue}{3}\),4] \(\rightarrow\) [\(\color{blue}{1}\),2,3,\(\color{blue}{4}\)] \(\rightarrow\) [1,\(\color{blue}{2}\),\(\color{blue}{3}\),4] \(\rightarrow\) [1,\(\color{blue}{2}\),3,\(\color{blue}{4}\)] \(\rightarrow\) [1,2,\(\color{blue}{3}\),\(\color{blue}{4}\)]
Output: false
Time complexity: The time complexity of the sorting solution is
\(O(n \log n)\), where \(n\) is the number of elements in
nums, because we need to combine sorting and one pass
iterating through the list. The sort and iterate operation has a time
complexity of \(O(n \log n)\) and \(O(n)\) respectively.
Space complexity: The space complexity is \(O(n)\), because we need to combine sorting and iterating through the list. The sort and iterate operation has a space complexity of \(O(n)\) and \(O(1)\) respectively.
Example 1:
Input: nums = [1,2,3,1]
Create: {}
Check: [\(\color{blue}{1}\),2,3,1], \(\color{blue}{1}\) \(\notin\) {} \(\rightarrow\) {\(\color{blue}{1}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),3,1], \(\color{blue}{2}\) \(\notin\) {\(\color{blue}{1}\)} \(\rightarrow\) {\(\color{blue}{1}, \color{blue}{2}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),\(\color{blue}{3}\),1], \(\color{blue}{3}\) \(\notin\) {\(\color{blue}{1}, \color{blue}{2}\)} \(\rightarrow\) {\(\color{blue}{1}, \color{blue}{2}, \color{blue}{3}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),\(\color{blue}{3}\),\(\color{blue}{1}\)], \(\color{blue}{1}\) \(\in\) {\(\color{blue}{1}, \color{blue}{2}, \color{blue}{3}\)} \(\rightarrow\) true
Output: true
Example 2:
Input: nums = [1,2,3,4]
Create: {}
Check: [\(\color{blue}{1}\),2,3,4], \(\color{blue}{1}\) \(\notin\) {} \(\rightarrow\) {\(\color{blue}{1}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),3,4], \(\color{blue}{2}\) \(\notin\) {\(\color{blue}{1}\)} \(\rightarrow\) {\(\color{blue}{1}, \color{blue}{2}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),\(\color{blue}{3}\),4], \(\color{blue}{3}\) \(\notin\) {\(\color{blue}{1}, \color{blue}{2}\)} \(\rightarrow\) {\(\color{blue}{1}, \color{blue}{2}, \color{blue}{3}\)}
Check: [\(\color{blue}{1}\),\(\color{blue}{2}\),\(\color{blue}{3}\),\(\color{blue}{4}\)], \(\color{blue}{4}\) \(\notin\) {\(\color{blue}{1}, \color{blue}{2}, \color{blue}{3}\)} \(\rightarrow\) {\(\color{blue}{1}, \color{blue}{2}, \color{blue}{3}, \color{blue}{4}\)}
Output: false
Time complexity: The time complexity of the Arrays & Hashing
solution is \(O(n)\), where \(n\) is the number of elements in
nums, because we need to one pass iterate through the list,
which has a time complexity of \(O(n)\).
Space complexity: The space complexity is \(O(n)\) because we use a set to store unique
elements from nums, which can potentially store up to n
elements.