Retained Probe Directives
Indices of each integer's last occurrence in an array, in increasing order
A space mission stores probe directives in the order they were received. The array probe_codes contains the signed integer identifier of the probe targeted by each directive.
Before transmission, mission control discards any directive that has a later directive targeting the same probe. Thus, only the last directive for each distinct probe identifier is retained.
Return the zero-based indices of all retained directives, in increasing order. Return an empty list if there are no directives.
Examples
Example 1
Input: probe_codes = [12,7,12,9,7] Output: [2,3,4]
Probe 12 appears at indices 0 and 2, so its directive at index 0 is discarded. Probe 7 appears at indices 1 and 4, so its directive at index 1 is discarded. The directive for probe 9 is retained because that probe appears only once.
Example 2
Input: probe_codes = [-2,-2,-2] Output: [2]
All three directives target probe -2. Only the final directive is retained.
Example 3
Input: probe_codes = [] Output: []
There are no directives, so there are no indices to retain.
Constraints
- 0 <= probe_codes.length <= 8000
- -10^9 <= probe_codes[i] <= 10^9
The required index ordering makes the answer unique. An optimal solution takes O(n) expected time and O(d) auxiliary space, excluding the returned list, where d is the number of distinct probe identifiers.
Hints
Show hint 1Hint 1
When examining a directive, you only need to know whether its probe occurs later.
Show hint 2Hint 2
Scan from right to left and store the probe identifiers you have already encountered.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the retained probe identifiers in transmission order instead of their indices?
- How would you retain the last two directives for each probe instead of only the last one?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem