HardAlgorithms & Data StructuresBuild

Extract the Smallest Matching Log Window

You're triaging a production incident. The logs from one node contain a sequence of event types, and you need to find the smallest contiguous window of log entries that contains every event type from a required set. Imp...

Start problem Browse all problems

What you will practice

PythonArrays & StringsHash Maps & SetsTwo PointersSliding WindowPerformance

Requirements

Return a `(start, end)` tuple where `end` is exclusive — `events[start:end]` is the matching window.
If multiple windows have the same minimum length, return the leftmost one.
If no window contains every required event type, return `(0, 0)`.
If `required` is empty, return `(0, 0)` — an empty requirement is trivially satisfied by an empty window.
If `required` contains duplicates (e.g. `['A', 'A', 'B']`), the window must contain at least that many occurrences of each event.
Run in O(n) over the events list — the perf test will TLE an O(n²) solution.

Starter files

main.pyEditable starter

What the judge checks

Runs in the python environment with the python-pytest runner.
Uses a 8000ms judge budget.
Behavior rules include: Correct On Simple Cases, Returns Empty Range When No Window, Handles Duplicate Required Events, Performance On Large Input Under Limit.

Constraints

Do not modify the inputs.
Use only the standard library. No NumPy, no external packages.
The perf test runs on `len(events)` up to 200,000 — any algorithm worse than O(n) on the inputs and requirements will exceed the time limit.

Example behavior

Input

events = ['A', 'C', 'B', 'A', 'D', 'B', 'A']
required = ['A', 'B']

Output

(2, 4)

events[2:4] = ['B', 'A'] — smallest window containing both required types.

Input

events = ['X', 'X', 'X']
required = ['Y']

Output

(0, 0)

No 'Y' anywhere in the log.

Follow-up

How would you change the algorithm if the events were arriving as a stream and you couldn't hold all of them in memory at once?