Question

Approach

I observe that for any index i > 0 to be unlockable there must exist some j < i with complexity[j] < complexity[i]. In particular j = 0 is always a candidate, so a sufficient (and in fact necessary) condition for all i > 0 to be unlockable is that complexity[0] is strictly smaller than every other complexity. If any i > 0 has complexity[i] <= complexity[0] then i has no earlier index with strictly smaller complexity and the task is impossible (answer 0). If complexity[0] is strictly the global minimum, then initially only computer 0 is unlocked but it can be used to unlock any other computer (since 0 < i and complexity[0] < complexity[i]), so the remaining n-1 computers can be unlocked in any order. Hence the number of valid permutations is (n-1)! modulo 10^9+7.

Implementation

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(complexity)

        base = complexity[0]
        for i in range(1, n):
            if complexity[i] <= base:
                return 0
        
        ans = 1
        for x in range(1, n):
            ans = (ans * x) % MOD
        return ans

Complexities

• Time: O(n)
• Space: O(1)