LeetCode 1797 - Design Authentication Manager

The problem asks us to design an authentication system that manages tokens with expiration times. Each token is valid for a fixed timeToLive seconds starting from the moment it is generated or renewed.

leetcodemediumhash-tablelinked-listdesigndoubly-linked-list

LeetCode Problem 1797

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List, Design, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to design an authentication system that manages tokens with expiration times. Each token is valid for a fixed timeToLive seconds starting from the moment it is generated or renewed. The system must support three operations: generating a new token, renewing an existing unexpired token, and counting the number of unexpired tokens at a given time.

The input represents a sequence of operations on this system. For generate(tokenId, currentTime), a new token is created. For renew(tokenId, currentTime), the system should extend the expiration of the token only if it has not already expired. For countUnexpiredTokens(currentTime), we need to return how many tokens are still valid at that moment.

Important constraints and observations include: all currentTime values are strictly increasing, so we never need to handle events in the past. All generate calls have unique token IDs, so no two tokens will share the same ID. The maximum number of operations is small (up to 2000), but timeToLive and currentTime can be very large (up to 10^8), which rules out naïve approaches that iterate over all possible times or simulate every second.

Key edge cases include attempting to renew a token that has already expired, generating multiple tokens with different IDs at different times, and counting unexpired tokens exactly at their expiration time, which happens before any operation at that timestamp.

Approaches

A brute-force approach would store each token with its expiration time in a list or dictionary. Each time renew or countUnexpiredTokens is called, we iterate over all tokens and check if they have expired. This approach is correct but inefficient for large numbers of tokens because each operation could be O(n), leading to a total of O(n^2) complexity in the worst case.

The optimal approach leverages a hash map for O(1) token lookup and a data structure that allows us to efficiently discard expired tokens. Since currentTime is strictly increasing, we can maintain a queue (or ordered dictionary) of tokens in the order they expire. Every time an operation occurs, we can remove all tokens from the front of the queue that have already expired. The hash map ensures we can renew or check tokens in constant time, while the queue allows efficient removal of expired tokens.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Stores tokens in a dictionary/list; every operation checks all tokens
Optimal O(n) O(n) Uses hash map + queue to track expiration efficiently; each token is processed at most twice

Algorithm Walkthrough

  1. Initialize an AuthenticationManager object with timeToLive. Maintain a hash map tokens mapping tokenId to its expiration time, and a queue expiryQueue to track tokens in order of expiration.
  2. To generate a token at currentTime, compute its expiration time as currentTime + timeToLive. Add the token to the hash map and append it to the queue.
  3. To renew a token at currentTime, first purge expired tokens by checking the front of the queue and removing any token whose expiration time is ≤ currentTime. Then, if the token exists in the hash map and is unexpired, update its expiration time in both the hash map and append the new expiration to the queue.
  4. To count unexpired tokens, purge expired tokens first. The length of the hash map gives the number of currently valid tokens.

Why it works: By maintaining the queue in order of expiration and strictly processing timestamps in increasing order, we guarantee that expired tokens are always removed before any operation at that time. The hash map allows constant-time access to individual tokens, while the queue ensures expired tokens are efficiently discarded.

Python Solution

from collections import deque

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokens = {}  # tokenId -> expiry time
        self.expiryQueue = deque()  # stores tuples (expiryTime, tokenId)

    def _purge(self, currentTime: int) -> None:
        while self.expiryQueue and self.expiryQueue[0][0] <= currentTime:
            expiry, tokenId = self.expiryQueue.popleft()
            if self.tokens.get(tokenId, 0) == expiry:
                del self.tokens[tokenId]

    def generate(self, tokenId: str, currentTime: int) -> None:
        expiry = currentTime + self.timeToLive
        self.tokens[tokenId] = expiry
        self.expiryQueue.append((expiry, tokenId))

    def renew(self, tokenId: str, currentTime: int) -> None:
        self._purge(currentTime)
        if tokenId in self.tokens:
            expiry = currentTime + self.timeToLive
            self.tokens[tokenId] = expiry
            self.expiryQueue.append((expiry, tokenId))

    def countUnexpiredTokens(self, currentTime: int) -> int:
        self._purge(currentTime)
        return len(self.tokens)

The _purge helper ensures all expired tokens are removed before any operation. The generate method adds tokens with their computed expiry, while renew first purges expired tokens and updates only unexpired ones. Counting simply returns the number of keys remaining in the dictionary.

Go Solution

package main

type tokenEntry struct {
	expiry  int
	tokenId string
}

type AuthenticationManager struct {
	timeToLive int
	tokens     map[string]int
	expiryQueue []tokenEntry
}

func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{
		timeToLive: timeToLive,
		tokens:     make(map[string]int),
		expiryQueue: []tokenEntry{},
	}
}

func (this *AuthenticationManager) purge(currentTime int) {
	i := 0
	for i < len(this.expiryQueue) {
		entry := this.expiryQueue[i]
		if entry.expiry > currentTime {
			break
		}
		if this.tokens[entry.tokenId] == entry.expiry {
			delete(this.tokens, entry.tokenId)
		}
		i++
	}
	this.expiryQueue = this.expiryQueue[i:]
}

func (this *AuthenticationManager) Generate(tokenId string, currentTime int) {
	expiry := currentTime + this.timeToLive
	this.tokens[tokenId] = expiry
	this.expiryQueue = append(this.expiryQueue, tokenEntry{expiry, tokenId})
}

func (this *AuthenticationManager) Renew(tokenId string, currentTime int) {
	this.purge(currentTime)
	if _, exists := this.tokens[tokenId]; exists {
		expiry := currentTime + this.timeToLive
		this.tokens[tokenId] = expiry
		this.expiryQueue = append(this.expiryQueue, tokenEntry{expiry, tokenId})
	}
}

func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	this.purge(currentTime)
	return len(this.tokens)
}

In Go, the main difference is using slices to simulate the queue and structs for token entries. Deleting expired tokens is handled by slicing the queue, and map lookup provides O(1) token access.

Worked Examples

Operation State of tokens State of queue Output
Generate("aaa", 2) {"aaa":7} [(7,"aaa")] -
CountUnexpiredTokens(6) {"aaa":7} [(7,"aaa")] 1
Generate("bbb", 7) {"aaa":7,"bbb":12} [(7,"aaa"),(12,"bbb")] -
Renew("aaa", 8) {"bbb":12} [(12,"bbb")] -
Renew("bbb", 10) {"bbb":15} [(12,"bbb"),(15,"bbb")] -
CountUnexpiredTokens(15) {} [] 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each token is added and removed from the queue at most once; each operation is O(1) amortized
Space O(n) We store all tokens in a map and queue, each token stored at most twice

Because currentTime is strictly increasing, purging expired tokens is amortized O(1) per operation.

Test Cases

# Basic example
am = AuthenticationManager(5)
am.renew("aaa", 1)
am.generate("aaa", 2)
assert am.countUnexpiredTokens(6) == 1
am.generate("bbb", 7)
am.renew("aaa", 8)
am.renew("bbb", 10)
assert am.countUnexpiredTokens(15) == 0

# Edge cases
am = AuthenticationManager(3)
am.generate("x", 1)
am.generate("y", 2)
am.renew("x", 3) # renew unexpired
assert am.countUnexpiredTokens(4) == 2
am.renew("y", 5) # renew expired
assert am.countUnexpiredTokens(5) == 1

# Single token generated and counted immediately
am = AuthenticationManager(10)
am.generate("token", 100)
assert am.countUnexpiredTokens(100) == 1
assert am.countUnexpiredTokens(110) == 0
Test Why
Provided example Valid