Find the Minimum Cost Array Permutation

Hard

#2798Time: 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.

Patterns

Dynamic Programming Bit Manipulation Bitmask

Data structures

Array

Prompt

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:

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:

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize min_score to a very large value and best_perm to an empty array.
Create a recursive function, say generatePermutations, that takes the current partial permutation and a set of used numbers as input.
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.
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.
Start the process by calling the recursive function with an empty initial permutation.
After all permutations have been explored, best_perm will hold the desired result.

Walkthrough

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.

1class Solution {2    private int minScore;3    private int[] bestPerm;4    private int[] nums;5    private int n;6 7    public int[] findPermutation(int[] nums) {8        this.n = nums.length;9        this.nums = nums;10        this.minScore = Integer.MAX_VALUE;11        this.bestPerm = new int[n];12 13        java.util.List<Integer> p = new java.util.ArrayList<>();14        boolean[] used = new boolean[n];15        generatePermutations(p, used);16        return bestPerm;17    }18 19    private void generatePermutations(java.util.List<Integer> p, boolean[] used) {20        if (p.size() == n) {21            int[] currentPerm = p.stream().mapToInt(i -> i).toArray();22            int currentScore = calculateScore(currentPerm);23 24            if (currentScore < minScore) {25                minScore = currentScore;26                System.arraycopy(currentPerm, 0, bestPerm, 0, n);27            } else if (currentScore == minScore) {28                if (isLexicographicallySmaller(currentPerm, bestPerm)) {29                    System.arraycopy(currentPerm, 0, bestPerm, 0, n);30                }31            }32            return;33        }34 35        for (int i = 0; i < n; i++) {36            if (!used[i]) {37                used[i] = true;38                p.add(i);39                generatePermutations(p, used);40                p.remove(p.size() - 1);41                used[i] = false;42            }43        }44    }45 46    private int calculateScore(int[] perm) {47        int score = 0;48        for (int i = 0; i < n - 1; i++) {49            score += Math.abs(perm[i] - nums[perm[i + 1]]);50        }51        score += Math.abs(perm[n - 1] - nums[perm[0]]);52        return score;53    }54 55    private boolean isLexicographicallySmaller(int[] p1, int[] p2) {56        for (int i = 0; i < n; i++) {57            if (p1[i] < p2[i]) {58                return true;59            }60            if (p1[i] > p2[i]) {61                return false;62            }63        }64        return false;65    }66}

Complexity

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.

Trade-offs

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.

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.

Algorithm

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]|.
Use dynamic programming with bitmasking. Define dp[mask][i] as the minimum cost of a path visiting nodes in mask and ending at i.
Initialize a dp table of size (1<<n) x n with infinity and a parent table to reconstruct paths.
Set base cases: dp[1<<i][i] = 0 for all i from 0 to n-1 (paths of length 1).
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).
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].
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]|.
Identify all permutations that achieve this minimum cost.
For each such optimal permutation (which forms a cycle), find its lexicographically smallest cyclic shift.
Return the lexicographically smallest among all these optimal candidates.

Walkthrough

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:

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.
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]|).
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.
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.

1class Solution {2    public int[] findPermutation(int[] nums) {3        int n = nums.length;4        int fullMask = (1 << n) - 1;5 6        int[][] dp = new int[1 << n][n];7        int[][] parent = new int[1 << n][n];8 9        for (int[] row : dp) {10            java.util.Arrays.fill(row, Integer.MAX_VALUE / 2);11        }12 13        for (int i = 0; i < n; i++) {14            dp[1 << i][i] = 0;15        }16 17        for (int mask = 1; mask < (1 << n); mask++) {18            for (int i = 0; i < n; i++) {19                if ((mask & (1 << i)) != 0) { // if i is in mask20                    int prevMask = mask ^ (1 << i);21                    if (prevMask == 0) continue;22                    for (int j = 0; j < n; j++) {23                        if ((prevMask & (1 << j)) != 0) { // if j is in prevMask24                            int cost = dp[prevMask][j] + Math.abs(j - nums[i]);25                            if (cost < dp[mask][i]) {26                                dp[mask][i] = cost;27                                parent[mask][i] = j;28                            }29                        }30                    }31                }32            }33        }34 35        int minScore = Integer.MAX_VALUE;36        int[] bestPerm = null;37 38        for (int i = 0; i < n; i++) { // i is the last element of the path39            int[] path = new int[n];40            int curr = i;41            int mask = fullMask;42            for (int k = n - 1; k >= 0; k--) {43                path[k] = curr;44                int prev = parent[mask][curr];45                mask ^= (1 << curr);46                curr = prev;47            }48            int startNode = path[0];49            50            int currentScore = dp[fullMask][i] + Math.abs(i - nums[startNode]);51 52            if (currentScore < minScore) {53                minScore = currentScore;54                bestPerm = getLexicographicallySmallest(path);55            } else if (currentScore == minScore) {56                int[] candidatePerm = getLexicographicallySmallest(path);57                if (isLexicographicallySmaller(candidatePerm, bestPerm)) {58                    bestPerm = candidatePerm;59                }60            }61        }62 63        return bestPerm;64    }65 66    private int[] getLexicographicallySmallest(int[] path) {67        int n = path.length;68        int[] bestShift = path.clone();69        int[] currentShift = path.clone();70 71        for (int i = 1; i < n; i++) {72            int[] nextShift = new int[n];73            for(int j=0; j<n; j++) {74                nextShift[j] = currentShift[(j + 1) % n];75            }76            currentShift = nextShift;77 78            if (isLexicographicallySmaller(currentShift, bestShift)) {79                bestShift = currentShift.clone();80            }81        }82        return bestShift;83    }84 85    private boolean isLexicographicallySmaller(int[] p1, int[] p2) {86        for (int i = 0; i < p1.length; i++) {87            if (p1[i] < p2[i]) return true;88            if (p1[i] > p2[i]) return false;89        }90        return false;91    }92}

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  Integer[][] f;4private5  int[] nums;6private7  int[] ans;8private9  int n;10public11  int[] findPermutation(int[] nums) {12    n = nums.length;13    ans = new int[n];14    this.nums = nums;15    f = new Integer[1 << n][n];16    g(1, 0, 0);17    return ans;18  }19private20  int dfs(int mask, int pre) {21    if (mask == (1 << n) - 1) {22      return Math.abs(pre - nums[0]);23    }24    if (f[mask][pre] != null) {25      return f[mask][pre];26    }27    int res = Integer.MAX_VALUE;28    for (int cur = 1; cur < n; ++cur) {29      if ((mask >> cur & 1) == 0) {30        res = Math.min(res,31                       Math.abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur));32      }33    }34    return f[mask][pre] = res;35  }36private37  void g(int mask, int pre, int k) {38    ans[k] = pre;39    if (mask == (1 << n) - 1) {40      return;41    }42    int res = dfs(mask, pre);43    for (int cur = 1; cur < n; ++cur) {44      if ((mask >> cur & 1) == 0) {45        if (Math.abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res) {46          g(mask | 1 << cur, cur, k + 1);47          break;48        }49      }50    }51  }52}

1class Solution {2public:3  vector<int> findPermutation(vector<int> &nums) {4    int n = nums.size();5    vector<int> ans;6    int f[1 << n][n];7    memset(f, -1, sizeof(f));8    function<int(int, int)> dfs = [&](int mask, int pre) {9      if (mask == (1 << n) - 1) {10        return abs(pre - nums[0]);11      }12      int *res = &f[mask][pre];13      if (*res != -1) {14        return *res;15      }16      *res = INT_MAX;17      for (int cur = 1; cur < n; ++cur) {18        if (mask >> cur & 1 ^ 1) {19          *res = min(*res, abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur));20        }21      }22      return *res;23    };24    function<void(int, int)> g = [&](int mask, int pre) {25      ans.push_back(pre);26      if (mask == (1 << n) - 1) {27        return;28      }29      int res = dfs(mask, pre);30      for (int cur = 1; cur < n; ++cur) {31        if (mask >> cur & 1 ^ 1) {32          if (abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res) {33            g(mask | 1 << cur, cur);34            break;35          }36        }37      }38    };39    g(1, 0);40    return ans;41  }42};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem