We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Cost Array Permutation

Number: 3431

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

You are given an array nums which is a permutation of [0, 1, 2, ..., n - 1]. The score of any permutation 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 that yields the minimum possible score. If multiple permutations have the same score, return the lexicographically smallest one.

Key Insights

  • The brute-force permutation space is n! and n is at most 14, but we can optimize using bitmask dynamic programming.
  • Use a DP table where each state is represented by a bitmask and the last element used, i.e., dp[mask][last] stores the best (minimum cost, lexicographically smallest) permutation for that state.
  • Transition from one state to another by considering the cost addition: absolute difference between the last element in the current permutation and nums[j] for the candidate j.
  • Final cost must add the closing term: |perm[n-1] - nums[perm[0]]|.
  • Keep track of both the cost and the permutation itself to enforce the lexicographical order in case of ties.

Space and Time Complexity

Time Complexity: O(n^2 * 2^n) due to iterating over all bitmask states and possible transitions. Space Complexity: O(n * 2^n) to store the DP states.

Solution

We use a bitmask DP approach where each state is defined by a mask that tracks which indices have been used and by the last chosen element. The DP table stores a pair (cost, permutation list). We initialize with all single-element permutations. For each state, we try to append a new candidate j (not in the current mask) by calculating the new cost (current cost + |last - nums[j]|) and updating the DP state if we get a lower cost or equal cost but with a lexicographically smaller permutation. After filling the DP states, we iterate over the complete states (mask with all bits set) and add the closing cost |last element - nums[first element]| to determine the final solution.

Code Solutions

# Python implementation

def find_minimum_cost_permutation(nums):
    from math import inf
    n = len(nums)
    # dp[mask][last] = (cost, permutation as a list)
    dp = [[(inf, []) for _ in range(n)] for _ in range(1 << n)]
    
    # Base case: initialize single-element permutations
    for i in range(n):
        dp[1 << i][i] = (0, [i])
    
    # Iterate over all DP states represented by mask and last element index
    for mask in range(1 << n):
        for last in range(n):
            cost, perm = dp[mask][last]
            if cost == inf:
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue
                next_mask = mask | (1 << j)
                # Add cost: absolute difference between last and nums[j]
                new_cost = cost + abs(last - nums[j])
                new_perm = perm + [j]
                curr_cost, curr_perm = dp[next_mask][j]
                if new_cost < curr_cost or (new_cost == curr_cost and new_perm < curr_perm):
                    dp[next_mask][j] = (new_cost, new_perm)
    
    # Complete the cycle with the closing cost: |perm[-1] - nums[perm[0]]|
    best_cost = inf
    best_perm = None
    full_mask = (1 << n) - 1
    for last in range(n):
        cost, perm = dp[full_mask][last]
        if cost == inf:
            continue
        total_cost = cost + abs(perm[-1] - nums[perm[0]])
        if total_cost < best_cost or (total_cost == best_cost and perm < best_perm):
            best_cost = total_cost
            best_perm = perm
            
    return best_perm

# Example usage:
nums = [1, 0, 2]
print(find_minimum_cost_permutation(nums))  # Expected Output: [0, 1, 2]
← Back to All Questions