First request that was retried
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A gateway logs the ID of each request it receives, in order. A client that retries sends the same ID again.
Return the ID whose second appearance comes earliest in the log, or null if no ID appears twice.
- 0 ≤ ids.length ≤ 200,000
- IDs are non-empty strings
Examples
firstRetry(["a1", "b7", "c3", "b7", "a1"])returns"b7"b7 repeats at position 3, before a1 repeats at 4.firstRetry(["x", "y", "z"])returnsnullfirstRetry(["q", "q"])returns"q"
Hints
Hint 1 of 2
Walk the log once. For each ID, you only need to know whether it has been seen before.
Hint 2 of 2
A Set answers that in one step. The first ID you find already in the set is the answer.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
The answer is decided at the moment of the second appearance, so the earliest second appearance is simply the first time, walking forward, that you meet an ID you have already seen.
A Set of seen IDs makes that check one step. Searching the earlier part of the list with indexOf gives the same answer but costs a scan per ID, which is quadratic on a log with no repeats until the end.
Counting first and then returning the first ID with a count above one answers a different question: whose first appearance is earliest. In a1, b7, c3, b7, a1 that is a1, but b7 was retried first.
function firstRetry(ids) {
const seen = new Set();
for (const id of ids) {
if (seen.has(id)) return id;
seen.add(id);
}
return null;
}Complexity. O(n) time and O(n) space for the set.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.