Latest K Unique Requests

Frequency: Reported

Given an array of n request IDs as strings and an integer k, return the k most recent distinct requests after every request has been received. Order the result from most recent to least recent.

Example

text

requests = ["item1", "item2", "item3", "item1", "item3"]
k = 3

Scan from right to left. Collect "item3", then "item1", skip the earlier "item3", and collect "item2". Return:

text

["item3", "item1", "item2"]

Function

text

getLatestKRequests(string requests[n], int k) -> string[k]

Constraints

text

1 < k <= n < 10^5
requests[i] contains lowercase letters and digits only: [a-z0-9]

Submitted implementation

python

def getLatestKRequests(requests, K):
    seen = set()
    result = []
    n = len(requests)

    for i in range(n - 1, -1, -1):
        request = requests[i]
        if request not in seen:
            seen.add(request)
            result.append(request)
            if len(result) == K:
                break

    return result