Archived Lift Itineraries
Count distinct array subsequences of length ≥2 per prefix obeying directed edges
A ski resort has an archive of station visits, listed chronologically in visits. Each integer is a station ID.
The resort also provides directed transfer rules in transfers. A rule [a, b] means that an itinerary may visit station b immediately after station a. The reverse transfer is not permitted unless it is listed separately.
An archived itinerary is a sequence of at least two station IDs that satisfies both conditions:
- It can be obtained by selecting visits at strictly increasing indices from the archive. Selected visits do not have to be consecutive.
- Every consecutive pair of station IDs in the selected sequence is a listed transfer rule.
Two itineraries are considered identical when their sequences of station IDs are identical, even if they use different archive indices. Repeated station IDs are permitted. In particular, consecutive equal IDs require a rule [a, a].
Return an array answer of the same length as visits. For each index i, answer[i] must be the number of distinct archived itineraries obtainable from visits[0:i+1], modulo 1,000,000,007.
Station IDs appearing in transfer rules need not appear in the archive. If visits is empty, return an empty array.
Examples
Example 1
Input: visits = [4,7,4,7], transfers = [[4,7],[7,4]] Output: [0,1,3,5]
The first visit cannot form an itinerary. After the second visit, the sequence [4, 7] is available. The third visit also makes [7, 4] and [4, 7, 4] available. At the last visit, using the later occurrence of 7 to form [4, 7] does not create a new itinerary, but [7, 4, 7] and [4, 7, 4, 7] are new.
Example 2
Input: visits = [5,5,5,5], transfers = [[5,5]] Output: [0,1,2,3]
The self-transfer permits repeated visits to station 5. There is only one distinct itinerary of each available length: choosing different occurrences for the same sequence does not create additional itineraries.
Example 3
Input: visits = [2,9,2,9], transfers = [[2,8]] Output: [0,0,0,0]
Although stations 2 and 9 both appear in the archive, the only permitted transfer leads from 2 to station 8. Since station 8 never appears, no archived itinerary can be formed.
Constraints
- 0 <= visits.length <= 100000
- 0 <= transfers.length <= 60000
- -1000000000 <= each station ID <= 1000000000
- Each element of transfers contains exactly two station IDs.
- No directed transfer rule appears more than once.
- For each station a, at most three rules have a as their first element.
- Self-transfer rules are allowed.
The intended solution takes O(visits.length + transfers.length) time because each visit propagates a change through at most three outgoing rules. Its auxiliary space is O(U + transfers.length), where U is the number of distinct station IDs in the input, excluding the returned array. All counting is performed modulo 1,000,000,007.
Hints
Show hint 1Hint 1
For each station, track the number of distinct nonempty valid sequences ending there. When that station appears again, extending every currently valid predecessor sequence describes all sequences ending there, not merely the new ones.
Show hint 2Hint 2
Maintain the sum of predecessor counts available to each station. When an ending count changes, propagate only its change along outgoing transfer rules. Exclude the distinct one-station sequences from each reported total.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you adapt the method to return counts only for itineraries whose final station belongs to a given set?
- Without the limit on outgoing transfer rules, express the running time in terms of station occurrence counts and outgoing degrees.
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