Shortest stretch of a trace that touches every service
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 distributed trace lists, in order, the name of the service that wrote each log entry. required lists distinct service names you are investigating.
Return the length of the shortest contiguous stretch of entries that contains every name in required at least once.
Return 0 if required is empty, and -1 if no stretch contains them all.
- 0 ≤ entries.length ≤ 200,000
- 0 ≤ required.length ≤ 50
- names in required are distinct
Examples
shortestSpan(["api", "db", "api", "cache", "db"], ["db", "cache"])returns2cache, db at the end.shortestSpan(["api", "api"], ["db"])returns-1db never appears.shortestSpan(["api"], [])returns0Nothing to cover.
Hints
Hint 1 of 2
Grow the window to the right until it covers every required name. Then it is a candidate; can it lose anything from the left and still cover them?
Hint 2 of 2
Keep a map from name to how many times it is in the window, and a count of required names that are present at least once. Shrink from the left while that count equals required.length.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
This window does the opposite of the budget problem. There, the window had to stay small enough; here it has to stay complete enough. So the loop grows until the window is valid, then shrinks while it stays valid, recording the length each time.
You cannot tell whether a window covers every name by scanning it, because that rebuilds the summary on every step. Keep a map of counts for the names you need, and a number, covered, of required names whose count is above zero. A name entering at zero raises covered; a name leaving at one lowers it.
Entries for services you are not investigating never change covered, so the reference skips them on the way in, and they leave the window freely on the way out.
The answer is a length, so update the best before letting the left entry go: the window is still complete at that moment, and the shrink that follows may break it.
function shortestSpan(entries, required) {
if (required.length === 0) return 0;
const need = new Set(required);
const inWindow = new Map();
let covered = 0, left = 0, best = Infinity;
for (let right = 0; right < entries.length; right++) {
const name = entries[right];
if (!need.has(name)) continue;
inWindow.set(name, (inWindow.get(name) ?? 0) + 1);
if (inWindow.get(name) === 1) covered++;
while (covered === need.size) {
best = Math.min(best, right - left + 1);
const out = entries[left++];
if (need.has(out)) {
inWindow.set(out, inWindow.get(out) - 1);
if (inWindow.get(out) === 0) covered--;
}
}
}
return best === Infinity ? -1 : best;
}Complexity. O(n + k) time for n entries and k required names; O(k) space for the counts.
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.