Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every unlocking chain begins with computer zero and strictly increases complexity at each step. Therefore any other computer with complexity at most computer zero's can never be reached. Conversely, if all others have larger complexity, computer zero can unlock each of them directly because its index is also smaller.

Approach

Scan every computer after index zero. If its complexity is less than or equal to the first complexity, return zero immediately. Otherwise all remaining computers may be unlocked in any order after the initially unlocked computer zero, giving (n - 1)! permutations.

Return that factorial modulo 1,000,000,007 from the precomputed table. The strict comparison matters: equal complexity does not satisfy the unlocking rule. The factorial table is initialized once at module level, so its setup cost is separate from the per-call scan in the complexity analysis.

MOD = 10**9 + 7
MX = 10**5 + 1
fact = [1] * MX
for i in range(1, MX):
    fact[i] = (fact[i - 1] * i) % MOD

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        n = len(complexity)

        for i in range(1, n):
            if complexity[i] <= complexity[0]: return 0
        
        return fact[n - 1]

Complexity analysis

Let n = complexity.length and M = 100001 be the module table size. Per call, time is O(n) and auxiliary space is O(1). Module initialization takes O(M) time and persistent O(M) space for factorials.