LeetCode 2622 - Cache With Time Limit

LeetCode Problem 2622

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a cache that stores key-value pairs, but unlike a normal hash map, each entry has an expiration time. A stored value remains accessible only for a limited duration measured in milliseconds. Once the duration expires, the key should behave as if it no longer exists.

We need to implement a class called TimeLimitedCache with three operations:

• set(key, value, duration) inserts or updates a key with a value and an expiration duration.
• get(key) retrieves the value if the key still exists and has not expired.
• count() returns how many currently valid, un-expired keys remain in the cache.

The most important detail is that keys automatically expire after their duration elapses. Expired keys should no longer be returned by get(), and they should not contribute to count().

The set() method has a special requirement. It should return true if the key already existed and had not expired yet, otherwise it should return false. Even if the key already exists, the method overwrites both the value and expiration duration.

The input in the examples simulates a sequence of operations over time. The actions array tells us which method is called, values provides method arguments, and timeDelays describes when each operation occurs relative to the start. These delays matter because expiration depends on elapsed time.

The constraints tell us several important things about the problem scale:

• There are at most 100 operations, which is very small.
• Keys and values can be as large as 10^9, meaning we should not rely on arrays indexed by keys.
• Durations are at most 1000 milliseconds, and delays are small.

Even though the constraints are small enough for simpler approaches, we should still aim for an efficient and clean implementation.

Several edge cases deserve attention:

• A key may expire exactly when another operation happens. We must carefully check whether expiration is inclusive or exclusive. A key becomes invalid once the expiration time is reached.
• A key may be overwritten before expiration. In this case, the old expiration timer should no longer matter.
• duration = 0 means the key expires immediately, so get() should return -1 unless checked instantly within the same execution timing.
• count() should only include valid keys, meaning expired entries must be ignored or removed.

Approaches

Brute Force Approach

A brute force solution would store every inserted key together with its expiration timestamp. Whenever get() or count() is called, we would scan all stored entries and manually remove expired ones.

For set(), we could check whether the key exists and whether its expiration timestamp is still valid. Then we overwrite the value and expiration.

For get(), we would search for the key and verify whether the current time is still less than its expiration time.

For count(), we would iterate through every key and count only those whose expiration time has not passed.

This approach is correct because expiration depends only on comparing the current timestamp with each key's stored expiration time. However, count() becomes inefficient since it repeatedly scans all keys.

Key Insight

The key observation is that JavaScript environments provide timers (setTimeout) that can automatically remove expired keys at the correct moment.

Instead of repeatedly scanning for expired entries, we can proactively schedule deletion when a key is inserted.

We use a hash map where:

• The key maps to its stored value.
• We also keep the timer reference so an existing expiration can be cancelled when overwriting a key.

When a new value is inserted:

1. Check whether an un-expired key already exists.
2. Cancel any old timer if necessary.
3. Create a new timer that deletes the key after duration milliseconds.
4. Store the updated value and timer.

Then:

• get() becomes a simple hash lookup.
• count() becomes the size of the hash map.

This makes every operation efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per query	O(n)	Repeatedly scans keys to filter expired entries
Optimal	O(1) average	O(n)	Uses hash map and scheduled expiration

Algorithm Walkthrough

1. Create a hash map to store cache entries.

Each entry stores two pieces of information: the value and a timer reference. The timer is needed so that if the same key is overwritten before expiration, we can cancel the old expiration event. 2. When set(key, value, duration) is called, first check whether the key already exists.

If the key exists in the hash map, it means it is currently un-expired because expired entries are automatically deleted. This determines whether the method returns true or false. 3. If the key already exists, cancel its old timer.

This is necessary because the previous expiration should no longer apply after overwriting the value. 4. Create a new timer using setTimeout.

The timer will automatically delete the key after duration milliseconds. This ensures expired entries disappear without manual cleanup. 5. Store the updated value and timer in the hash map.

This replaces any previous version of the key. 6. When get(key) is called, check whether the key exists in the hash map.

If it exists, return its stored value. Otherwise, return -1. 7. When count() is called, simply return the hash map size.

Since expired keys are automatically removed, the map only contains valid entries.

Why it works

The correctness relies on the invariant that the hash map always contains only un-expired keys. Every inserted key schedules its own removal exactly at expiration time, and overwriting a key cancels the previous timer to prevent stale deletions. Therefore, get() and count() always operate on a structure containing only valid cache entries.

Python Solution

from typing import Dict, Tuple
from threading import Timer

class TimeLimitedCache:

    def __init__(self):
        self.cache: Dict[int, Tuple[int, Timer]] = {}

    def set(self, key: int, value: int, duration: int) -> bool:
        key_exists = key in self.cache

        if key_exists:
            _, old_timer = self.cache[key]
            old_timer.cancel()

        def expire() -> None:
            self.cache.pop(key, None)

        timer = Timer(duration / 1000, expire)
        timer.start()

        self.cache[key] = (value, timer)

        return key_exists

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        return self.cache[key][0]

    def count(self) -> int:
        return len(self.cache)

The implementation uses a dictionary where each key maps to a tuple containing the stored value and an active timer.

Inside set(), we first determine whether the key already exists. Since expired keys are removed automatically, any key present in the dictionary is guaranteed to still be valid.

If the key exists, we cancel the old timer before overwriting. Without this step, the previous timer could still fire and accidentally delete the newly updated value.

A nested expire() function removes the key when the timer finishes. We then create a new timer using Timer(duration / 1000, expire) because Python timers use seconds rather than milliseconds.

The get() method is intentionally simple. Since expired entries are automatically removed, we only need to check whether the key exists.

Similarly, count() returns the dictionary length because only valid entries remain in storage.

Important Note: LeetCode's original environment for this problem is JavaScript, where setTimeout is available. Python submissions may vary depending on execution support. The algorithmic idea remains the same.

Go Solution

package main

import (
	"sync"
	"time"
)

type CacheEntry struct {
	value int
	timer *time.Timer
}

type TimeLimitedCache struct {
	cache map[int]CacheEntry
	mutex sync.Mutex
}

func Constructor() TimeLimitedCache {
	return TimeLimitedCache{
		cache: make(map[int]CacheEntry),
	}
}

func (this *TimeLimitedCache) Set(key int, value int, duration int) bool {
	this.mutex.Lock()
	defer this.mutex.Unlock()

	_, exists := this.cache[key]

	if exists {
		this.cache[key].timer.Stop()
	}

	timer := time.AfterFunc(
		time.Duration(duration)*time.Millisecond,
		func() {
			this.mutex.Lock()
			defer this.mutex.Unlock()
			delete(this.cache, key)
		},
	)

	this.cache[key] = CacheEntry{
		value: value,
		timer: timer,
	}

	return exists
}

func (this *TimeLimitedCache) Get(key int) int {
	this.mutex.Lock()
	defer this.mutex.Unlock()

	entry, exists := this.cache[key]
	if !exists {
		return -1
	}

	return entry.value
}

func (this *TimeLimitedCache) Count() int {
	this.mutex.Lock()
	defer this.mutex.Unlock()

	return len(this.cache)
}

The Go version follows the same design but uses time.AfterFunc() instead of Python's Timer. Since timers execute asynchronously in goroutines, a mutex is required to protect concurrent access to the shared map.

Unlike Python, Go does not have automatic thread safety for maps. Without synchronization, concurrent timer execution could lead to race conditions.

Worked Examples

Example 1

Input:

actions = ["TimeLimitedCache", "set", "get", "count", "get"]
values = [[], [1, 42, 100], [1], [], [1]]
timeDelays = [0, 0, 50, 50, 150]

Time	Operation	Cache State	Return
0	Initialize	{}	null
0	set(1, 42, 100)	{1: 42}	false
50	get(1)	{1: 42}	42
50	count()	{1: 42}	1
100	key expires	{}	-
150	get(1)	{}	-1

At time 0, the cache is empty. We insert key 1 with expiration at 100ms.

At 50ms, the key still exists, so get(1) returns 42, and count() returns 1.

At 100ms, the timer removes the key.

At 150ms, the cache is empty, so get(1) returns -1.

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]

Time	Operation	Cache State	Return
0	Initialize	{}	null
0	set(1, 42, 50)	{1: 42}	false
40	set(1, 50, 100)	{1: 50}	true
50	get(1)	{1: 50}	50
120	get(1)	{1: 50}	50
140	key expires	{}	-
200	get(1)	{}	-1
250	count()	{}	0

At 40ms, key 1 still exists, so set() returns true. The old timer is cancelled and replaced with a new expiration at 140ms.

The key remains accessible until expiration, after which get() returns -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) average	Hash map operations and timer setup are constant time
Space	O(n)	At most n active keys stored in the cache

Each operation performs a constant number of hash map lookups, insertions, or deletions. Since expiration is handled asynchronously by timers, no extra scanning work is required.

The space complexity is linear because we store one map entry and one timer for each active key.

Test Cases

import time

cache = TimeLimitedCache()

assert cache.set(1, 42, 100) is False  # new key
assert cache.get(1) == 42  # immediate retrieval
assert cache.count() == 1  # one active key

time.sleep(0.15)
assert cache.get(1) == -1  # expired key
assert cache.count() == 0  # cache empty after expiration

cache = TimeLimitedCache()

assert cache.set(1, 42, 100) is False  # initial insert
time.sleep(0.05)
assert cache.set(1, 50, 100) is True  # overwrite before expiry
assert cache.get(1) == 50  # updated value

time.sleep(0.08)
assert cache.get(1) == 50  # still valid under new timer

time.sleep(0.05)
assert cache.get(1) == -1  # expired after overwrite

cache = TimeLimitedCache()

assert cache.set(1, 99, 0) is False  # zero duration
time.sleep(0.01)
assert cache.get(1) == -1  # immediate expiry

cache = TimeLimitedCache()

assert cache.set(1, 10, 100) is False
assert cache.set(2, 20, 100) is False
assert cache.count() == 2  # multiple keys

time.sleep(0.15)
assert cache.count() == 0  # all expired

cache = TimeLimitedCache()

assert cache.get(999) == -1  # missing key
assert cache.count() == 0  # empty cache

Test	Why
Basic insertion and expiration	Verifies normal cache lifecycle
Overwrite existing key	Ensures timer replacement works correctly
Zero duration	Validates immediate expiration
Multiple keys	Confirms independent expiration handling
Missing key lookup	Verifies -1 behavior

Edge Cases

Overwriting a Key Before Expiration

A key may be updated before its previous expiration timer fires. This is a common source of bugs because the old timer might still delete the newly updated value.

For example, if key 1 expires in 50ms, but we overwrite it at 40ms with a new 100ms duration, the original expiration must not remove the updated entry. The implementation handles this by cancelling the previous timer before creating a new one.

Duration Equal to Zero

A duration of 0 means the key expires immediately. A naive implementation might accidentally leave the key accessible longer than intended.

The timer-based solution handles this naturally because the expiration callback runs immediately. The key becomes unavailable almost instantly and get() correctly returns -1.

Expiration Exactly at Query Time

A subtle boundary condition occurs when an operation happens exactly at the expiration timestamp. The key should already be considered expired.

Since expiration is scheduled precisely through timers, once the duration elapses the key is removed from the map. Any subsequent get() or count() call correctly behaves as if the key never existed.