Recipe Tasting Routes
Lexicographically ordered index permutations with unequal adjacent array values
A recipe app is planning a guided tasting of ingredient samples. Each sample has a flavor-family code, given in the array flavors. Samples with the same code belong to the same family, but they are still separate samples identified by their indices.
A tasting route is a list of sample indices that:
- Includes every index exactly once.
- Never places two samples from the same flavor family next to each other.
Return every valid tasting route in lexicographically increasing order. Compare two routes by their first differing index; the route with the smaller index comes first.
If no valid route exists, return an empty list. If there are no samples, return a list containing one empty route.
Examples
Example 1
Input: flavors = [4,9,4] Output: [[0,1,2],[2,1,0]]
Samples 0 and 2 belong to the same family. They must be separated by sample 1, so a valid route must put sample 1 in the middle.
Example 2
Input: flavors = [-2,0,7] Output: [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]
Every sample has a different flavor-family code, so every ordering of the three sample indices is valid.
Example 3
Input: flavors = [5,5] Output: []
Both samples belong to the same family. Any ordering puts them next to each other, so no route is valid.
Constraints
- 0 <= flavors.length <= 8
- -10^9 <= flavors[i] <= 10^9
- Sample indices are zero-based.
- Equal flavor-family codes do not make samples interchangeable: routes are distinguished by their indices.
The output can contain up to n! routes. The reference solution uses O(n) auxiliary space excluding the output, and O(n * n!) time in the worst case.
Hints
Show hint 1Hint 1
Build a route one index at a time, keeping track of which indices have already been used.
Show hint 2Hint 2
Before adding an unused index, compare its flavor family with that of the last sample in the current route. Try indices in increasing order.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the implementation to return only the number of valid routes without storing them?
- How would you adapt the rule so that samples from the same family must have at least two other samples between them?
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