Count the Number of Computer Unlocking Permutations

This approach is based on a combinatorial insight derived from building the permutation incrementally. We determine the number of valid permutations for computers {0, ..., i} based on the number of valid permutations for {0, ..., i-1}. The key is to find how many valid positions computer i can be inserted into a permutation of {0, ..., i-1}. This number turns out to be independent of the specific permutation and can be expressed as i - |K_i|, where K_i is the set of computers {k | k < i} that could potentially form a valid prefix of a permutation without needing any of i's prerequisites. The total number of permutations is then the product of these counts for i from 1 to n-1.

1. Preliminary Check: Iterate from i = 1 to n-1. For each i, check if there exists at least one j < i such that complexity[j] < complexity[i]. If this condition fails for any i, no computer i can ever be unlocked, so no full permutation is possible. Return 0.
2. Calculate Prerequisites: For each computer k from 0 to n-1, we need to find the minimum complexity among its prerequisites. Let's denote this as m[k]. A prerequisite j for k satisfies j < k and complexity[j] < complexity[k]. So, m[k] = min({complexity[j] | j < k and complexity[j] < complexity[k]}). If k has no prerequisites, we can consider m[k] to be infinity. This step takes O(n^2) time.
3. Iterative Calculation: The core idea is that the total number of valid permutations can be built iteratively. Let f(i) be the number of valid permutations for the first i computers {0, ..., i-1}. The number of permutations for {0, ..., i} can be found by determining the number of valid positions to insert computer i into any valid permutation of {0, ..., i-1}. It can be shown that this number of insertion spots is i - |K_i|, where K_i is a specific subset of computers {0, ..., i-1}.
4. Identify K_i: The set K_i consists of computers k < i that do not depend on any of i's prerequisites. Formally, K_i = {k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}. We calculate the size of this set, |K_i|, for each i from 1 to n-1.
5. Calculate Total Permutations: The final answer is the product of the number of choices at each step. Initialize ans = 1. Iterate i from 1 to n-1. In each step, calculate |K_i| by iterating k from 0 to i-1. The number of ways to place computer i is i - |K_i|. Update the answer: ans = (ans * (i - |K_i|)) % MOD. The total time complexity for this part is O(n^2).
6. Return Result: Return the final calculated ans.

The algorithm proceeds as follows:

First, we perform a basic check. For any computer i > 0 to be unlockable, it must have at least one prerequisite j < i with complexity[j] < complexity[i]. We can iterate through each i from 1 to n-1 and check if such a j exists. If not, we return 0. This check takes O(n^2).

Next, we define m[k] as the minimum complexity among all prerequisites of computer k. We can compute m[k] for all k from 0 to n-1 with a nested loop, which also takes O(n^2).

The main logic calculates the result ans as the product ans = product_{i=1 to n-1} (i - |K_i|). The set K_i is defined as {k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}. We can compute |K_i| for each i by iterating k from 0 to i-1 and checking the conditions. This nested loop structure results in an O(n^2) complexity for the main calculation.

class Solution {
    public int countPermutations(int[] complexity) {
        int n = complexity.length;
        long MOD = 1_000_000_007;

        // Preliminary check: O(n^2)
        for (int i = 1; i < n; i++) {
            boolean hasPrereq = false;
            for (int j = 0; j < i; j++) {
                if (complexity[j] < complexity[i]) {
                    hasPrereq = true;
                    break;
                }
            }
            if (!hasPrereq) {
                return 0;
            }
        }

        // Precompute m[k]: min complexity of prerequisites for k: O(n^2)
        long[] m = new long[n];
        for (int k = 0; k < n; k++) {
            m[k] = Long.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                if (complexity[j] < complexity[k]) {
                    m[k] = Math.min(m[k], complexity[j]);
                }
            }
        }

        long ans = 1;
        // Main calculation: O(n^2)
        for (int i = 1; i < n; i++) {
            int countKi = 0;
            for (int k = 0; k < i; k++) {
                if (complexity[k] >= complexity[i] && m[k] >= complexity[i]) {
                    countKi++;
                }
            }
            long choices = i - countKi;
            ans = (ans * choices) % MOD;
        }

        return (int) ans;
    }
}