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 and LRU Cache is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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)Alternative: Sort-Based Approach
For contrast, the sort-and-scan approach runs in O(n log n): sort the array, deduplicate consecutive duplicates, then count consecutive runs. While slower, it uses O(1) extra space (if sorting in-place). The set approach uses O(n) extra space. Mention both in an interview and clarify whether the O(n log n) solution is acceptable given space constraints.
def longestConsecutive_sort(nums):
if not nums:
return 0
nums.sort()
best = length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
continue # skip duplicates
if nums[i] == nums[i-1] + 1:
length += 1
best = max(best, length)
else:
length = 1
return best
print(longestConsecutive_sort([100,4,200,1,3,2])) # 4What Is an LRU Cache?
An LRU (Least Recently Used) cache is a fixed-capacity data structure that evicts the least recently used item when it is full and a new item needs to be inserted. Operations: get(key) returns the value if key exists (and marks it as recently used) or -1 if absent; put(key, value) inserts the pair (evicting LRU if at capacity).
LRU caches are used in operating systems (page replacement), browser caches, and database query caches. LeetCode 146 asks you to implement one with O(1) get and put.
LRU Cache Using OrderedDict
Python's collections.OrderedDict maintains insertion order and supports move_to_end(key) (O(1)) to mark an item as most recently used. On put, move the key to the end; on overflow, pop the first item (LRU). This gives O(1) get and put using a built-in that is backed by a doubly-linked list + hash map internally.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict LRU (first item)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1 (and 1 becomes most recently used)
cache.put(3, 3) # evict key 2 (LRU)
print(cache.get(2)) # -1
cache.put(4, 4) # evict key 1 (LRU)
print(cache.get(1)) # -1
print(cache.get(3)) # 3
print(cache.get(4)) # 4LRU Cache from Scratch: Doubly Linked List + HashMap
The from-scratch implementation uses a doubly linked list (to support O(1) node removal) and a hash map (for O(1) node lookup by key). The list maintains order from LRU (head.next) to MRU (tail.prev). Dummy head and tail sentinels eliminate edge cases for insertion and removal at the boundaries.
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheDLL:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> DNode
self.head = DNode() # dummy LRU end
self.tail = DNode() # dummy MRU end
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = DNode(key, val)
self._add_to_tail(node)
self.map[key] = node
if len(self.map) > self.cap:
lru = self.head.next
self._remove(lru)
del self.map[lru.key]
cache = LRUCacheDLL(2)
cache.put(1,1); cache.put(2,2)
print(cache.get(1)) # 1
cache.put(3,3)
print(cache.get(2)) # -1 (evicted)Why Doubly Linked List for LRU?
A singly linked list cannot remove an arbitrary node in O(1) without knowing the predecessor. A doubly linked list stores both prev and next pointers, making removal O(1) given the node reference. The hash map provides O(1) access to the node by key. Together: get(key) takes O(1) to find the node and O(1) to move it to the tail; put(key) takes O(1) to add and O(1) to remove the LRU node from the head.
# Why not a singly linked list?
# To remove a node you need its predecessor
# With SLL: must traverse from head to find predecessor => O(n)
# With DLL: node.prev IS the predecessor => O(1) removal
print('SLL removal: O(n) — must find predecessor by traversal')
print('DLL removal: O(1) — node.prev is immediately available')
print('Hash map lookup: O(1) — get DNode reference by key')
print('Combined LRU get/put: O(1) average')LFU Cache (Least Frequently Used)
A harder variant is the LFU cache (LeetCode 460), where the item with the smallest access count is evicted. Ties are broken by recency (least recently used among least frequent). Implementation requires three data structures: a key-to-value map, a key-to-frequency map, and a frequency-to-OrderedDict map (to maintain insertion order within each frequency group). LFU get and put are O(1) amortised.
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.min_f = 0
self.kv = {} # key -> val
self.kf = {} # key -> freq
self.fk = defaultdict(OrderedDict) # freq -> {key: None}
def _touch(self, key):
f = self.kf[key]
self.kf[key] = f + 1
del self.fk[f][key]
if not self.fk[f] and f == self.min_f:
self.min_f += 1
self.fk[f+1][key] = None
def get(self, key):
if key not in self.kv:
return -1
self._touch(key)
return self.kv[key]
def put(self, key, val):
if self.cap == 0: return
if key in self.kv:
self.kv[key] = val
self._touch(key)
else:
if len(self.kv) == self.cap:
lfu_key, _ = self.fk[self.min_f].popitem(last=False)
del self.kv[lfu_key]; del self.kf[lfu_key]
self.kv[key] = val; self.kf[key] = 1
self.fk[1][key] = None; self.min_f = 1Design Patterns: Hash Map + Linked List
The LRU cache illustrates a powerful design pattern: combine a hash map for O(1) key lookup with a linked list for O(1) ordered operations. This pattern appears in several interview design problems: LRU cache, LFU cache, skip lists, and some queue variants. Whenever a problem requires both O(1) lookup and O(1) order-based operations, consider this combination.
In interviews, stating this pattern explicitly demonstrates system-level thinking and familiarity with classic data structure combinations.
Consecutive Sequence in a Matrix
An extension of the consecutive sequence idea to 2D: given a matrix of integers, find the length of the longest consecutive sequence that can be traced (each step moves to an adjacent cell). This combines BFS/DFS with the consecutive-sequence set approach. Store each value's position, then for each starting value check if value+1 exists as a neighbour.
# Simpler: find longest consecutive values in a 2D matrix (no adjacency)
def longestConsecutiveMatrix(matrix):
all_vals = set()
for row in matrix:
for v in row:
all_vals.add(v)
best = 0
for v in all_vals:
if v - 1 not in all_vals: # start of sequence
length = 0
while v in all_vals:
v += 1
length += 1
best = max(best, length)
return best
m = [[1, 5, 3], [4, 6, 2], [8, 7, 9]]
print(longestConsecutiveMatrix(m)) # 9 (1..9 all present)Interview Summary: Set + HashMap Power
These two problems share a theme: converting O(n log n) or O(n²) problems to O(n) using the right hash structure. Longest consecutive sequence uses a set to answer 'is the predecessor present?' in O(1). LRU cache uses a hash map to find the node instantly and a doubly linked list to update order in O(1). Both replace slow traversal with O(1) membership or lookup.
When an interviewer says 'can you do better than O(n log n)?', the answer is almost always 'use a hash map or hash set to avoid sorting'.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: longest consecutive sequence runs in O(n) by using a set for O(1) membership and only starting counts from sequence beginnings, LRU cache achieves O(1) get and put using an OrderedDict (or hash map + doubly linked list from scratch), and the hash map + linked list pattern is a reusable building block for order-sensitive O(1) data structures. Next up we revisit recursion with the base-case, trust, and build framework.
Frequently asked questions
Is the “Longest Consecutive Sequence and LRU Cache” lesson free?
Yes — the full text of “Longest Consecutive Sequence and LRU Cache” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Longest Consecutive Sequence and LRU Cache”?
Solve longest-consecutive-sequence in O(n) using a set, then design an LRU cache using an OrderedDict. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Consecutive Sequence and LRU Cache” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
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