// Time: O(n^2) // Space: O(n) class Solution { public: /** * @param A an integer array * @return a long integer */ long long permutationIndexII(vector& A) { long long index = 1; // Position 1 is paired with factor 0 and so is skipped. int position = 2; long long factor = 1; map number_to_count; ++number_to_count[A.back()]; for (int i = static_cast(A.size()) - 2; i >= 0; --i) { ++number_to_count[A[i]]; for (const auto& kvp : number_to_count) { if (kvp.first >= A[i]) { break; } index += factor * kvp.second / number_to_count[A[i]]; } factor = factor * position / number_to_count[A[i]]; ++position; } return index; } }; // Time: O(n^2) // Space: O(n) class Solution2 { public: /** * @param A an integer array * @return a long integer */ long long permutationIndexII(vector& A) { long long index = 1; // Position 1 is paired with factor 0 and so is skipped. int position = 2; long long factor = 1; unordered_map number_to_count; ++number_to_count[A.back()]; for (int i = static_cast(A.size()) - 2; i >= 0; --i) { unordered_map successor_to_count; ++number_to_count[A[i]]; for (int j = i + 1; j < A.size(); ++j) { if (A[i] > A[j]) { ++successor_to_count[A[j]]; } } for (const auto& kvp : successor_to_count) { index += factor * kvp.second / number_to_count[A[i]]; } factor = factor * position / number_to_count[A[i]]; ++position; } return index; } }; // Time: O(n^3) // Space: O(n) class Solution3 { public: /** * @param A an integer array * @return a long integer */ long long permutationIndexII(vector& A) { long long index = 1; unordered_map number_to_count; ++number_to_count[A.back()]; for (int i = static_cast(A.size()) - 2; i >= 0; --i) { unordered_map successor_to_count; ++number_to_count[A[i]]; for (int j = i + 1; j < A.size(); ++j) { if (A[i] > A[j]) { ++successor_to_count[A[j]]; } } for (const auto& kvp : successor_to_count) { --number_to_count[kvp.first]; index += combination(number_to_count); ++number_to_count[kvp.first]; } } return index; } long long combination(const unordered_map& number_to_count) { int n = 0; for (const auto& kvp : number_to_count) { n += kvp.second; } long long count = 1; for (const auto& kvp : number_to_count) { // C(n, k) = (n) / 1 * (n - 1) / 2 ... * (n - k + 1) / k for (int i = 1; i <= kvp.second; ++i, --n) { count = count * n / i; } } return count; } };

Problem