Initial Solution
Time and Space Complexity Analysis
Time Complexity: O(n log n)
•
The sort() method dominates the time complexity with O(n log n), where n is the length of the input array
•
The subsequent loop that checks for duplicates runs in O(n) time
•
Overall: O(n log n) + O(n) = O(n log n)
Space Complexity: O(1) or O(n)
•
If the sorting is done in-place (which Python's sort() does), the space complexity is O(1) auxiliary space
•
However, some sorting algorithms may require O(log n) space for the recursion stack
•
Python's Timsort uses O(n) space in the worst case
Alternative Approach:
•
Using a hash set would provide O(n) time complexity and O(n) space complexity
•
This would be more efficient for time but uses more space
What I didn’t know
•
Implement hashmap with python
Optimized Solution with HashSet
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Python
복사
Time and Space Complexity Analysis
Time Complexity: O(n)
•
We iterate through the array once, performing O(1) hash set operations for each element
•
This is more efficient than the sorting approach
Space Complexity: O(n)
•
In the worst case (no duplicates), we store all n elements in the hash set
•
This trades space for improved time complexity