In Providence telemetry processing, an existing implementation checks every pair of event IDs to find the first duplicate, which is too slow for large inputs. Write an optimized algorithm that returns the index of the first event whose value has appeared earlier in the list.
Implement a function first_duplicate_event(events) where:
events, a list of integers representing event IDs in arrival order-1 if no duplicate existsA duplicate is any value that has already appeared earlier. “First duplicate” means the duplicate occurrence with the smallest index.
Example 1
Input: events = [4, 2, 7, 2, 5, 7]
Output: 3
Explanation: 2 first repeats at index 3. Although 7 also repeats, its duplicate occurs later at index 5.
Example 2
Input: events = [9, 1, 3, 4]
Output: -1
Explanation: No event ID appears more than once.
1 <= len(events) <= 10^5-10^9 <= events[i] <= 10^9O(n^2) approachevents = [4, 2, 7, 2, 5, 7]Output3WhyThe value `2` appears first at index `1` and repeats at index `3`, which is the earliest duplicate occurrence.events = [9, 1, 3, 4]Output-1WhyAll values are distinct, so there is no duplicate occurrence.events = [8, 8, 2, 3]Output1WhyThe second `8` at index `1` is immediately the first duplicate occurrence.1 <= len(events) <= 10^5-10^9 <= events[i] <= 10^9Input contains integers onlyReturn the index of the earliest duplicate occurrence, or -1 if none existsdef first_duplicate_event(events):
