Find the Minimum Cost Array Permutation - Solution & Explanation
Problem Statement
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 <= 14numsis a permutation of[0, 1, 2, ..., n - 1].
Approach Overview
Problem Overview: You are given an array and must build a permutation that minimizes the total cost defined by the relationship between adjacent elements. The challenge is deciding the order of elements so that the cumulative transition cost stays as small as possible. Since permutations grow factorially, naive solutions quickly become infeasible.
Approach 1: Brute Force with Permutations (O(n! * n) time, O(n) space)
The most direct strategy is to generate every possible permutation of the array and compute the total cost for each ordering. Use a permutation generator (such as backtracking or Python's itertools.permutations) and iterate through the resulting order to accumulate adjacent costs. Track the minimum cost encountered. This approach is easy to implement and helps verify correctness for small inputs, but the factorial growth makes it impractical beyond small n. It mainly serves as a baseline to understand the search space.
Approach 2: Brute Force with State Tracking (O(n^2 * 2^n) time, O(n * 2^n) space)
A better strategy models the problem as visiting elements in different orders using bitmask states. Represent the set of used indices with a bitmask and store the minimum cost for reaching a state ending at a specific element. Transition by iterating over unused elements and updating the cost based on the previous element. This reduces redundant work compared to pure permutation generation and leverages bitmask state compression with dynamic programming. The idea is similar to a Traveling Salesman–style DP where the state is (mask, last).
Approach 3: Greedy Approach with Pairings (O(n log n) time, O(n) space)
If the cost function depends on relative differences between elements, sorting the array and pairing elements strategically can significantly reduce total transitions. Start by sorting the input and greedily placing elements so that adjacent differences stay small. The algorithm iterates through the sorted list and constructs a permutation that avoids large jumps between neighbors. This approach works well when the cost behaves monotonically with element distance, and it relies heavily on properties of the array values.
Approach 4: Greedy with Lexicographical Construction (O(n log n) time, O(n) space)
This variant builds the permutation incrementally while maintaining the smallest achievable cost prefix. Use sorted candidates and pick the next element that preserves the minimal cost pattern while keeping the permutation lexicographically valid. The algorithm repeatedly selects the best remaining element using comparisons against the last chosen value. Although greedy decisions guide the process, careful ordering ensures the global cost remains minimal.
Recommended for interviews: Start by describing the permutation brute force solution to show understanding of the search space. Then move to the bitmask dynamic programming formulation, which reduces repeated computation and demonstrates strong problem‑solving ability. Interviewers usually expect recognition of the (mask, last) DP state and its O(n^2 * 2^n) complexity, which is the scalable solution for moderate input sizes.
Approach 1: Brute Force with Permutations
This approach involves generating all possible permutations of the array [0, 1, 2, ..., n - 1] and calculating the score for each permutation according to the formula given. The goal is to find the permutation with the minimum score. In case of ties in scores, the lexicographically smallest permutation is chosen. This can be efficiently brute-forced given constraints, since the maximum permutation count is 14! = 87,178,291,200, which is feasible for this problem.
In this solution, we use the itertools.permutations to generate all permutations. For each permutation, we calculate its score according to the formula and keep track of the permutation with the lowest score. If there are multiple permutations with the same score, we select the lexicographically smallest one.
Code
Python
Complexity
Time Complexity: O(n! * n), as we are generating n! permutations, each requiring O(n) time to compute the score.
Space Complexity: O(n), used for storing permutations and current best solution.
Approach 2: Greedy Approach with Pairings
This smarter approach notices the required pattern for minimum permutation is closely tight to pair matching nums with their natural order, taking care to ensure differences maintain minimization. Instead of generating all permutations, directly using this idea forms a good basis to achieve both minimized score and lexicographic arrangement.
Here, we pair each element with its index and sort by the values in nums. The resulting index order forms the permutation ensuring pairing close elements from nums to their indices minimizes the sum of differences.
Code
Python
Complexity
Time Complexity: O(n log n), due to the sorting of indexed numbers.
Space Complexity: O(n), for storing pairs of indexes and numbers.
Approach 3: Brute Force Approach
This approach involves generating all possible permutations of the given array and calculating their scores. Given the constraints (n <= 14), this approach is feasible. We will evaluate the score for each permutation and return the one with the minimum score. If multiple permutations have the same score, we choose the lexicographically smallest one.
The Python itertools library provides a permutations function to generate all possible permutations of a list. For each permutation, we calculate the score using the given formula and update the minimum score and the best permutation found if this score is lower than the previously found scores. We also check for lexicographically smaller permutations in case of a tie in score.
Code
Python
JavaScript
Complexity
Time Complexity: O(n! * n), as we are generating all permutations (which are n!) and calculating the score in O(n) time for each.
Space Complexity: O(n!), for storing all permutations if needed (though here we evaluate them one by one).
Approach 4: Greedy and Lexicographical Approach
This approach leverages the properties of permutations and lexicographical order to select elements iteratively, minimizing the score contribution step-by-step while ensuring lexicographical ordering.
We use C++ standard library for permutations. By starting with the natural order, we go through all permutations using next_permutation, which generates permutations in lexicographical order. Each permutation is evaluated for its score, and we track a minimum score. This efficiently finds a minimal score permutation that is also lexicographically smaller among equal scores.
Complexity
Time Complexity: O(n! * n), which reflects iterating through permutations and calculating scores.
Space Complexity: O(n), used for storing the current permutation array.
Approach 5: Memoization Search
We notice that for any permutation perm, if we cyclically shift it to the left any number of times, the score of the permutation remains the same. Since the problem requires returning the lexicographically smallest permutation, we can determine that the first element of the permutation must be 0.
Also, since the data range of the problem does not exceed 14, we can consider using the method of state compression to represent the set of numbers selected in the current permutation. We use a binary number mask of length n to represent the set of numbers selected in the current permutation, where the i-th bit of mask is 1 indicates that the number i has been selected, and 0 indicates that the number i has not been selected yet.
We design a function dfs(mask, pre), which represents the minimum score of the permutation obtained when the set of numbers selected in the current permutation is mask and the last selected number is pre. Initially, we add the number 0 to the permutation.
The calculation process of the function dfs(mask, pre) is as follows:
- If the number of
1s in the binary representation ofmaskisn, that is,mask = 2^n - 1, it means that all numbers have been selected, then return|pre - nums[0]|; - Otherwise, we enumerate the next selected number
cur. If the numbercurhas not been selected yet, then we can add the numbercurto the permutation. At this time, the score of the permutation is|pre - nums[cur]| + dfs(mask \, | \, 1 << cur, cur). We need to take the minimum score among allcur.
Finally, we use a function g(mask, pre) to construct the permutation that gets the minimum score. We first add the number pre to the permutation, and then enumerate the next selected number cur. If the number cur has not been selected yet, and it satisfies that the value of |pre - nums[cur]| + dfs(mask \, | \, 1 << cur, cur) is equal to dfs(mask, pre), then we can add the number cur to the permutation.
The time complexity is (n^2 times 2^n), and the space complexity is O(n times 2^n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force with Permutations | Time Complexity: O(n! * n), as we are generating n! permutations, each requiring O(n) time to compute the score. Space Complexity: O(n), used for storing permutations and current best solution. |
| Greedy Approach with Pairings | Time Complexity: O(n log n), due to the sorting of indexed numbers. Space Complexity: O(n), for storing pairs of indexes and numbers. |
| Brute Force Approach | Time Complexity: O(n! * n), as we are generating all permutations (which are n!) and calculating the score in O(n) time for each. Space Complexity: O(n!), for storing all permutations if needed (though here we evaluate them one by one). |
| Greedy and Lexicographical Approach | Time Complexity: O(n! * n), which reflects iterating through permutations and calculating scores. Space Complexity: O(n), used for storing the current permutation array. |
| Memoization Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Permutations | O(n! * n) | O(n) | Very small arrays or verifying correctness |
| Brute Force with Bitmask DP | O(n^2 * 2^n) | O(n * 2^n) | General case when exploring permutations efficiently |
| Greedy Pairing Strategy | O(n log n) | O(n) | When cost correlates with value differences |
| Greedy Lexicographical Construction | O(n log n) | O(n) | When maintaining minimal prefix cost while building permutation |
Video Solution
Find the Minimum Cost Array Permutation | Tree Diagram | Backtrack | Leetcode 3149 |codestorywithMIK • codestorywithMIK • 7,981 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Find the Minimum Cost Array Permutation easy or hard?
Find the Minimum Cost Array Permutation Python or Java solution
How to solve Find the Minimum Cost Array Permutation in O(n log n)?
What is the best approach for Find the Minimum Cost Array Permutation?
Is Find the Minimum Cost Array Permutation asked at Google/Amazon/Meta?
What data structure is used in Find the Minimum Cost Array Permutation?
What is the time complexity of Find the Minimum Cost Array Permutation?
Ready to solve this problem?
Practice Find the Minimum Cost Array Permutation with our built-in code editor and test cases.
Practice on FleetCode