Find the Minimum Cost Array Permutation - Practice Coding Problems

Find the Minimum Cost Array Permutation - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1, 0, 2]

› Output: [0, 1, 2]

💡 Note: For permutation [0,1,2]: score = |0-nums[1]| + |1-nums[2]| + |2-nums[0]| = |0-0| + |1-2| + |2-1| = 0 + 1 + 1 = 2. This is the minimum possible score.

Example 2 — Minimum Size

$ Input: nums = [0]

› Output: [0]

💡 Note: Only one element, so the only permutation is [0]. Score = |0-nums[0]| = |0-0| = 0.

Example 3 — Larger Array

$ Input: nums = [1, 3, 0, 2]

› Output: [0, 2, 3, 1]

💡 Note: Optimal permutation gives score = |0-nums[2]| + |2-nums[3]| + |3-nums[1]| + |1-nums[0]| = |0-0| + |2-2| + |3-3| + |1-1| = 0. This is lexicographically smallest among optimal solutions.

Constraints

1 ≤ nums.length ≤ 14
nums is a permutation of [0, 1, 2, ..., n - 1]

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums = [1, 0, 2] representing values at positions

Process

Find permutation perm where circular sum |perm[i] - nums[perm[(i+1)%n]]| is minimized

Output

Return lexicographically smallest optimal permutation [0, 1, 2]

Key Takeaway

🎯 Key Insight: Model as circular TSP using bitmask DP to efficiently explore all permutations while maintaining lexicographic order

Asked in

G Google 8 a Amazon 5

The key insight is to model this as a Traveling Salesman Problem variant using bitmask dynamic programming. We track visited nodes with bitmasks and build optimal paths incrementally, ensuring lexicographic ordering by starting from node 0. Best approach uses bitmask DP with Time: O(n² × 2ⁿ), Space: O(n × 2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(n² × 2ⁿ)	O(n × 2ⁿ)	Use bitmask DP to track visited nodes and find optimal path
Brute Force - Generate All Permutations	O(n! × n)	O(n)	Generate all possible permutations and calculate their scores

Dynamic Programming with Bitmask — Algorithm Steps

Start from node 0 (for lexicographic ordering)
Use bitmask to track visited nodes
For each state, try visiting unvisited nodes
Reconstruct path from DP table

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start at node 0, mark it as visited (bitmask = 1)

Build States

For each state (mask, position), try visiting unvisited nodes

Complete Cycle

Add cost to return to start, find minimum total cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    if (numsSize == 1) {
        int* result = (int*)malloc(sizeof(int));
        result[0] = 0;
        return result;
    }
    
    int n = numsSize;
    int maxMask = 1 << n;
    
    // DP state: dp[mask][i] = minimum cost
    int** dp = (int**)malloc(maxMask * sizeof(int*));
    int** parent = (int**)malloc(maxMask * sizeof(int*));
    
    for (int i = 0; i < maxMask; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
        parent[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            dp[i][j] = INT_MAX;
            parent[i][j] = -1;
        }
    }
    
    // Start from node 0
    dp[1][0] = 0;
    
    for (int mask = 1; mask < maxMask; mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i)) || dp[mask][i] == INT_MAX) continue;
            
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;
                
                int newMask = mask | (1 << j);
                int cost = abs(i - nums[j]);
                
                if (dp[mask][i] + cost < dp[newMask][j]) {
                    dp[newMask][j] = dp[mask][i] + cost;
                    parent[newMask][j] = i;
                }
            }
        }
    }
    
    // Find minimum cost
    int fullMask = maxMask - 1;
    int minCost = INT_MAX;
    int lastNode = -1;
    
    for (int i = 0; i < n; i++) {
        int totalCost = dp[fullMask][i] + abs(i - nums[0]);
        if (totalCost < minCost) {
            minCost = totalCost;
            lastNode = i;
        }
    }
    
    // Reconstruct path
    int* path = (int*)malloc(n * sizeof(int));
    int pathLen = 0;
    int mask = fullMask;
    int current = lastNode;
    
    while (current != -1) {
        path[pathLen++] = current;
        int prev = parent[mask][current];
        mask ^= (1 << current);
        current = prev;
    }
    
    // Reverse path
    for (int i = 0; i < pathLen / 2; i++) {
        int temp = path[i];
        path[i] = path[pathLen - 1 - i];
        path[pathLen - 1 - i] = temp;
    }
    
    // Free memory
    for (int i = 0; i < maxMask; i++) {
        free(dp[i]);
        free(parent[i]);
    }
    free(dp);
    free(parent);
    
    return path;
}

int main() {
    char buffer[1000];
    fgets(buffer, sizeof(buffer), stdin);
    
    // Parse array
    int nums[20];
    int count = 0;
    char* ptr = buffer + 1;
    while (*ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9') {
            nums[count++] = atoi(ptr);
            while (*ptr >= '0' && *ptr <= '9') ptr++;
        } else {
            ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(nums, count, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 2ⁿ)

For each of 2^n bitmask states and n positions, we try n next positions

⚠ Quadratic Growth

Space Complexity

O(n × 2ⁿ)

DP table stores cost for each (position, visited_mask) state

⚡ Linearithmic Space

6.8K Views

Medium Frequency

~35 min Avg. Time

180 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler