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 Index of Permutation

Number: 3417

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a permutation array perm of length n (which is a permutation of [1, 2, ..., n]), the task is to return the index (0-indexed) of the given permutation in the lexicographically sorted list of all permutations. Since the answer may be very large, return it modulo (10^9 + 7).

Example 1: Input: perm = [1,2] Output: 0 Explanation: The lexicographically sorted list of permutations is [ [1,2], [2,1] ] and [1,2] appears at index 0.

Example 2: Input: perm = [3,1,2] Output: 4 Explanation: The lexicographically sorted list of permutations is [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] and [3,1,2] appears at index 4.

Key Insights

  • The lexicographic rank of a permutation can be determined by counting how many permutations would come before it.
  • For every position in the permutation, count the number of unused numbers smaller than the current number.
  • Multiply this count by the factorial of the number of remaining positions.
  • Use a data structure like a Binary Indexed Tree (Fenwick Tree) to efficiently count the number of unused numbers smaller than a given value.
  • Precompute factorials mod (10^9+7) to avoid recomputation and to handle the large numbers under modulo arithmetic.

Space and Time Complexity

Time Complexity: O(n log n) – O(n) iterations each doing BIT (Fenwick tree) operations in O(log n).
Space Complexity: O(n) – for the BIT and factorial precomputation arrays.

Solution

We first precompute factorials modulo (10^9+7) for numbers from 0 to n. Then, we initialize a Binary Indexed Tree (BIT) that keeps track of which numbers are still unused (initially every number from 1 to n is available). For each element in the permutation:

  1. Query the BIT to determine how many numbers less than the current element are still available.
  2. The contribution of the current element is (number of such unused numbers) * factorial(remaining positions) modulo (10^9+7).
  3. Update the BIT to mark the current element as used.
  4. Sum up all contributions to obtain the lexicographic index. This approach efficiently handles the computation even for large n.

Code Solutions

# Python solution using Binary Indexed Tree (Fenwick Tree)
MOD = 10**9 + 7

class BIT:
    # Binary Indexed Tree for range sum queries and point updates
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (size + 1)
        
    def update(self, index, delta):
        # Update BIT at position index by adding delta 
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index
            
    def query(self, index):
        # Query the prefix sum up to index
        result = 0
        while index:
            result += self.tree[index]
            index -= index & -index
        return result

def findPermutationIndex(perm):
    n = len(perm)
    # Precompute factorials mod MOD
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    # Initialize BIT with frequency of numbers 1..n (all 1's since all numbers available)
    bit = BIT(n)
    for i in range(1, n + 1):
        bit.update(i, 1)
    
    rank = 0
    # Process each element of the permutation
    for i in range(n):
        cur = perm[i]
        # Count numbers less than cur still available
        count_less = bit.query(cur - 1)
        # Add contribution: count_less * factorial of remaining positions
        rank = (rank + count_less * fact[n - i - 1]) % MOD
        # Mark current number as used
        bit.update(cur, -1)
    
    return rank

# Example usage
print(findPermutationIndex([3,1,2]))  # Expected output: 4
← Back to All Questions