Cache With Time Limit - Solution & Explanation
Problem Statement
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"- First action is always "TimeLimitedCache" and must be executed immediately, with a 0-millisecond delay
Approach Overview
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 1: Approach 1: Using HashMap with Timestamps
This approach involves using a HashMap (or dictionary in Python) to store the key-value pairs along with their expiration timestamps. The expiration timestamp is calculated at the time of insertion by adding the current time with the duration. Each time a get or count operation is performed, expired keys are ignored.
The implementation uses an array of KeyValue structures, each holding a value and an expiration time, to simulate a hashmap. The expiration time is computed as the current time plus duration. The set operation checks if the key already exists by comparing expiration times. The get operation returns the value if the key is valid; otherwise, it returns -1. The count operation counts valid keys only.
Complexity
Time Complexity: O(1) on average for set, get, and count operations.
Space Complexity: O(n) where n is the capacity of the cache.
Approach 2: Approach 2: Using Priority Queue for Automatic Expiry
This approach combines a HashMap to store the values and their expiration time, with a PriorityQueue (or equivalent) to keep track of the order in which keys expire. Whenever a key is accessed or updated, expired keys at the front of the queue are removed to keep the cache up-to-date. This enables efficient removal of expired elements.
This C++ approach uses an unordered_map for storage and a priority_queue for expiration handling. Before any operation, expired items are removed using the priority queue to ensure correctness. This allows lazy expiration checking without iterating over the entire map for each check.
Complexity
Time Complexity: O(log n) for cleanup and set due to the priority queue, but O(1) on average for get.
Space Complexity: O(n) where n is the size of the cache.
Approach 3: Hash Table
Code
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using HashMap with Timestamps | Time Complexity: |
| Approach 2: Using Priority Queue for Automatic Expiry | Time Complexity: |
| Hash Table | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Cache With Time Limit - Leetcode 2622 - JavaScript 30-Day Challenge • NeetCodeIO • 10,703 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Cache With Time Limit easy or hard?
Cache With Time Limit Python/Java solution
How to solve Cache With Time Limit in O(1)?
What is the best approach for Cache With Time Limit?
Is Cache With Time Limit asked at Google/Amazon/Meta?
What data structure is used in Cache With Time Limit?
What is the time complexity of Cache With Time Limit?
Ready to solve this problem?
Practice Cache With Time Limit with our built-in code editor and test cases.
Practice on FleetCode