# Count the Number of Computer Unlocking Permutations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-computer-unlocking-permutations)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-computer-unlocking-permutations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Array
---
## Problem
You are given an array `complexity` of length `n`.

There are `n` **locked** computers in a room with labels from 0 to `n - 1`, each with its own **unique** password. The password of the computer `i` has a complexity `complexity[i]`.

The password for the computer labeled 0 is **already** decrypted and serves as the root. All other computers must be unlocked using it or another previously unlocked computer, following this information:

* You can decrypt the password for the computer `i` using the password for computer `j`, where `j` is **any** integer less than `i` with a lower complexity. (i.e. `j < i` and `complexity[j] < complexity[i]`)
* To decrypt the password for computer `i`, you must have already unlocked a computer `j` such that `j < i` and `complexity[j] < complexity[i]`.

Find the number of permutations of `[0, 1, 2, ..., (n - 1)]` that represent a valid order in which the computers can be unlocked, starting from computer 0 as the only initially unlocked one.

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

**Note** that the password for the computer **with label** 0 is decrypted, and _not_ the computer with the first position in the permutation.

**Example 1:**

**Input:** complexity = \[1,2,3\]

**Output:** 2

**Explanation:**

The valid permutations are:

* \[0, 1, 2\]  
  * Unlock computer 0 first with root password.
  * Unlock computer 1 with password of computer 0 since `complexity[0] < complexity[1]`.
  * Unlock computer 2 with password of computer 1 since `complexity[1] < complexity[2]`.
* \[0, 2, 1\]  
  * Unlock computer 0 first with root password.
  * Unlock computer 2 with password of computer 0 since `complexity[0] < complexity[2]`.
  * Unlock computer 1 with password of computer 0 since `complexity[0] < complexity[1]`.

**Example 2:**

**Input:** complexity = \[3,3,3,4,4,4\]

**Output:** 0

**Explanation:**

There are no possible permutations which can unlock all computers.

**Constraints:**

* `2 <= complexity.length <= 105`
* `1 <= complexity[i] <= 109`

# Approaches
## Brute Force / Naive O(N^2) Approach
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`.
**Time:** O(N^2) due to nested loops for the preliminary check, calculation of `m`, and the main product calculation. · **Space:** O(N) to store the minimum prerequisite complexities `m`.
**Pros:** The logic is relatively straightforward to understand and implement.; It correctly solves the problem for smaller values of `n`.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), and will result in a Time Limit Exceeded (TLE) error.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
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`.

## Optimized O(N log N) Approach
This approach follows the same combinatorial formula as the O(N^2) solution but optimizes every computational step using advanced data structures and algorithms. The key idea is to rephrase the counting and minimum-finding problems as geometric range queries, which can be solved much faster than with naive loops. By using techniques like coordinate compression, Fenwick trees (or segment trees), and offline processing (sweep-line algorithm), we can reduce the time complexity of each major step to O(N log N), making the overall solution efficient enough to pass the given constraints.
**Time:** O(N log N) dominated by coordinate compression and the optimized calculations of `m_k` and `|K_i|`. · **Space:** O(N) for storing `m`, `|K_i|`, and for the data structures like Fenwick Tree or Segment Tree.
**Pros:** Highly efficient with O(N log N) time complexity, which passes the given constraints.; Demonstrates deep knowledge of advanced data structures and algorithmic techniques.
**Cons:** The implementation is significantly more complex, requiring advanced data structures and algorithms like coordinate compression, Fenwick trees, and offline processing.; Debugging can be challenging due to the multiple intricate parts.
### Explanation
The overall formula remains `ans = product_{i=1 to n-1} (i - |K_i|)`. We optimize the computation of `m_k` and `|K_i|`.

**1. Computing `m_k` and `size_k` in O(N log N):**
We first coordinate compress the `complexity` values. Then, we iterate through computers `k` sorted by `complexity[k]`. We use a segment tree over indices `j 	< k`. When processing `k`, all computers `j` processed so far have `complexity[j] <= complexity[k]`. We query the segment tree for `min(complexity[j])` and `count(j)` over the range `[0, k-1]` to find `m_k` and `size_k`. After processing all computers with the same complexity as `k`, we update the segment tree with their information. This computes all `m_k` and `size_k` in O(N log N).

**2. Computing `|K_i|` for all `i` in O(N log N):**
This is the most complex part. We need to find `|{k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}|` for each `i`. This is a set of 3D counting queries. We can solve this with a sweep-line algorithm.

- Create a list of all `complexity` and `m` values, then coordinate compress them.
- Create two lists of events: `points` and `queries`. 
  - `points`: For each `k` from `0` to `n-1`, add `(complexity[k], m[k], k)`.
  - `queries`: For each `i` from `1` to `n-1`, add `(complexity[i], i)`.
- Sort both `points` and `queries` by complexity in descending order.
- Use a Fenwick Tree (BIT) on indices `[0, ..., n-1]`.
- Use two pointers, one for `points` (`p_ptr`) and one for `queries` (`q_ptr`). Iterate through `queries`.
- For each query `(C, i)`:
  - Advance `p_ptr` to add all points `(c_p, m_p, k_p)` where `c_p >= C` to a temporary structure, grouped by `m_p`.
  - This is still complex. A better offline approach is to combine points and queries and sort by the main coordinate.
  - Let's sweep on the index `t` from `0` to `n-1`. We need a 2D data structure to handle queries on `(complexity, m)`. A persistent segment tree can solve this in O(N log N). At each step `t`, we update the persistent segment tree with the point `(complexity[t], m[t])` and for any query `i=t`, we use the tree's state to answer the 2D range query.

```java
// The O(N log N) solution is highly complex to implement from scratch.
// The following is a conceptual representation of the logic.
// A full implementation would require helper classes for Fenwick Tree/Segment Tree,
// coordinate compression, and careful offline event handling.

class Solution {
    public int countPermutations(int[] complexity) {
        // High-level logic for an O(N log N) solution
        int n = complexity.length;
        long MOD = 1_000_000_007;

        // 1. Coordinate compress complexity values. O(N log N)

        // 2. Compute size[i] and m[i] for all i in O(N log N)
        //    using a Fenwick/Segment tree and processing computers sorted by complexity.
        //    If any size[i] == 0 for i > 0, return 0.
        long[] m = new long[n]; // Assume m is computed
        // ... computation of m ...

        // 3. Compute |K_i| for all i in O(N log N)
        //    This is a 3D counting problem: count k < i s.t. c[k] >= c[i] and m[k] >= c[i].
        //    Can be solved with a sweep-line algorithm or a persistent segment tree.
        //    Let's assume `countsKi` array is populated with |K_i| values.
        int[] countsKi = new int[n]; // Assume this is computed
        // ... computation of countsKi ...

        // 4. Final calculation
        long ans = 1;
        for (int i = 1; i < n; i++) {
            long choices = i - countsKi[i];
            ans = (ans * choices) % MOD;
        }

        return (int) ans;
    }
}
```
*Note: A full, correct O(N log N) implementation is very advanced. The provided snippet illustrates the high-level structure, as the details of the data structures are extensive.*
### Algorithm
1. **Coordinate Compression**: The complexities can be large, but only their relative order matters. We gather all unique complexity values, sort them, and map each to a smaller integer rank. This takes O(N log N).
2. **Optimized Prerequisite Calculation**: We can calculate `size[i]` (number of prerequisites for `i`) and `m[i]` (minimum complexity of prerequisites for `i`) for all `i` efficiently. We process computers sorted by their complexity. We use a data structure like a Segment Tree or Fenwick Tree (BIT) over the computer indices `[0, ..., n-1]`. When processing computer `i`, we query the data structure for information about computers `j < i` that have already been processed (i.e., have smaller complexity). This allows computing all `size[i]` and `m[i]` values in O(N log N) time. During this step, we also perform the preliminary check: if `size[i] == 0` for any `i > 0`, return 0.
3. **Optimized `|K_i|` Calculation**: The main bottleneck is calculating `|K_i| = |{k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}|` for all `i`. This is a series of 2D range counting problems. We can solve this efficiently in O(N log N) using an offline approach with a Fenwick Tree (BIT).
    - Create events for points and queries. Points are `(k, complexity[k], m[k])`. Queries are `(i, complexity[i])`.
    - We need to count points `k` such that `k < i`, `complexity[k] >= complexity[i]`, and `m[k] >= complexity[i]`.
    - We can process all points and queries offline. Let's create events based on the complexity values. We group points and queries by their complexity `C`. We iterate through `C` in descending order.
    - We use a BIT on the indices `[0, ..., n-1]`. When processing complexity `C`, we first add all points `k` with `complexity[k] == C` to another data structure (e.g., lists grouped by `m[k]`). Then, we add points `k` with `m[k] == C` to our BIT at index `k`. Finally, for all queries `i` with `complexity[i] == C`, we query the BIT for the sum up to `i-1`. This gives us the count `|K_i|`.
4. **Final Calculation**: With all `|K_i|` values computed, we calculate the final answer `ans = product_{i=1 to n-1} (i - |K_i|)` in O(N) time.