Count the Number of Computer Unlocking Permutations

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 computer i has 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 these rules:

  • You can decrypt the password for computer i using the password for computer j, where j is any integer less than i with a lower complexity; that is, 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 10^9 + 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
Inputcomplexity = [1,2,3]
Output2
The valid unlocking orders are [0, 1, 2] and [0, 2, 1].
Example 2
Inputcomplexity = [3,3,3,4,4,4]
Output0
There are no possible permutations which can unlock all computers.

Constraints

  • 2 <= complexity.length <= 10^5
  • 1 <= complexity[i] <= 10^9

Asked at 3 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate