# Find the Minimum Cost Array Permutation
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-minimum-cost-array-permutation)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-cost-array-permutation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
You are given an array `nums` which is a permutation of `[0, 1, 2, ..., n - 1]`. The **score** of any permutation of `[0, 1, 2, ..., n - 1]` named `perm` is defined as:

`score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|`

Return the permutation `perm` which has the **minimum** possible score. If _multiple_ permutations exist with this score, return the one that is lexicographically smallest among them.

**Example 1:**

**Input:** nums = \[1,0,2\]

**Output:** \[0,1,2\]

**Explanation:**

**![](https://assets.glich.co/dsa/find-the-minimum-cost-array-permutation/image0.gif)**

The lexicographically smallest permutation with minimum cost is `[0,1,2]`. The cost of this permutation is `|0 - 0| + |1 - 2| + |2 - 1| = 2`.

**Example 2:**

**Input:** nums = \[0,2,1\]

**Output:** \[0,2,1\]

**Explanation:**

**![](https://assets.glich.co/dsa/find-the-minimum-cost-array-permutation/image1.gif)**

The lexicographically smallest permutation with minimum cost is `[0,2,1]`. The cost of this permutation is `|0 - 1| + |2 - 2| + |1 - 0| = 2`.

**Constraints:**

* `2 <= n == nums.length <= 14`
* `nums` is a permutation of `[0, 1, 2, ..., n - 1]`.

# Approaches
## Brute Force by Generating All Permutations
This approach involves generating every single possible permutation of the numbers `[0, 1, ..., n-1]`. For each permutation, we calculate its score based on the provided formula. We maintain a variable to keep track of the minimum score found so far and the permutation that produced it. If we find a permutation with a score equal to the current minimum, we choose the one that is lexicographically smaller. This exhaustive search guarantees finding the correct answer but is computationally very expensive.
**Time:** O(n! * n) - There are `n!` permutations to generate. For each permutation, calculating the score takes O(n) time. · **Space:** O(n) - The space is dominated by the recursion depth and the storage for the current and best permutations.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find the correct answer as it checks every possibility.
**Cons:** Extremely high time complexity, making it impractical for `n` greater than 10 or 11.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The brute-force method systematically explores the entire search space of `n!` permutations. We can implement this using a recursive backtracking algorithm.

We define a helper function that builds a permutation step by step. This function would keep track of the numbers already included in the current partial permutation to ensure no duplicates are used.

Once a full permutation of length `n` is constructed, we compute its score. The score is the sum of absolute differences as defined in the problem: `Σ|perm[i] - nums[perm[i+1]]|` (with the index wrapping around at the end).

This score is then compared against the minimum score found so far. If it's better, we update our best-found permutation. If it's the same, we perform a lexicographical comparison to decide if we should update. Due to the `n!` growth, this method is only feasible for very small values of `n`.

```java
class Solution {
    private int minScore;
    private int[] bestPerm;
    private int[] nums;
    private int n;

    public int[] findPermutation(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        this.minScore = Integer.MAX_VALUE;
        this.bestPerm = new int[n];

        java.util.List<Integer> p = new java.util.ArrayList<>();
        boolean[] used = new boolean[n];
        generatePermutations(p, used);
        return bestPerm;
    }

    private void generatePermutations(java.util.List<Integer> p, boolean[] used) {
        if (p.size() == n) {
            int[] currentPerm = p.stream().mapToInt(i -> i).toArray();
            int currentScore = calculateScore(currentPerm);

            if (currentScore < minScore) {
                minScore = currentScore;
                System.arraycopy(currentPerm, 0, bestPerm, 0, n);
            } else if (currentScore == minScore) {
                if (isLexicographicallySmaller(currentPerm, bestPerm)) {
                    System.arraycopy(currentPerm, 0, bestPerm, 0, n);
                }
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                p.add(i);
                generatePermutations(p, used);
                p.remove(p.size() - 1);
                used[i] = false;
            }
        }
    }

    private int calculateScore(int[] perm) {
        int score = 0;
        for (int i = 0; i < n - 1; i++) {
            score += Math.abs(perm[i] - nums[perm[i + 1]]);
        }
        score += Math.abs(perm[n - 1] - nums[perm[0]]);
        return score;
    }

    private boolean isLexicographicallySmaller(int[] p1, int[] p2) {
        for (int i = 0; i < n; i++) {
            if (p1[i] < p2[i]) {
                return true;
            }
            if (p1[i] > p2[i]) {
                return false;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Initialize `min_score` to a very large value and `best_perm` to an empty array.
2. Create a recursive function, say `generatePermutations`, that takes the current partial permutation and a set of used numbers as input.
3. The base case for the recursion is when the partial permutation's length equals `n`.
   a. When a full permutation is formed, calculate its score using the formula: `score = |perm[0] - nums[perm[1]]| + ... + |perm[n-1] - nums[perm[0]]|`.
   b. If the calculated `score` is less than `min_score`, update `min_score` to this new score and `best_perm` to the current permutation.
   c. If the `score` is equal to `min_score`, compare the current permutation with `best_perm` lexicographically. If the current one is smaller, update `best_perm`.
4. The recursive step involves iterating through all numbers from `0` to `n-1`. If a number has not been used, add it to the partial permutation and recurse. Backtrack by removing the number and marking it as unused after the recursive call returns.
5. Start the process by calling the recursive function with an empty initial permutation.
6. After all permutations have been explored, `best_perm` will hold the desired result.

## Dynamic Programming with Bitmask (TSP)
This problem can be framed as the classic Traveling Salesperson Problem (TSP). The numbers `0, 1, ..., n-1` act as cities (nodes). The cost to travel from a city `u` to a city `v` is given by `|u - nums[v]|`. We are looking for a tour (a permutation) that visits every city exactly once and returns to the start, minimizing the total travel cost. Given the constraint `n <= 14`, this can be efficiently solved using dynamic programming with bitmasking.
**Time:** O(n^2 * 2^n) - The main loop iterates through `2^n` masks, `n` end-nodes, and `n` predecessor nodes. · **Space:** O(n * 2^n) - To store the `dp` and `parent` tables, each of size `(1 << n) x n`.
**Pros:** Provides an optimal and efficient solution for the given constraints.; It's a standard and powerful technique for problems like TSP on a small number of nodes.
**Cons:** Considerably more complex to implement compared to brute force.; Requires a good understanding of dynamic programming, bitmasking, and the TSP.; Uses significant memory, `O(n * 2^n)`, which can be large.
### Explanation
The DP state `dp[mask][i]` will store the minimum cost of a path that visits the set of nodes represented by the bitmask `mask` and ends at node `i`. A `parent[mask][i]` table is also used to backtrack and reconstruct the path itself.

**Algorithm Steps:**

1.  **Initialization**: Create `dp[1<<n][n]` and `parent[1<<n][n]` tables. Initialize `dp` with a large value. For each node `i`, the cost of a path just visiting `i` is 0, so `dp[1 << i][i] = 0`.

2.  **DP Calculation**: We iterate through all masks, from those with 2 set bits up to `n`. For each `mask`, we iterate through each node `i` it contains. We then look at all possible predecessors `j` (from `mask` excluding `i`) and update `dp[mask][i]` if we find a cheaper path through `j`.
    The transition is: `dp[mask][i] = min(dp[mask][i], dp[mask ^ (1<<i)][j] + |j - nums[i]|)`.

3.  **Finding Minimum Cost and Permutation**: Once the `dp` table is populated, `dp[(1<<n)-1][i]` gives the cost of the cheapest Hamiltonian path ending at `i`. To complete the cycle, we add the cost of the edge from the end node `i` back to the start node of that path. The start node is found by backtracking using the `parent` table. We do this for all possible end nodes `i` to find the global minimum cycle cost.

4.  **Lexicographical Requirement**: After finding the minimum possible score, we must find the lexicographically smallest permutation that achieves it. We iterate through all cycles that yield this minimum score. For each such cycle (represented as a permutation), we find its lexicographically smallest cyclic shift. The smallest among these shifts is our final answer.

```java
class Solution {
    public int[] findPermutation(int[] nums) {
        int n = nums.length;
        int fullMask = (1 << n) - 1;

        int[][] dp = new int[1 << n][n];
        int[][] parent = new int[1 << n][n];

        for (int[] row : dp) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE / 2);
        }

        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = 0;
        }

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) { // if i is in mask
                    int prevMask = mask ^ (1 << i);
                    if (prevMask == 0) continue;
                    for (int j = 0; j < n; j++) {
                        if ((prevMask & (1 << j)) != 0) { // if j is in prevMask
                            int cost = dp[prevMask][j] + Math.abs(j - nums[i]);
                            if (cost < dp[mask][i]) {
                                dp[mask][i] = cost;
                                parent[mask][i] = j;
                            }
                        }
                    }
                }
            }
        }

        int minScore = Integer.MAX_VALUE;
        int[] bestPerm = null;

        for (int i = 0; i < n; i++) { // i is the last element of the path
            int[] path = new int[n];
            int curr = i;
            int mask = fullMask;
            for (int k = n - 1; k >= 0; k--) {
                path[k] = curr;
                int prev = parent[mask][curr];
                mask ^= (1 << curr);
                curr = prev;
            }
            int startNode = path[0];
            
            int currentScore = dp[fullMask][i] + Math.abs(i - nums[startNode]);

            if (currentScore < minScore) {
                minScore = currentScore;
                bestPerm = getLexicographicallySmallest(path);
            } else if (currentScore == minScore) {
                int[] candidatePerm = getLexicographicallySmallest(path);
                if (isLexicographicallySmaller(candidatePerm, bestPerm)) {
                    bestPerm = candidatePerm;
                }
            }
        }

        return bestPerm;
    }

    private int[] getLexicographicallySmallest(int[] path) {
        int n = path.length;
        int[] bestShift = path.clone();
        int[] currentShift = path.clone();

        for (int i = 1; i < n; i++) {
            int[] nextShift = new int[n];
            for(int j=0; j<n; j++) {
                nextShift[j] = currentShift[(j + 1) % n];
            }
            currentShift = nextShift;

            if (isLexicographicallySmaller(currentShift, bestShift)) {
                bestShift = currentShift.clone();
            }
        }
        return bestShift;
    }

    private boolean isLexicographicallySmaller(int[] p1, int[] p2) {
        for (int i = 0; i < p1.length; i++) {
            if (p1[i] < p2[i]) return true;
            if (p1[i] > p2[i]) return false;
        }
        return false;
    }
}
```
### Algorithm
1. Model the problem as a Traveling Salesperson Problem (TSP) where nodes are `0..n-1` and edge cost from `u` to `v` is `|u - nums[v]|`.
2. Use dynamic programming with bitmasking. Define `dp[mask][i]` as the minimum cost of a path visiting nodes in `mask` and ending at `i`.
3. Initialize a `dp` table of size `(1<<n) x n` with infinity and a `parent` table to reconstruct paths.
4. Set base cases: `dp[1<<i][i] = 0` for all `i` from 0 to `n-1` (paths of length 1).
5. Iterate through `mask` from 1 to `(1<<n)-1`. For each `mask`, iterate through nodes `i` in the mask. Then iterate through nodes `j` in `mask` excluding `i` (`prev_mask`).
6. Update `dp[mask][i]` using the transition: `dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + |j - nums[i]|)`. Store `j` in `parent[mask][i]`.
7. After filling the DP table, find the overall minimum cycle cost. For each possible path end-node `i`, reconstruct the path using the `parent` table to find its start-node `s`. The cycle cost is `dp[(1<<n)-1][i] + |i - nums[s]|`.
8. Identify all permutations that achieve this minimum cost.
9. For each such optimal permutation (which forms a cycle), find its lexicographically smallest cyclic shift.
10. Return the lexicographically smallest among all these optimal candidates.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  int[] nums;
private
  int[] ans;
private
  int n;
public
  int[] findPermutation(int[] nums) {
    n = nums.length;
    ans = new int[n];
    this.nums = nums;
    f = new Integer[1 << n][n];
    g(1, 0, 0);
    return ans;
  }
private
  int dfs(int mask, int pre) {
    if (mask == (1 << n) - 1) {
      return Math.abs(pre - nums[0]);
    }
    if (f[mask][pre] != null) {
      return f[mask][pre];
    }
    int res = Integer.MAX_VALUE;
    for (int cur = 1; cur < n; ++cur) {
      if ((mask >> cur & 1) == 0) {
        res = Math.min(res,
                       Math.abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur));
      }
    }
    return f[mask][pre] = res;
  }
private
  void g(int mask, int pre, int k) {
    ans[k] = pre;
    if (mask == (1 << n) - 1) {
      return;
    }
    int res = dfs(mask, pre);
    for (int cur = 1; cur < n; ++cur) {
      if ((mask >> cur & 1) == 0) {
        if (Math.abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res) {
          g(mask | 1 << cur, cur, k + 1);
          break;
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findPermutation(vector<int> &nums) {
    int n = nums.size();
    vector<int> ans;
    int f[1 << n][n];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int mask, int pre) {
      if (mask == (1 << n) - 1) {
        return abs(pre - nums[0]);
      }
      int *res = &f[mask][pre];
      if (*res != -1) {
        return *res;
      }
      *res = INT_MAX;
      for (int cur = 1; cur < n; ++cur) {
        if (mask >> cur & 1 ^ 1) {
          *res = min(*res, abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur));
        }
      }
      return *res;
    };
    function<void(int, int)> g = [&](int mask, int pre) {
      ans.push_back(pre);
      if (mask == (1 << n) - 1) {
        return;
      }
      int res = dfs(mask, pre);
      for (int cur = 1; cur < n; ++cur) {
        if (mask >> cur & 1 ^ 1) {
          if (abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res) {
            g(mask | 1 << cur, cur);
            break;
          }
        }
      }
    };
    g(1, 0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]: @ cache def dfs(mask: int, pre: int) -> int: if mask == (1 << n) - 1: return abs(pre - nums[0]) res = inf for cur in range(1, n): if mask >> cur & 1 ^ 1: res = min(res, abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur)) return res def g(mask: int, pre: int): ans . append(pre) if mask == (1 << n) - 1: return res = dfs(mask, pre) for cur in range(1, n): if mask >> cur & 1 ^ 1: if abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res: g(mask | 1 << cur, cur) break n = len(nums) ans = [] g(1, 0) return ans

```