3149. Find the Minimum Cost Array Permutation LeetCode Solution
In this guide, you will get 3149. Find the Minimum Cost Array Permutation LeetCode Solution with the best time and space complexity. The solution to Find the Minimum Cost Array Permutation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Minimum Cost Array Permutation
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.
2 <= n == nums.length <= 14
nums is a permutation of [0, 1, 2, …, n – 1].
Complexity Analysis
Time Complexity: O(2^n \cdot n^2)
Space Complexity: O(2^n \cdot n)
3149. Find the Minimum Cost Array Permutation LeetCode Solution in C++
class Solution {
public:
vector<int> findPermutation(vector<int>& nums) {
const int n = nums.size();
vector<vector<int>> mem(n, vector<int>(1 << n));
// bestPick[last][mask] := the best pick, where `last` is the last chosen
// number and `mask` is the bitmask of the chosen numbers
vector<vector<int>> bestPick(n, vector<int>(1 << n));
// Choose 0 as perm[0] since the score function is cyclic.
getScore(nums, /*last=*/0, /*mask=*/1, bestPick, mem);
return construct(bestPick);
}
private:
// Returns the minimum score, where `last` is the last chosen number and
// `mask` is the bitmask of the chosen numbers.
int getScore(const vector<int>& nums, int last, unsigned mask,
vector<vector<int>>& bestPick, vector<vector<int>>& mem) {
if (popcount(mask) == nums.size())
return abs(last - nums[0]); // |perm[n - 1] - nums[perm[0]]|
if (mem[last][mask] > 0)
return mem[last][mask];
int minScore = INT_MAX;
for (int i = 1; i < nums.size(); ++i) {
if (mask >> i & 1)
continue;
const int nextMinScore =
abs(last - nums[i]) + getScore(nums, i, mask | 1 << i, bestPick, mem);
if (nextMinScore < minScore) {
minScore = nextMinScore;
bestPick[last][mask] = i;
}
}
return mem[last][mask] = minScore;
}
vector<int> construct(const vector<vector<int>>& bestPick) {
vector<int> ans;
int last = 0;
int mask = 1;
for (int i = 0; i < bestPick.size(); ++i) {
ans.push_back(last);
last = bestPick[last][mask];
mask |= 1 << last;
}
return ans;
}
}; /* code provided by PROGIEZ */
3149. Find the Minimum Cost Array Permutation LeetCode Solution in Java
class Solution {
public int[] findPermutation(int[] nums) {
final int n = nums.length;
int[][] mem = new int[n][1 << n];
// bestPick[last][mask] := the best pick, where `last` is the last chosen
// number and `mask` is the bitmask of the chosen numbers
int[][] bestPick = new int[n][1 << n];
// Choose 0 as perm[0] since the score function is cyclic.
getScore(nums, /*last=*/0, /*mask=*/1, bestPick, mem);
return construct(bestPick);
}
// Returns the minimum score, where `last` is the last chosen number and
// `mask` is the bitmask of the chosen numbers.
private int getScore(int[] nums, int last, int mask, int[][] bestPick, int[][] mem) {
if (Integer.bitCount(mask) == nums.length)
return Math.abs(last - nums[0]); // |perm[n - 1] - nums[perm[0]]|
if (mem[last][mask] > 0)
return mem[last][mask];
int minScore = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; ++i) {
if ((mask >> i & 1) == 1)
continue;
int nextMinScore = Math.abs(last - nums[i]) + getScore(nums, i, mask | 1 << i, bestPick, mem);
if (nextMinScore < minScore) {
minScore = nextMinScore;
bestPick[last][mask] = i;
}
}
return mem[last][mask] = minScore;
}
private int[] construct(int[][] bestPick) {
int[] ans = new int[bestPick.length];
int last = 0;
int mask = 1;
for (int i = 0; i < bestPick.length; ++i) {
ans[i] = last;
last = bestPick[last][mask];
mask |= 1 << last;
}
return ans;
}
} // code provided by PROGIEZ
3149. Find the Minimum Cost Array Permutation LeetCode Solution in Python
class Solution:
def findPermutation(self, nums: list[int]) -> list[int]:
n = len(nums)
bestPick = [[0] * (1 << n) for _ in range(n)]
@functools.lru_cache(None)
def getScore(last: int, mask: int) -> int:
if mask.bit_count() == len(nums):
return abs(last - nums[0])
minScore = math.inf
for i in range(1, len(nums)):
if mask >> i & 1:
continue
nextMinScore = abs(last - nums[i]) + getScore(i, mask | (1 << i))
if nextMinScore < minScore:
minScore = nextMinScore
bestPick[last][mask] = i
return minScore
getScore(0, 1)
return self._construct(bestPick)
def _construct(self, bestPick: list[list[int]]) -> list[int]:
ans = []
last = 0
mask = 1
for _ in range(len(bestPick)):
ans.append(last)
last = bestPick[last][mask]
mask |= 1 << last
return ans # code by PROGIEZ
