Find the minimum cost array permutation

Array Dynamic Programming Bit Manipulation Bitmask

25.4% acceptance

Feb 24, 2026

146

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_permutation(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let full = (1usize << n) - 1;
    const INF: i64 = i64::MAX / 2;

    // suffix[mask][last] = min cost to complete path from state (mask, last)
    // back to perm[0]=0, visiting all remaining elements
    let mut suffix = vec![vec![INF; n]; full + 1];

    // Base: all visited, close cycle back to perm[0]=0
    for last in 0..n {
      suffix[full][last] = (last as i32 - nums[0]).unsigned_abs() as i64;
    }

    // Fill backwards (decreasing mask popcount)
    for mask in (1..full).rev() {
      for last in 0..n {
        if mask & (1 << last) == 0 {
          continue;
        }
        let mut best = INF;
        for j in 0..n {
          if mask & (1 << j) != 0 {
            continue;
          }
          let step = (last as i32 - nums[j]).unsigned_abs() as i64;
          let new_mask = mask | (1 << j);
          if suffix[new_mask][j] < INF {
            let total = step + suffix[new_mask][j];
            if total < best {
              best = total;
            }
          }
        }
        suffix[mask][last] = best;
      }
    }

    // Greedy reconstruction: perm[0]=0, at each step pick the lex-smallest valid next
    let mut result = vec![0i32];
    let mut mask = 1usize;
    let mut last = 0usize;

    for _ in 1..n {
      for j in 0..n {
        if mask & (1 << j) != 0 {
          continue;
        }
        let step = (last as i32 - nums[j]).unsigned_abs() as i64;
        let new_mask = mask | (1 << j);
        if step + suffix[new_mask][j] == suffix[mask][last] {
          result.push(j as i32);
          mask = new_mask;
          last = j;
          break;
        }
      }
    }

    result
  }
}