Watch 10 video solutions for Cache With Time Limit, a medium level problem. This walkthrough by NeetCodeIO has 10,383 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.
The class has three public methods:
set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.
get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.
count(): returns the count of un-expired keys.
Example 1:
Input: actions = ["TimeLimitedCache", "set", "get", "count", "get"] values = [[], [1, 42, 100], [1], [], [1]] timeDelays = [0, 0, 50, 50, 150] Output: [null, false, 42, 1, -1] Explanation: At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned. At t=50, key=1 is requested and the value of 42 is returned. At t=50, count() is called and there is one active key in the cache. At t=100, key=1 expires. At t=150, get(1) is called but -1 is returned because the cache is empty.
Example 2:
Input: actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"] values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []] timeDelays = [0, 0, 40, 50, 120, 200, 250] Output: [null, false, true, 50, 50, -1, 0] Explanation: At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned. At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten. At t=50, get(1) is called which returned 50. At t=120, get(1) is called which returned 50. At t=140, key=1 expires. At t=200, get(1) is called but the cache is empty so -1 is returned. At t=250, count() returns 0 because the cache is empty.
Constraints:
0 <= key, value <= 1090 <= duration <= 10001 <= actions.length <= 100actions.length === values.lengthactions.length === timeDelays.length0 <= timeDelays[i] <= 1450actions[i] is one of "TimeLimitedCache", "set", "get" and "count"Problem Overview: Design a cache where each key-value pair expires after a given time limit. You must implement set, get, and count so expired entries are ignored while active entries behave like a normal key-value store.
Approach 1: Using HashMap with Timestamps (Time: O(1), Space: O(n))
The straightforward solution stores each key in a hash map along with its value and expiration timestamp. When set(key, value, duration) runs, compute the expiry time using the current timestamp plus duration. Store both the value and expiry in the map. If the key already exists and hasn't expired yet, return true; otherwise overwrite it and return false.
For get(key), perform a constant-time hash lookup. If the key does not exist or the stored expiration time is less than the current time, treat it as expired and return -1. Otherwise return the stored value. The count() method iterates over stored entries and counts only those with expiry timestamps greater than the current time.
The key insight is lazy expiration. Instead of actively removing expired entries, the cache checks expiration only when the key is accessed or counted. This keeps set and get operations at O(1) average time while using O(n) space for stored entries. This design is common in lightweight in-memory caches and interview settings.
Approach 2: Using Priority Queue for Automatic Expiry (Time: O(log n), Space: O(n))
A more structured design tracks expirations using a priority queue (min-heap). Each entry pushed into the heap contains (expiryTime, key). The heap always keeps the earliest expiration at the top.
Before executing any cache operation, repeatedly remove heap entries whose expiry time is less than the current timestamp. When an item expires, remove its key from the map as well. This keeps the active cache clean without relying on lazy checks.
The hash map still stores the actual key-value pairs for constant-time retrieval, while the heap efficiently identifies the next item that should expire. Heap insertion and removal cost O(log n), which slightly increases runtime compared to the pure hash map solution, but it keeps the structure strictly synchronized with expiration events.
This pattern appears frequently in system design problems involving TTL caches, task scheduling, or delayed execution queues. Combining a hash map with a priority queue provides both fast lookups and efficient expiration management.
Recommended for interviews: The HashMap with timestamps approach is typically expected. It demonstrates strong understanding of constant-time lookups and lazy expiration logic. The priority queue version shows deeper design thinking and is closer to how production systems manage timed events, but the simpler hash map approach is usually sufficient in interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap with Timestamps | O(1) average for set/get, O(n) for count | O(n) | Best general solution. Simple implementation with lazy expiration checks. |
| HashMap + Priority Queue (Min Heap) | O(log n) per insertion/expiry | O(n) | Useful when automatic cleanup of expired entries is required. |