Initial Solution
Time complexity and Space Complexity
Time Complexity: O(n log n) due to sorting the dictionary items. The initial loop to populate the dictionary is O(n), but the sorting dominates the complexity.
Space Complexity: O(n) for storing the dictionary with unique numbers from the input array.
What I didn’t know
•
sorting with the key
•
sorted function’s speed
The sorted() function in Python uses Timsort algorithm, which has O(n log n) time complexity in the worst case. While efficient for general sorting, it becomes a bottleneck when dealing with large datasets where we need linear time performance.
Best Case Time Complexity: O(n) - This occurs when there are no consecutive sequences at all, or when there's only one long sequence. In both cases, each number is checked once to see if it's a sequence start, and the inner while loop either doesn't execute or executes for the entire sequence just once.
Other Better Solutions
The optimal solution uses a HashSet to achieve O(n) time complexity. The key insight is to only start counting sequences from numbers that don't have a predecessor (num-1) in the set. This way, each number is visited at most twice - once when checking if it's a sequence start, and once when it's part of a sequence.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
# Only start counting if num is the start of a sequence
if num - 1 not in num_set:
current_num = num
current_length = 1
# Count consecutive numbers
while current_num + 1 in num_set:
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_length
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n) - Each number is visited at most twice (once in the outer loop, once in the inner while loop)
Space Complexity: O(n) - Using a HashSet to store all unique numbers