EF-T02: Earliest Longest Unique Event Range

Exercise contract#

Given an array of event ID strings, return [start, end), the earliest half-open index range of maximum length containing no repeated event ID. If several maximum-length ranges exist, return the one with the smallest start index. Empty input returns [0, 0]. Event IDs are compared exactly and the input is not modified.

Constraints

• 0 <= number of event IDs <= 200,000.
• Each event ID is a non-null string with length at most 100.
• Equality is exact string equality; no normalization is performed.
• The answer uses zero-based half-open indices [start, end).
• When maximum lengths tie, retain the earlier start index.

Examples

["a", "b", "a", "c", "d", "b"]

[1, 5]The range [1, 5) contains ["b", "a", "c", "d"]. The later range [2, 6) has the same length, so the earlier start wins.

["x", "x", "x"]

[0, 1]Every valid maximum has length one, and [0, 1) is earliest.

Derive the approach#

Baseline: Start at every index and extend right until the first duplicate, retaining the earliest longest range. This checks the same suffixes repeatedly and can take O(n^2) time.

1. The valid answer is contiguous, so represent the current candidate with left and right boundaries.
2. When event[right] last appeared inside the current window, every range starting at or before that prior position would repeat it.
3. Move left to one position after that occurrence; never move left backward when the last occurrence is outside the window.
4. Record the current index as the event's latest position.
5. Update the best range only when the current length is strictly larger; left never decreases, so the first maximum remains the earliest.

Time

O(n) expected time for n events.

Space

O(u) auxiliary space for u distinct event IDs.

Assumptions

Map lookup/update is expected O(1), string equality and hashing costs are treated as bounded by the declared event-ID length, and the input is not copied or modified.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def earliest_longest_unique_range(events):
    last_seen = {}
    left = 0
    best_start = 0
    best_end = 0

    for right, event in enumerate(events):
        previous = last_seen.get(event)
        if previous is not None and previous >= left:
            left = previous + 1
        last_seen[event] = right
        if right + 1 - left > best_end - best_start:
            best_start = left
            best_end = right + 1

    return [best_start, best_end]

static int[] earliestLongestUniqueRange(List<String> events) {
    Map<String, Integer> lastSeen = new HashMap<>();
    int left = 0;
    int bestStart = 0;
    int bestEnd = 0;

    for (int right = 0; right < events.size(); right++) {
        String event = events.get(right);
        Integer previous = lastSeen.put(event, right);
        if (previous != null && previous >= left) {
            left = previous + 1;
        }
        if (right + 1 - left > bestEnd - bestStart) {
            bestStart = left;
            bestEnd = right + 1;
        }
    }
    return new int[] {bestStart, bestEnd};
}

Deterministic test plan#

Transfer and follow-ups#

• Return the actual event slice as well as the range, accounting for O(length) output copying.
• Allow at most k occurrences of each event ID and replace last-seen position with per-event counts inside the window.

State why the left boundary moves monotonically and why strict best-length updates preserve the earliest tie.

Authorship and review#

Original Engineering Foundry prompt, examples, explanations, and verification programs using standard algorithmic techniques. This is not attributed to an employer and is not evidence of interview frequency.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09