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]. The score of any permutation of [0, 1, 2, ..., n - 1], called perm, is defined as:

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

The task is to return the permutation perm which has the minimum possible score. If multiple permutations exist with this minimum score, return the one that is lexicographically smallest among them.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem effectively, we need to consider a few key observations:

Cyclical Nature of Score: The score calculation involves a cyclical permutation of indices, which means that if we shift the permutation left or right, the score remains unchanged. Thus, starting the permutation with a fixed element (like 0) is a valid strategy to find the lexicographically smallest permutation.
Search Space: Given that nums is a permutation of integers from 0 to n-1, the complexity of trying all permutations is not feasible for larger n. However, because the problem constraints are within manageable limits (n does not exceed 14), leveraging state space search is practical.
State Compression and DP: We use a state compression technique where a binary number (mask) represents the set of selected numbers in the permutation. This allows for efficient tracking of which numbers have been used.
- DFS with Memoization: We define a recursive function dfs(mask, pre) that computes the minimum score possible when the set of numbers represented by mask is selected, with pre being the last number in the current permutation. The base case is when all numbers have been used, and we return the final transition's absolute difference.
- Constructing the Permutation: Once we know the minimum score, another function g(mask, pre) is used to reconstruct the actual permutation that achieves this score. It ensures we build the permutation in lexicographically smallest order by carefully selecting candidates for the next position.

By coupling state compression and memoization with strategic backtracking, we efficiently explore the permutation space to solve for the minimum score permutation.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The solution for this problem is centered around a dynamic programming approach using memoization and state compression. Here's a detailed walk-through of the implementation:

State Representation:
- We use a binary number mask of length n to indicate which numbers have been included in the current permutation. This allows us to efficiently manage and track the choices available at each step.
Recursive Function dfs(mask, pre):
- This function calculates the minimum score for a given state (mask, pre). Here, mask represents the selected numbers, and pre is the last number chosen in the permutation.
- Base Case: If all numbers are selected (mask equals (1 << n) - 1), return the final transition score |pre - nums[0]|.
- Recursive Case: Iterate over all possible next numbers (cur) that haven't been selected (determined by checking if the cur bit in mask is 0).
  - For each viable cur, update mask to include cur and recursively call dfs to compute the score. Select the minimum score among all possibilities.
Constructing the Result with g(mask, pre):
- This function constructs the permutation that achieves the minimum score by leveraging dfs outcomes.
- Start by appending pre to the results list ans.
- For the next number cur, verify if it matches the criteria for the minimal score path and includes it in the permutation sequentially while updating mask.
Algorithm Execution:
- Initialize by calling g(1, 0) with 0 already selected, as we aim for the lexicographically smallest starting point.
- Utilize memoization (@cache) to store intermediate results and avoid redundant calculations, ensuring efficient execution.

Using this approach, the solution efficiently explores all permutations, minimizes the score, and constructs the optimal permutation sequence. The combination of state compression with dynamic programming allows handling complex permutations within acceptable limits.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the array nums defined as [2, 0, 1]. We'll walk through the steps to find the permutation perm that minimizes the score and is lexicographically smallest.

Initial Setup:
- Our goal is to construct a permutation of [0, 1, 2] that minimizes the score function described.
- We start by selecting the initial element 0 to ensure the permutation is lexicographically smallest, as 0 is the smallest possible starting element.
Recursive Function dfs(mask, pre):
- Begin by calling dfs(1, 0) where 1 (binary 001) indicates 0 is selected, and pre is also 0.
Recursive Exploration:
- For mask 1 and pre 0:
  - We can select other elements that haven't been picked. Next options are 1 and 2.
  - Suppose we select 1, updating mask to 3 (binary 011) and calling dfs(3, 1).
- For mask 3 and pre 1:
  - The only remaining unpicked number is 2.
  - Select 2, update mask to 7 (binary 111), and call dfs(7, 2).
- For mask 7 and pre 2:
  - All numbers are now selected. Calculate the final transition score as |2 - nums[0]| = |2 - 2| = 0.
  - This contributes to the final score.
Calculate Score Iteratively:
- Throughout recursive calls, calculate the contribution to the score and keep track of each minimal score scenario using memoization.
- Repeat similar steps for other combinations such as selecting 2 after 0, but ensure the lexicographical order is maintained.
Constructing the Permutation with g(mask, pre):
- The result is constructed backward using the dfs outcomes, ensuring throughout we choose next elements that lead to minimal score paths and maintain lexicographical order.
Final Result:
- After completing all calls, the function g(1, 0) constructs the result by selecting elements in the order satisfying both the minimum score and lexicographical precedence.

In this example, the permutation perm = [0, 2, 1] provides the minimal score path with the given nums = [2, 0, 1].

Solution Implementation

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def findPermutation(self, nums: List[int]) -> List[int]:
6        # Use a cached depth-first search to find the optimal path
7        @lru_cache(None)
8        def dfs(mask: int, pre_idx: int) -> int:
9            if mask == (1 << n) - 1:
10                # If all elements are visited, calculate the absolute difference with the first element
11                return abs(nums[pre_idx] - nums[0])
12          
13            result = float('inf')  # Initialize to infinity for minimum comparison
14            for cur_idx in range(1, n):
15                if not (mask >> cur_idx) & 1:
16                    # If the current index 'cur_idx' is not visited, proceed with it
17                    result = min(result, abs(nums[pre_idx] - nums[cur_idx]) + dfs(mask | (1 << cur_idx), cur_idx))
18            return result
19
20        # Reconstruct the optimal path using the results from dfs
21        def reconstruct_path(mask: int, pre_idx: int):
22            ans.append(nums[pre_idx])  # Append the current element to the answer
23            if mask == (1 << n) - 1:
24                return  # If all elements are visited, return
25
26            optimal_cost = dfs(mask, pre_idx)
27            for cur_idx in range(1, n):
28                if not (mask >> cur_idx) & 1:
29                    # Check which next step leads to the optimal cost
30                    if abs(nums[pre_idx] - nums[cur_idx]) + dfs(mask | (1 << cur_idx), cur_idx) == optimal_cost:
31                        reconstruct_path(mask | (1 << cur_idx), cur_idx)
32                        break  # Break as soon as the correct path is found
33
34        n = len(nums)  # Length of the input list
35        ans = []  # Initialize the answer list
36        reconstruct_path(1, 0)  # Start reconstructing from the first element
37        return ans  # Return the final permutation
38

1class Solution {
2    // Memoization table to store results of subproblems
3    private Integer[][] memoizationTable;
4    // Array to store input numbers
5    private int[] numbers;
6    // Array to store the result permutation
7    private int[] resultPermutation;
8    // Length of the numbers array
9    private int length;
10
11    public int[] findPermutation(int[] nums) {
12        length = nums.length;
13        resultPermutation = new int[length];
14        this.numbers = nums;
15        memoizationTable = new Integer[1 << length][length];
16        // Begin recursive permutation finding
17        g(1, 0, 0);
18        return resultPermutation;
19    }
20
21    // Recursive method to calculate minimum sum of differences
22    private int dfs(int mask, int prevIndex) {
23        // If all numbers are included in the mask, return the difference with the first element
24        if (mask == (1 << length) - 1) {
25            return Math.abs(numbers[prevIndex] - numbers[0]);
26        }
27        // Return previously computed result if available
28        if (memoizationTable[mask][prevIndex] != null) {
29            return memoizationTable[mask][prevIndex];
30        }
31        // Initialize result to a large value to find minimum
32        int minDifference = Integer.MAX_VALUE;
33        // Iterate over possible elements to include next
34        for (int currentIndex = 1; currentIndex < length; ++currentIndex) {
35            // Check if the current element is not yet included in the mask
36            if ((mask >> currentIndex & 1) == 0) {
37                // Calculate new difference and recursively find the rest
38                minDifference = Math.min(minDifference, Math.abs(numbers[prevIndex] - numbers[currentIndex]) + dfs(mask | 1 << currentIndex, currentIndex));
39            }
40        }
41        // Memoize and return the result
42        return memoizationTable[mask][prevIndex] = minDifference;
43    }
44
45    // Generates the permutation based on the minimum differences found
46    private void g(int mask, int prevIndex, int position) {
47        // Assign the current element to the result permutation
48        resultPermutation[position] = prevIndex;
49        // Base case: if all the numbers are included, return
50        if (mask == (1 << length) - 1) {
51            return;
52        }
53        // Get the minimum sum of differences from the dfs
54        int minDifference = dfs(mask, prevIndex);
55        // Iterate over possible elements to include next
56        for (int currentIndex = 1; currentIndex < length; ++currentIndex) {
57            // Check if the current element is not yet included in the mask
58            if ((mask >> currentIndex & 1) == 0) {
59                // If this inclusion gives the minimum value found, proceed recursively
60                if (Math.abs(numbers[prevIndex] - numbers[currentIndex]) + dfs(mask | 1 << currentIndex, currentIndex) == minDifference) {
61                    g(mask | 1 << currentIndex, currentIndex, position + 1);
62                    break;
63                }
64            }
65        }
66    }
67}
68

1#include <vector>
2#include <cstring>
3#include <functional>
4#include <climits>
5#include <cmath>
6
7class Solution {
8public:
9    std::vector<int> findPermutation(std::vector<int>& nums) {
10        int n = nums.size(); // Get the size of the array nums
11        std::vector<int> result;
12        int dp[1 << n][n]; // Dynamic programming table to store intermediate results
13
14        // Initialize the dp table with -1 (indicating not computed)
15        std::memset(dp, -1, sizeof(dp));
16
17        // Helper function for depth-first search to find the minimum cost path
18        std::function<int(int, int)> dfs = [&](int mask, int preIndex) {
19            // If all numbers are included in the permutation
20            if (mask == (1 << n) - 1) {
21                return std::abs(preIndex - nums[0]); // Return the absolute difference with the first number
22            }
23
24            int* res = &dp[mask][preIndex]; // Reference to the result for current state in dp table
25            if (*res != -1) {
26                return *res; // Return cached result if already computed
27            }
28
29            *res = INT_MAX; // Set to maximum value for minimization
30            for (int curIndex = 1; curIndex < n; ++curIndex) {
31                // If curIndex is not included in the current mask
32                if ((mask >> curIndex & 1) == 0) {
33                    // Recur for the next state including curIndex and update the minimum result
34                    *res = std::min(*res, std::abs(preIndex - nums[curIndex]) + dfs(mask | (1 << curIndex), curIndex));
35                }
36            }
37            return *res; // Return computed result
38        };
39
40        // Helper function to reconstruct the path from the dp table
41        std::function<void(int, int)> reconstructPath = [&](int mask, int preIndex) {
42            result.push_back(preIndex); // Add the current index to the result
43            if (mask == (1 << n) - 1) {
44                return; // If all numbers are included, base case
45            }
46
47            int res = dfs(mask, preIndex); // Get the result for the current state
48            for (int curIndex = 1; curIndex < n; ++curIndex) {
49                // If curIndex is not included in the current mask
50                if ((mask >> curIndex & 1) == 0) {
51                    // Check if including curIndex in the path leads to the optimal result
52                    if (std::abs(preIndex - nums[curIndex]) + dfs(mask | (1 << curIndex), curIndex) == res) {
53                        reconstructPath(mask | (1 << curIndex), curIndex); // Recur with curIndex included
54                        break; // Stop after finding the first valid path
55                    }
56                }
57            }
58        };
59
60        reconstructPath(1, 0); // Start the reconstruction from the first number
61        return result; // Return the resulting permutation
62    }
63};
64

1function findPermutation(nums: number[]): number[] {
2    const n = nums.length; // Length of the input array
3    const ans: number[] = []; // Resultant array to store the permutation
4    const f: number[][] = Array.from({ length: 1 << n }, () => Array(n).fill(-1)); // DP table to memoize results
5
6    // DFS function to find the minimum cost to visit all nodes by dynamic programming
7    const dfs = (mask: number, pre: number): number => {
8        // Base case: if all elements have been included in the mask
9        if (mask === (1 << n) - 1) {
10            return Math.abs(pre - nums[0]); // Return the cost to form a cycle 
11        }
12        // Return memoized result if it exists
13        if (f[mask][pre] !== -1) {
14            return f[mask][pre];
15        }
16        let res = Infinity; // Variable to store the minimum cost
17
18        // Check all possible elements to include in the permutation
19        for (let cur = 1; cur < n; ++cur) {
20            // If the current element is not yet included in the mask
21            if (((mask >> cur) & 1) ^ 1) {
22                // Compute the cost recursively and update the minimum
23                res = Math.min(res, Math.abs(pre - nums[cur]) + dfs(mask | (1 << cur), cur));
24            }
25        }
26        // Memoize the result
27        return (f[mask][pre] = res);
28    };
29
30    // Helper function to reconstruct the path from the DP table
31    const g = (mask: number, pre: number) => {
32        ans.push(pre); // Add the current index to the result
33        // Termination condition: all elements included
34        if (mask === (1 << n) - 1) {
35            return;
36        }
37        const res = dfs(mask, pre); // Get the result of the current state
38      
39        // Reconstruct the path by finding the correct element to include next
40        for (let cur = 1; cur < n; ++cur) {
41            if (((mask >> cur) & 1) ^ 1) {
42                // Checking if including 'cur' yields the optimal result
43                if (Math.abs(pre - nums[cur]) + dfs(mask | (1 << cur), cur) === res) {
44                    g(mask | (1 << cur), cur); // Recurse into the next state
45                    break; // Stop the loop as we found the correct path
46                }
47            }
48        }
49    };
50
51    g(1, 0); // Start the reconstruction with first element included
52    return ans; // Return the computed permutation
53}
54

Time and Space Complexity

The time complexity and space complexity of the code are as follows:

Time Complexity: The function primarily uses a Depth-First Search (DFS) with memoization over all permutations of nums. The number of states is influenced by mask, which is of size 2^n, and for each state, it checks n possibilities resulting in a time complexity of O(n^2 * 2^n).
Space Complexity: The space complexity is mainly driven by the memoization cache, which stores results for each combination of mask and pre. Hence, it requires space proportional to O(n * 2^n).

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

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

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems