#3109 - Find the Index of Permutation

Medium • View on LeetCode • View on GitHub

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

Problem Description

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 of the permutations of [1, 2, ..., n].

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

Solution

/**
 * @param {number[]} perm
 * @return {number}
 */
var getPermutationIndex = function(perm) {
  const smallerToRight = perm.map(() => 0);

  mergeSort(0, perm.length - 1);

  const MOD = 10 ** 9 + 7;
  const factorials = computeFactorials(perm.length);

  return perm.reduce((total, _, i) => {
    return (total + smallerToRight[i] * factorials[perm.length - 1 - i]) % MOD;
  }, 0);

  function mergeSort(left, right) {
    if (left >= right) return [left];

    const mid = (left + right) >> 1;
    const leftIndices = mergeSort(left, mid);
    const rightIndices = mergeSort(mid + 1, right);
    const merged = [];
    let [leftPointer, rightPointer] = [0, 0];

    while (leftPointer < leftIndices.length || rightPointer < rightIndices.length) {
      if (rightPointer === rightIndices.length
         || (leftPointer < leftIndices.length
            && perm[leftIndices[leftPointer]] < perm[rightIndices[rightPointer]])) {
        smallerToRight[leftIndices[leftPointer]] += rightPointer;
        merged.push(leftIndices[leftPointer++]);
      } else {
        merged.push(rightIndices[rightPointer++]);
      }
    }

    return merged;
  }

  function computeFactorials(n) {
    const MOD = 10n ** 9n + 7n;
    const factorials = [1n, 1n];

    for (let i = 2n; i <= BigInt(n); i++) {
      factorials.push(i * factorials[factorials.length - 1] % MOD);
    }

    return factorials.map(val => parseInt(val));
  }
};