3149. Find the Minimum Cost Array Permutation

HardBit ManipulationArrayDynamic ProgrammingBitmask

Problem Description

You are given an array nums which is a permutation of [0, 1, 2, ..., n - 1]. Your task is to find another permutation perm of the same set [0, 1, 2, ..., n - 1] that minimizes a specific score.

The score of any permutation perm is calculated as: score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|

In this formula:

Each term calculates the absolute difference between an element in perm at position i and an element in nums at position perm[i+1]
The calculation wraps around cyclically, so the last term uses perm[n-1] and nums[perm[0]]

The goal is to find the permutation perm that produces the minimum possible score. If multiple permutations have the same minimum score, you should return the lexicographically smallest one among them.

For example, if nums = [1, 0, 2], you need to find a permutation of [0, 1, 2] that, when used as indices and values according to the scoring formula, gives the smallest total sum of absolute differences. The permutation should start with 0 when possible for lexicographic ordering, and among all minimum-score permutations, choose the one that comes first in dictionary order.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The first key observation is that the score formula creates a cycle: we're essentially creating a circular chain where each element in perm points to the next one, and we sum up the differences between each element and what it points to in nums. Since this is a cycle, we can rotate any valid permutation and get the same score. For example, [0, 1, 2] and [1, 2, 0] would have the same score value.

Given that rotations preserve the score and we want the lexicographically smallest result, we can fix the first element as 0. This simplifies our problem significantly - we only need to find the optimal arrangement of the remaining elements [1, 2, ..., n-1].

The small constraint (n ≤ 14) immediately suggests that we can use bit manipulation and dynamic programming. With at most 14 elements, we have 2^14 = 16384 possible states, which is manageable.

We can think of building the permutation step by step. At each step, we need to decide which unvisited number to visit next. The challenge is that our current choice affects future costs - if we choose number cur after pre, we pay |pre - nums[cur]| now, but this also determines where we'll be when making the next choice.

This naturally leads to a state-based dynamic programming approach where:

We track which numbers we've already used (using a bitmask)
We track what the last number we chose was (since this affects the cost of the next choice)
We compute the minimum remaining cost from each state

Once we know the minimum costs, we can reconstruct the actual permutation by greedily choosing the next number that leads to the optimal total cost while maintaining lexicographic order (trying smaller numbers first).

Learn more about Dynamic Programming and Bitmask patterns.

Solution Implementation

1class Solution: 2 def findPermutation(self, nums: List[int]) -> List[int]: 3 """ 4 Find a permutation of indices [0, 1, ..., n-1] that minimizes the total 5 absolute difference when traversing the array in that order (forming a cycle). 6 7 Args: 8 nums: List of integers 9 10 Returns: 11 List of indices representing the optimal permutation 12 """ 13 14 @cache 15 def calculate_min_cost(visited_mask: int, last_index: int) -> int: 16 """ 17 Calculate minimum cost to visit all remaining nodes starting from last_index. 18 19 Args: 20 visited_mask: Bitmask representing visited indices (1 = visited) 21 last_index: The index of the last visited element 22 23 Returns: 24 Minimum cost to complete the tour 25 """ 26 # If all nodes are visited, return cost to go back to start 27 if visited_mask == (1 << n) - 1: 28 return abs(nums[last_index] - nums[0]) 29 30 min_cost = float('inf') 31 32 # Try visiting each unvisited node 33 for next_index in range(1, n): 34 # Check if next_index is not visited (bit is 0) 35 if (visited_mask >> next_index) & 1 == 0: 36 # Calculate cost: edge cost + remaining tour cost 37 cost = abs(nums[last_index] - nums[next_index]) + \ 38 calculate_min_cost(visited_mask | (1 << next_index), next_index) 39 min_cost = min(min_cost, cost) 40 41 return min_cost 42 43 def construct_path(visited_mask: int, current_index: int) -> None: 44 """ 45 Reconstruct the optimal path by following the decisions that led to minimum cost. 46 47 Args: 48 visited_mask: Bitmask representing visited indices 49 current_index: Current position in the tour 50 """ 51 # Add current index to the result path 52 result_path.append(current_index) 53 54 # If all nodes are visited, we're done 55 if visited_mask == (1 << n) - 1: 56 return 57 58 # Get the optimal cost from current state 59 optimal_cost = calculate_min_cost(visited_mask, current_index) 60 61 # Find which next move achieves this optimal cost 62 for next_index in range(1, n): 63 # Check if next_index is not visited 64 if (visited_mask >> next_index) & 1 == 0: 65 # Calculate cost of moving to next_index 66 edge_cost = abs(nums[current_index] - nums[next_index]) 67 remaining_cost = calculate_min_cost(visited_mask | (1 << next_index), next_index) 68 69 # If this path gives optimal cost, follow it 70 if edge_cost + remaining_cost == optimal_cost: 71 construct_path(visited_mask | (1 << next_index), next_index) 72 break 73 74 # Initialize variables 75 n = len(nums) 76 result_path = [] 77 78 # Start from index 0 (with bitmask having only bit 0 set) 79 construct_path(1, 0) 80 81 return result_path 82

1class Solution { 2 // Memoization table: dp[mask][lastIndex] stores minimum cost 3 // mask: bitmask representing visited positions 4 // lastIndex: the last visited position 5 private Integer[][] dp; 6 7 // Input array 8 private int[] nums; 9 10 // Result array to store the permutation 11 private int[] result; 12 13 // Length of the input array 14 private int n; 15 16 /** 17 * Finds the permutation that minimizes the sum of absolute differences 18 * between consecutive elements, starting and ending at index 0 19 * 20 * @param nums the input array 21 * @return the optimal permutation as indices 22 */ 23 public int[] findPermutation(int[] nums) { 24 n = nums.length; 25 result = new int[n]; 26 this.nums = nums; 27 28 // Initialize DP table: 2^n states for mask, n states for last position 29 dp = new Integer[1 << n][n]; 30 31 // Start building the path from position 0 32 buildPath(1, 0, 0); 33 34 return result; 35 } 36 37 /** 38 * Dynamic programming function to find minimum cost 39 * 40 * @param mask bitmask representing visited positions (1 = visited) 41 * @param lastPos the last visited position index 42 * @return minimum cost to complete the tour from current state 43 */ 44 private int dfs(int mask, int lastPos) { 45 // Base case: all positions visited, return cost to go back to start 46 if (mask == (1 << n) - 1) { 47 return Math.abs(lastPos - nums[0]); 48 } 49 50 // Return memoized result if already computed 51 if (dp[mask][lastPos] != null) { 52 return dp[mask][lastPos]; 53 } 54 55 int minCost = Integer.MAX_VALUE; 56 57 // Try visiting each unvisited position (except position 0) 58 for (int nextPos = 1; nextPos < n; ++nextPos) { 59 // Check if position nextPos is not visited yet 60 if ((mask >> nextPos & 1) == 0) { 61 // Calculate cost: distance to next position + remaining cost 62 int currentCost = Math.abs(lastPos - nums[nextPos]) + 63 dfs(mask | (1 << nextPos), nextPos); 64 minCost = Math.min(minCost, currentCost); 65 } 66 } 67 68 // Memoize and return the result 69 return dp[mask][lastPos] = minCost; 70 } 71 72 /** 73 * Reconstructs the optimal path by following the DP decisions 74 * 75 * @param mask bitmask representing visited positions 76 * @param currentPos current position index 77 * @param stepIndex current step number in the result array 78 */ 79 private void g(int mask, int currentPos, int stepIndex) { 80 // Store current position in result array 81 result[stepIndex] = currentPos; 82 83 // Base case: all positions visited 84 if (mask == (1 << n) - 1) { 85 return; 86 } 87 88 // Get the optimal cost from current state 89 int optimalCost = dfs(mask, currentPos); 90 91 // Find which next position achieves the optimal cost 92 for (int nextPos = 1; nextPos < n; ++nextPos) { 93 // Check if position is unvisited 94 if ((mask >> nextPos & 1) == 0) { 95 // Check if this move leads to optimal solution 96 int moveCost = Math.abs(currentPos - nums[nextPos]) + 97 dfs(mask | (1 << nextPos), nextPos); 98 99 if (moveCost == optimalCost) { 100 // Found the optimal next move, continue building path 101 g(mask | (1 << nextPos), nextPos, stepIndex + 1); 102 break; 103 } 104 } 105 } 106 } 107} 108

1class Solution { 2public: 3 vector<int> findPermutation(vector<int>& nums) { 4 int n = nums.size(); 5 vector<int> result; 6 7 // dp[mask][last]: minimum cost to visit all positions set in mask, ending at position 'last' 8 // -1 indicates uncomputed state 9 int dp[1 << n][n]; 10 memset(dp, -1, sizeof(dp)); 11 12 // Dynamic programming function to compute minimum cost 13 // mask: bitmask representing visited positions (1 = visited, 0 = unvisited) 14 // lastPos: the last position in the current path 15 function<int(int, int)> computeMinCost = [&](int mask, int lastPos) { 16 // Base case: all positions visited, return cost to go back to start 17 if (mask == (1 << n) - 1) { 18 return abs(lastPos - nums[0]); 19 } 20 21 // Check memoization 22 int* dpValue = &dp[mask][lastPos]; 23 if (*dpValue != -1) { 24 return *dpValue; 25 } 26 27 // Try all unvisited positions as next position 28 *dpValue = INT_MAX; 29 for (int nextPos = 1; nextPos < n; ++nextPos) { 30 // Check if nextPos is unvisited (bit is 0) 31 if ((mask >> nextPos & 1) ^ 1) { 32 int cost = abs(lastPos - nums[nextPos]) + 33 computeMinCost(mask | (1 << nextPos), nextPos); 34 *dpValue = min(*dpValue, cost); 35 } 36 } 37 38 return *dpValue; 39 }; 40 41 // Reconstruct the optimal path 42 // mask: bitmask representing visited positions 43 // currentPos: current position in the path 44 function<void(int, int)> reconstructPath = [&](int mask, int currentPos) { 45 // Add current position to result 46 result.push_back(currentPos); 47 48 // Base case: all positions visited 49 if (mask == (1 << n) - 1) { 50 return; 51 } 52 53 // Get the optimal cost from current state 54 int optimalCost = computeMinCost(mask, currentPos); 55 56 // Find which next position achieves the optimal cost 57 for (int nextPos = 1; nextPos < n; ++nextPos) { 58 // Check if nextPos is unvisited 59 if ((mask >> nextPos & 1) ^ 1) { 60 int costThroughNext = abs(currentPos - nums[nextPos]) + 61 computeMinCost(mask | (1 << nextPos), nextPos); 62 63 // If this path achieves optimal cost, follow it 64 if (costThroughNext == optimalCost) { 65 reconstructPath(mask | (1 << nextPos), nextPos); 66 break; 67 } 68 } 69 } 70 }; 71 72 // Start from position 0 (bit 0 is set in initial mask) 73 reconstructPath(1, 0); 74 75 return result; 76 } 77}; 78

1/** 2 * Finds the optimal permutation of array indices that minimizes the total distance 3 * when traversing elements in sequence, starting and ending at index 0 4 * @param nums - Input array of numbers 5 * @returns Array of indices representing the optimal permutation 6 */ 7function findPermutation(nums: number[]): number[] { 8 const arrayLength: number = nums.length; 9 const resultPath: number[] = []; 10 11 // Memoization table: dp[visitedMask][lastIndex] = minimum cost 12 // visitedMask uses bit representation to track visited indices 13 const memoTable: number[][] = Array.from( 14 { length: 1 << arrayLength }, 15 () => Array(arrayLength).fill(-1) 16 ); 17 18 /** 19 * Dynamic programming function to find minimum cost path 20 * @param visitedMask - Bitmask representing visited indices 21 * @param lastVisitedIndex - The last visited index in the path 22 * @returns Minimum cost to complete the path from current state 23 */ 24 const calculateMinimumCost = (visitedMask: number, lastVisitedIndex: number): number => { 25 // Base case: all indices visited, return cost to go back to start 26 if (visitedMask === (1 << arrayLength) - 1) { 27 return Math.abs(lastVisitedIndex - nums[0]); 28 } 29 30 // Return memoized result if already calculated 31 if (memoTable[visitedMask][lastVisitedIndex] !== -1) { 32 return memoTable[visitedMask][lastVisitedIndex]; 33 } 34 35 let minimumCost: number = Infinity; 36 37 // Try visiting each unvisited index 38 for (let currentIndex = 1; currentIndex < arrayLength; ++currentIndex) { 39 // Check if currentIndex is not visited (bit is 0) 40 if (((visitedMask >> currentIndex) & 1) ^ 1) { 41 // Calculate cost: distance to current + cost of remaining path 42 const totalCost: number = Math.abs(lastVisitedIndex - nums[currentIndex]) + 43 calculateMinimumCost(visitedMask | (1 << currentIndex), currentIndex); 44 minimumCost = Math.min(minimumCost, totalCost); 45 } 46 } 47 48 // Memoize and return the result 49 return (memoTable[visitedMask][lastVisitedIndex] = minimumCost); 50 }; 51 52 /** 53 * Reconstructs the optimal path by following the minimum cost decisions 54 * @param visitedMask - Bitmask representing visited indices 55 * @param lastVisitedIndex - The last visited index in the path 56 */ 57 const reconstructPath = (visitedMask: number, lastVisitedIndex: number): void => { 58 // Add current index to result path 59 resultPath.push(lastVisitedIndex); 60 61 // Base case: all indices visited 62 if (visitedMask === (1 << arrayLength) - 1) { 63 return; 64 } 65 66 // Get the optimal cost from current state 67 const optimalCost: number = calculateMinimumCost(visitedMask, lastVisitedIndex); 68 69 // Find which next index achieves the optimal cost 70 for (let currentIndex = 1; currentIndex < arrayLength; ++currentIndex) { 71 // Check if currentIndex is not visited 72 if (((visitedMask >> currentIndex) & 1) ^ 1) { 73 // Check if this path achieves the optimal cost 74 const pathCost: number = Math.abs(lastVisitedIndex - nums[currentIndex]) + 75 calculateMinimumCost(visitedMask | (1 << currentIndex), currentIndex); 76 77 if (pathCost === optimalCost) { 78 // Continue reconstruction with this choice 79 reconstructPath(visitedMask | (1 << currentIndex), currentIndex); 80 break; 81 } 82 } 83 } 84 }; 85 86 // Start path reconstruction from index 0 (with bitmask having bit 0 set) 87 reconstructPath(1, 0); 88 89 return resultPath; 90} 91

Solution Approach

The solution uses memoized recursion with state compression to find the optimal permutation. Here's how the implementation works:

State Representation: We use a bitmask mask to represent which numbers have been selected. If the i-th bit of mask is 1, it means number i has been included in our permutation. For example, mask = 5 (binary: 101) means we've selected numbers 0 and 2.

Dynamic Programming Function dfs(mask, pre): This function calculates the minimum score possible when:

We've already selected the numbers indicated by mask
The last selected number was pre

The function works as follows:

Base case: If mask == (1 << n) - 1 (all bits set, meaning all numbers selected), we've completed the cycle. Return |pre - nums[0]| to close the cycle back to the first element.
Recursive case: For each unselected number cur (where mask >> cur & 1 ^ 1 checks if bit cur is 0):
- Calculate the cost of selecting cur next: |pre - nums[cur]|
- Add the minimum cost for the remaining choices: dfs(mask | 1 << cur, cur)
- Track the minimum total cost across all choices

The @cache decorator memoizes results to avoid recomputing the same states.

Permutation Construction with g(mask, pre): Once we know the minimum costs, we reconstruct the actual permutation:

Add the current number pre to our answer list
If we've selected all numbers (mask == (1 << n) - 1), we're done
Otherwise, get the minimum cost from the current state: res = dfs(mask, pre)
Try each unselected number cur in ascending order (for lexicographic ordering):
- Check if selecting cur achieves the minimum cost: |pre - nums[cur]| + dfs(mask | 1 << cur, cur) == res
- If yes, recursively build the rest of the permutation with g(mask | 1 << cur, cur) and break (ensuring lexicographically smallest choice)

Main Execution: The solution starts by calling g(1, 0), which means:

Initial mask is 1 (binary: 0...001), indicating only number 0 is selected
Starting with pre = 0 (first element is 0 for lexicographic ordering)

The time complexity is O(n^2 * 2^n) due to the state space and transitions, while the space complexity is O(n * 2^n) for memoization.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with nums = [1, 0, 2].

Step 1: Understanding the Score Calculation For any permutation perm, the score is: |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + |perm[2] - nums[perm[0]]|

Step 2: Initialize DFS Computation We start with perm[0] = 0 (for lexicographic ordering). Now we need to find the minimum cost using dfs(mask, pre):

dfs(001, 0): mask=1 (binary 001) means only 0 is selected, pre=0
- Can choose 1: cost = |0 - nums[1]| + dfs(011, 1) = |0 - 0| + dfs(3, 1) = 0 + dfs(3, 1)
- Can choose 2: cost = |0 - nums[2]| + dfs(101, 2) = |0 - 2| + dfs(5, 2) = 2 + dfs(5, 2)
dfs(011, 1): mask=3 means 0,1 selected, pre=1
- Only 2 available: cost = |1 - nums[2]| + dfs(111, 2) = |1 - 2| + dfs(7, 2) = 1 + dfs(7, 2)
dfs(101, 2): mask=5 means 0,2 selected, pre=2
- Only 1 available: cost = |2 - nums[1]| + dfs(111, 1) = |2 - 0| + dfs(7, 1) = 2 + dfs(7, 1)
dfs(111, 2): All selected, pre=2, return to start
- Return |2 - nums[0]| = |2 - 1| = 1
dfs(111, 1): All selected, pre=1, return to start
- Return |1 - nums[0]| = |1 - 1| = 0

Step 3: Compute Minimum Costs Working backwards:

dfs(7, 2) = 1
dfs(7, 1) = 0
dfs(3, 1) = 1 + 1 = 2
dfs(5, 2) = 2 + 0 = 2
dfs(1, 0) = min(0 + 2, 2 + 2) = min(2, 4) = 2

Step 4: Construct the Permutation Now we build the permutation using g(mask, pre):

Starting with g(1, 0):

Add 0 to answer: ans = [0]
Check minimum cost: dfs(1, 0) = 2
Try cur=1: |0 - nums[1]| + dfs(3, 1) = 0 + 2 = 2 ✓ (equals minimum)
Recurse with g(3, 1)

Continue with g(3, 1):

Add 1 to answer: ans = [0, 1]
Only option is cur=2: |1 - nums[2]| + dfs(7, 2) = 1 + 1 = 2
Recurse with g(7, 2)

Finally g(7, 2):

Add 2 to answer: ans = [0, 1, 2]
All bits set, we're done

Result: The optimal permutation is [0, 1, 2] with score = 2

We can verify:

|0 - nums[1]| + |1 - nums[2]| + |2 - nums[0]|
= |0 - 0| + |1 - 2| + |2 - 1|
= 0 + 1 + 1 = 2

Time and Space Complexity

Time Complexity: O(n² × 2ⁿ)

The time complexity is determined by the dynamic programming function dfs:

The function uses memoization with @cache, creating at most 2ⁿ × n unique states (where mask has 2ⁿ possible values representing subsets, and pre has n possible values representing the previous index)
For each state (mask, pre), the function iterates through all n positions to find unvisited nodes (the for loop from 1 to n)
Each state is computed only once due to memoization
Therefore, the total time complexity is O(n × 2ⁿ × n) = O(n² × 2ⁿ)

The reconstruction function g has the same traversal pattern but doesn't add to the overall complexity since it only traces back the optimal path once.

Space Complexity: O(n × 2ⁿ)

The space complexity consists of:

The memoization cache storing up to 2ⁿ × n states, each taking O(1) space
The recursion stack depth which is at most O(n) (visiting each element once)
The answer array ans which stores O(n) elements
Since 2ⁿ × n dominates, the overall space complexity is O(n × 2ⁿ)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Cycle Closure in Base Case

Pitfall: A common mistake is forgetting to close the cycle properly or using the wrong indices. In the base case, developers often return abs(pre - nums[pre]) or abs(nums[pre] - pre) instead of the correct abs(pre - nums[perm[0]]).

Why it happens: The scoring formula |perm[n-1] - nums[perm[0]]| for the last term is confusing. When we reach the base case, pre represents perm[n-1], and we need to connect back to nums[perm[0]]. Since we started with index 0, perm[0] = 0, so we should return abs(pre - nums[0]).

Solution: Always remember that in the cyclic tour, the last element connects back to wherever we started. Since we fix the starting point as 0, the base case should return abs(pre - nums[0]).

2. Mixing Up Index and Value in the Scoring Formula

Why it happens: The formula uses perm both as a source of values (left side) and indices (right side), which is counterintuitive.

Solution: Think of it this way:

perm[i] is the VALUE at position i in our permutation
perm[i+1] is used as an INDEX into the nums array
So we compare: value at position i vs. nums element at index given by position i+1

3. Starting from Arbitrary Position Instead of Fixed Position

Pitfall: Trying to consider all possible starting positions by iterating through different initial values, which breaks the lexicographical ordering requirement and increases complexity unnecessarily.

Why it happens: Developers might think they need to try all starting points to find the global minimum, not realizing that fixing the start at 0 is both correct and ensures lexicographical ordering.

Solution: Always start with 0 (calling g(1, 0)). Since it's a cycle, the minimum score is the same regardless of where we "cut" the cycle to represent it as a sequence. Starting with 0 guarantees the lexicographically smallest result among all minimum-score permutations.

4. Incorrect Bitmask Operations

Pitfall: Using wrong bit operations to check or set visited status:

Using mask & (1 << cur) instead of (mask >> cur) & 1 to check if bit is set
Using mask + (1 << cur) instead of mask | (1 << cur) to set a bit

Why it happens: Bit manipulation can be tricky, and different equivalent forms can be confusing.

Solution: Stick to consistent patterns:

Check if visited: (mask >> cur) & 1 == 1
Check if unvisited: (mask >> cur) & 1 == 0
Mark as visited: mask | (1 << cur)

5. Not Breaking After Finding First Valid Choice in Path Construction

Pitfall: In the construct_path function, continuing to explore other options after finding the first valid next move, which could lead to incorrect permutations or violate lexicographical ordering.

Why it happens: Developers might think they need to explore all paths that achieve minimum cost.

Solution: Since we iterate through indices in ascending order (0 to n-1), the first valid choice we find is automatically the lexicographically smallest. Always break immediately after recursing into the first valid path.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know