Longest Consecutive Sequence and LRU Cache
Solve longest-consecutive-sequence in O(n) using a set, then design an LRU cache using an OrderedDict.
Longest Consecutive Sequence Problem
LeetCode 128 'Longest Consecutive Sequence': given an unsorted array, find the length of the longest sequence of consecutive integers. Example: [100,4,200,1,3,2] contains the consecutive sequence [1,2,3,4] of length 4. The challenge is to solve it in O(n) rather than O(n log n) (which a sort-then-scan would give).
The key insight: use a set for O(1) membership tests, and only start counting a sequence from its smallest element (identified by checking that the predecessor is absent from the set).
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set: # n is the start of a sequence
curr_n = n
length = 1
while curr_n + 1 in num_set:
curr_n += 1
length += 1
best = max(best, length)
return best
print(longestConsecutive([100,4,200,1,3,2])) # 4
print(longestConsecutive([0,3,7,2,5,8,4,6,0,1])) # 9Why the O(n) Proof Holds
Each number is visited in the while loop at most once across all iterations of the outer for loop. Even though there is a while loop inside a for loop, the total number of while loop iterations across all outer iterations is at most n (since each number is the 'curr_n + 1' of at most one sequence). This amortised argument gives O(n) overall, similar to the monotonic stack analysis.
# Demonstrate O(n) total inner iterations
nums = list(range(1000)) # worst case: one long sequence
num_set = set(nums)
inner_iters = 0
for n in num_set:
if n - 1 not in num_set:
curr = n
while curr + 1 in num_set:
curr += 1
inner_iters += 1
print('n =', len(nums), ' total inner iterations =', inner_iters)
# inner_iters = n-1 <= n => O(n)All lessons in this course
- Hash Function Internals and Collision Handling
- Two-Sum and Its Many Variants
- Frequency Counting and Grouping
- Longest Consecutive Sequence and LRU Cache