3149. Find the Minimum Cost Array Permutation

Description

You are given an array nums which is a 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 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].

 

Solutions

Solution: Dynamic Programming + Bit Manipulation

• Time complexity: O(2ⁿ*n²)
• Space complexity: O(2ⁿ*n²)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const findPermutation = function (nums) {
  const n = nums.length;
  const totalMask = 1 << n;
  const dp = Array.from({ length: n }, () => new Array(totalMask).fill(-1));
  const bestPick = Array.from({ length: n }, () => new Array(totalMask).fill(-1));

  const getScore = (last, mask) => {
    if (popcount(mask) === n) {
      return Math.abs(last - nums[0]);
    }

    if (dp[last][mask] !== -1) {
      return dp[last][mask];
    }

    let result = Number.MAX_SAFE_INTEGER;

    for (let index = 1; index < n; index++) {
      if ((mask >> index) & 1) continue;

      const nextMask = mask | (1 << index);
      const score = Math.abs(last - nums[index]) + getScore(index, nextMask);

      if (score < result) {
        result = score;
        bestPick[last][mask] = index;
      }
    }

    dp[last][mask] = result;

    return result;
  };

  const result = [];
  let last = 0;
  let mask = 1;

  getScore(0, 1);

  for (let index = 0; index < n; index++) {
    result.push(last);
    last = bestPick[last][mask];
    mask |= 1 << last;
  }

  return result;
};

function popcount(mask) {
  let count = 0;

  while (mask) {
    mask &= mask - 1;
    count += 1;
  }

  return count;
}