Minimum-Score Array Permutation
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Minimum-Score Array Permutation
You are given `nums`, a permutation of the integers from `0` through `n - 1`.
For another permutation `perm` of those same integers, define its score by the cyclic sum:
```text
score(perm) = |perm[0] - nums[perm[1]]|
+ |perm[1] - nums[perm[2]]|
+ ...
+ |perm[n - 1] - nums[perm[0]]|
```
Return a permutation `perm` with the smallest possible score. If several permutations have that score, return the lexicographically smallest one: at the first position where two permutations differ, the one containing the smaller value is lexicographically smaller.
### Examples
**Example 1**
```text
Input: nums = [2,0,1]
Output: [0,1,2]
```
The score is `|0 - 0| + |1 - 1| + |2 - 2| = 0`, which is minimal. Its cyclic rotations have the same score; `[0,1,2]` is the smallest rotation and the lexicographically smallest minimum-score permutation.
**Example 2**
```text
Input: nums = [0,1,2,3]
Output: [0,1,2,3]
```
The score is `1 + 1 + 1 + 3 = 6`. Any cyclic ordering visiting both zero and three must cover their distance in both directions around the cycle, so its score is at least six. This output attains that bound and is lexicographically smallest among all permutations.
### Constraints
- `2 <= n == nums.length <= 14`.
- `nums` is a permutation of `[0,1,2,...,n - 1]`.
### Clarifying Questions
- Is the final term included? Yes; it connects the last entry back to the first.
- Does a term subtract adjacent entries of `nums`? No; it subtracts `nums[perm[next]]` from the current value of `perm` exactly as written.
- Should the answer be the minimum score itself? No; return the permutation attaining it, with the stated tie rule.
- May the answer contain repeated values? No; it must use every integer from zero through `n - 1` exactly once.
### C++ Interface
```cpp
class Solution {
public:
vector<int> findPermutation(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Evaluate the indexed score formula correctly, including the last-to-first term.
- Return a valid permutation with globally minimum score.
- Resolve equal-score choices using the full lexicographic rule and justify resource use at `n = 14`.
```hint Use the cyclic structure
Rotating a permutation leaves its score unchanged. The lexicographically smallest optimal answer therefore starts with zero. From that fixed start, use a bitmask dynamic program for minimum completion cost, then reconstruct by trying the next unused value in increasing order.
```
Overview: Find the lexicographically smallest permutation minimizing a cyclic score with indexed array lookups. Covers wraparound terms, score ties and the original n <= 14 contract.