LeetCode 3149 - Find the Minimum Cost Array Permutation

LeetCode Problem 3149

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem presents an array nums of length n that is a permutation of integers from 0 to n - 1. We are asked to find a permutation perm of the same range [0, 1, 2, ..., n-1] that minimizes a special cost function defined as:

$$\text{score}(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + \dots + |perm[n-1] - nums[perm[0]]|$$

The output must not only minimize this cost but also be lexicographically smallest if multiple permutations yield the same minimum score. Lexicographical order means that for two permutations, the first position where they differ determines which is smaller.

The constraints are crucial: 2 <= n <= 14. Since the array length is small, we can consider algorithms that are exponential in n, but factorial time is still borderline for n = 14 (as 14! ≈ 87 billion). This strongly hints at dynamic programming with bitmasking as an appropriate approach.

Important edge cases include: arrays where nums[i] = i for all i, which often have trivial solutions, or arrays with maximum disorder, which stress the algorithm to consider multiple permutations carefully.

Approaches

The brute-force approach is straightforward. We can generate all permutations of [0, 1, 2, ..., n-1], compute their score using the given formula, and track the permutation with the smallest score. This guarantees correctness but is extremely slow. With n = 14, there are 14! permutations, which is computationally infeasible.

The optimal approach relies on dynamic programming with bitmasking. The key insight is that we can incrementally build permutations, tracking which elements are used with a bitmask. We define a state dp[mask][i] representing the minimum cost of a permutation that ends with element i and has used elements corresponding to mask. This allows us to recursively compute the minimum score efficiently. Lexicographical ordering is maintained by iterating through possible next elements in increasing order.

Algorithm Walkthrough

1. Define a DP table dp[mask][i] where mask is a bitmask of used indices, and i is the last element in the partial permutation. dp[mask][i] stores the minimum cost for that partial permutation.
2. Initialize dp for masks with a single bit set: dp[1 << i][i] = 0 since a permutation with one element has zero contribution.
3. Iterate over all masks with increasing numbers of set bits. For each mask and last element i, consider all elements j not in mask as the next element in the permutation.
4. Compute the incremental cost for adding j as the next element: abs(i - nums[j]).
5. Update dp[mask | (1 << j)][j] with the minimum between its current value and dp[mask][i] + abs(i - nums[j]). If there is a tie, choose the smaller j first to ensure lexicographical order.
6. After filling the DP table, all full masks (mask = (1 << n) - 1) contain the cost for complete permutations. To account for the last term connecting perm[n-1] back to nums[perm[0]], iterate over all possible last elements and add abs(last - nums[first]).
7. Reconstruct the permutation from the DP table using backtracking, always choosing the next element that contributed to the minimum cost and maintaining lexicographical order.

Why it works: The DP guarantees optimal substructure because any optimal full permutation is composed of optimal partial permutations. By keeping track of used elements and costs, we ensure that we do not recompute subproblems and that lexicographical order is preserved through careful iteration.

Python Solution

from typing import List

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        full_mask = (1 << n) - 1
        dp = [[float('inf')] * n for _ in range(1 << n)]
        parent = [[-1] * n for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = 0
        
        for mask in range(1 << n):
            for last in range(n):
                if not (mask & (1 << last)):
                    continue
                for nxt in range(n):
                    if mask & (1 << nxt):
                        continue
                    new_mask = mask | (1 << nxt)
                    cost = dp[mask][last] + abs(last - nums[nxt])
                    if cost < dp[new_mask][nxt]:
                        dp[new_mask][nxt] = cost
                        parent[new_mask][nxt] = last
                    elif cost == dp[new_mask][nxt] and last < parent[new_mask][nxt]:
                        parent[new_mask][nxt] = last
        
        min_cost = float('inf')
        end = -1
        for last in range(n):
            total_cost = dp[full_mask][last] + abs(last - nums[0])
            if total_cost < min_cost:
                min_cost = total_cost
                end = last
        
        mask = full_mask
        perm = []
        while end != -1:
            perm.append(end)
            prev = parent[mask][end]
            mask ^= (1 << end)
            end = prev
        perm.reverse()
        return perm

Implementation Walkthrough: The DP table stores minimum costs for every partial permutation. The parent table is used to reconstruct the path. We iterate over all possible last elements and unused elements to extend permutations incrementally. At the end, we account for the cycle closure and reconstruct the optimal permutation.

Go Solution

package main

import "math"

func findPermutation(nums []int) []int {
    n := len(nums)
    fullMask := (1 << n) - 1
    dp := make([][]int, 1<<n)
    parent := make([][]int, 1<<n)
    for i := 0; i < 1<<n; i++ {
        dp[i] = make([]int, n)
        parent[i] = make([]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = math.MaxInt
            parent[i][j] = -1
        }
    }
    for i := 0; i < n; i++ {
        dp[1<<i][i] = 0
    }
    
    for mask := 0; mask <= fullMask; mask++ {
        for last := 0; last < n; last++ {
            if mask&(1<<last) == 0 {
                continue
            }
            for nxt := 0; nxt < n; nxt++ {
                if mask&(1<<nxt) != 0 {
                    continue
                }
                newMask := mask | (1 << nxt)
                cost := dp[mask][last] + abs(last - nums[nxt])
                if cost < dp[newMask][nxt] {
                    dp[newMask][nxt] = cost
                    parent[newMask][nxt] = last
                } else if cost == dp[newMask][nxt] && last < parent[newMask][nxt] {
                    parent[newMask][nxt] = last
                }
            }
        }
    }
    
    minCost := math.MaxInt
    end := -1
    for last := 0; last < n; last++ {
        totalCost := dp[fullMask][last] + abs(last - nums[0])
        if totalCost < minCost {
            minCost = totalCost
            end = last
        }
    }
    
    perm := make([]int, 0, n)
    mask := fullMask
    for end != -1 {
        perm = append(perm, end)
        prev := parent[mask][end]
        mask ^= (1 << end)
        end = prev
    }
    
    // reverse
    for i, j := 0, len(perm)-1; i < j; i, j = i+1, j-1 {
        perm[i], perm[j] = perm[j], perm[i]
    }
    return perm
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Go Notes: Go handles MaxInt instead of float('inf'), and slices are used instead of lists. Backtracking and reversing the slice are done manually. Otherwise, the logic is identical to Python.

Worked Examples

Example 1: nums = [1,0,2]

Start DP initialization: