Find the index of permutation

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

36.4% acceptance

Mar 31, 2026

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

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_permutation_index(perm: Vec<i32>) -> i32 {
    let n = perm.len();
    let modp: i64 = 1_000_000_007;
    let mut fact = vec![1i64; n + 1];
    for i in 1..=n {
      fact[i] = fact[i - 1] * i as i64 % modp;
    }
    let mut bit = vec![0i32; n + 2];
    let update = |bit: &mut Vec<i32>, mut i: usize, val: i32| {
      while i <= n {
        bit[i] += val;
        i += i & i.wrapping_neg();
      }
    };
    let query = |bit: &Vec<i32>, mut i: usize| -> i32 {
      let mut s = 0;
      while i > 0 {
        s += bit[i];
        i -= i & i.wrapping_neg();
      }
      s
    };
    for i in 1..=n {
      update(&mut bit, i, 1);
    }
    let mut result = 0i64;
    for i in 0..n {
      let v = perm[i] as usize;
      let cnt = query(&bit, v - 1) as i64;
      result = (result + cnt % modp * fact[n - 1 - i] % modp) % modp;
      update(&mut bit, v, -1);
    }
    result as i32
  }
}