Find the Index of Permutation - Practice Coding Problems

Find the Index of Permutation - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Medium

Given an array perm of length n which is a permutation of [1, 2, ..., n], return the index of perm in the lexicographically sorted array of all permutations of [1, 2, ..., n].

Since the answer may be very large, return it modulo 10⁹ + 7.

Lexicographic order means dictionary order - for example, permutations of [1,2,3] in lexicographic order are: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Input & Output

Example 1 — Basic Case

$ Input: perm = [2,3,1]

› Output: 3

💡 Note: All permutations of [1,2,3] in lexicographic order: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The permutation [2,3,1] is at index 3.

Example 2 — First Permutation

$ Input: perm = [1,2]

› Output: 0

💡 Note: Permutations of [1,2] in order: [1,2], [2,1]. The permutation [1,2] is the first one, so index is 0.

Example 3 — Last Permutation

$ Input: perm = [3,2,1]

› Output: 5

💡 Note: The permutation [3,2,1] is the last permutation of [1,2,3] in lexicographic order, so it's at index 5.

Constraints

1 ≤ perm.length ≤ 1000
perm is a permutation of [1, 2, ..., n]

Visualization

Tap to expand

Understanding the Visualization

Input

Given permutation [2,3,1] of [1,2,3]

Process

Calculate position using factorial mathematics

Output

Return lexicographic index: 3

Key Takeaway

🎯 Key Insight: Use factorial mathematics to count permutations lexicographically without generating them all

Asked in

G Google 35 M Microsoft 28 a Amazon 22 F Facebook 18

The key insight is to use factorial mathematics instead of generating all permutations. For each position, count how many smaller unused numbers exist and multiply by the factorial of remaining positions. Best approach is the mathematical factorial calculation with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Permutations	O(n! × n)	O(n!)	Generate all permutations in lexicographic order and find the target
Mathematical Factorial Calculation	O(n²)	O(n)	Use factorial mathematics to calculate position without generating permutations

Brute Force - Generate All Permutations — Algorithm Steps

Generate all permutations of [1,2,...,n]
Sort them lexicographically
Find index of target permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all permutations of [1,2,3]

Sort Lexicographically

Order them like dictionary

Find Target

Locate our target permutation

Code -

solution.c — C

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

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int solution(int* perm, int n) {
    int* nums = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) nums[i] = i + 1;
    
    int totalPerms = factorial(n);
    int** allPerms = (int**)malloc(totalPerms * sizeof(int*));
    for (int i = 0; i < totalPerms; i++) {
        allPerms[i] = (int*)malloc(n * sizeof(int));
    }
    
    int count = 0;
    do {
        for (int i = 0; i < n; i++) {
            allPerms[count][i] = nums[i];
        }
        count++;
    } while (count < totalPerms);
    
    for (int i = 0; i < totalPerms; i++) {
        int match = 1;
        for (int j = 0; j < n; j++) {
            if (allPerms[i][j] != perm[j]) {
                match = 0;
                break;
            }
        }
        if (match) {
            for (int k = 0; k < totalPerms; k++) free(allPerms[k]);
            free(allPerms);
            free(nums);
            return i % (int)(1e9 + 7);
        }
    }
    
    for (int k = 0; k < totalPerms; k++) free(allPerms[k]);
    free(allPerms);
    free(nums);
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int perm[10];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        perm[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(perm, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, each taking O(n) time to create and compare

⚠ Quadratic Growth

Space Complexity

O(n!)

Store all n! permutations in memory

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Brute Force - Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler