#3577

Medium

LeetCode Problem Workspace

Count the Number of Computer Unlocking Permutations

Calculate the total valid unlocking sequences for computers based on their complexity using array and combinatorics logic patterns.

array math brainteaser combinatorics

Problem Statement

You are given an array complexity of length n representing n locked computers labeled from 0 to n - 1. Each computer i has a password of complexity complexity[i], and only computer 0 is initially unlocked as the root. All other computers can only be unlocked if there is at least one previously unlocked computer with strictly lower complexity.

Calculate the total number of valid permutations of unlocking all computers. A permutation is valid if each computer is unlocked after at least one computer with lower complexity is unlocked. Return 0 if no valid permutation exists. For example, if complexity contains duplicates preventing any unlocking order beyond computer 0, the result is 0.

Examples

Example 1

Input: complexity = [1,2,3]

Output: 2

The valid permutations are:

Example 2

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

Output: 0

There are no possible permutations which can unlock all computers.

Constraints

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

Solution Approach

Sort complexities and verify root uniqueness

Sort the complexity array to ensure the first element is the unique minimum. If another element shares this minimum, return 0 immediately, as unlocking beyond the root becomes impossible.

Count available unlock options for each computer

Iterate over the sorted array and compute for each computer how many unlocked computers with lower complexity exist. Multiply these counts to get the total number of valid permutations, ensuring array access respects complexity constraints.

Apply modular arithmetic to handle large results

Since the number of permutations can be huge, perform all multiplication steps under a large prime modulus (e.g., 10^9 + 7). This preserves numerical stability while maintaining correct combinatorial counts.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting the array, giving O(n log n), and iterating to count unlock options adds O(n), resulting in overall O(n log n). Space complexity is O(1) additional or O(n) if storing sorted indices separately.

What Interviewers Usually Probe

Check if the root has the unique minimum complexity early.
Consider how duplicate complexities prevent unlocking sequences.
Expect the candidate to combine array traversal with combinatorial counting.

Common Pitfalls or Variants

Common pitfalls

Not verifying that the first computer is the unique minimum complexity.
Incorrectly counting unlock options for computers with equal complexity.
Ignoring modulus arithmetic, leading to integer overflow on large arrays.

Follow-up variants

Allow unlocking only if complexity difference is at most k.
Count permutations where root is not fixed at index 0.
Consider circular unlocking order constraints instead of linear sequence.

FAQ

What is the main pattern in Count the Number of Computer Unlocking Permutations?

The problem combines array ordering with combinatorial counting, requiring careful tracking of unlocked computers for valid sequences.

How do I handle duplicate complexities in this problem?

If duplicates include the minimum complexity, unlocking beyond the root is impossible, so the solution must return 0.

What is the time complexity for solving this problem efficiently?

Sorting the array takes O(n log n), and computing the product of available options is O(n), resulting in O(n log n) total time.

Why do I need modular arithmetic here?

The number of permutations can be extremely large, so using modulus like 10^9 + 7 prevents integer overflow and keeps results correct.

Can the root computer be other than index 0?

The canonical solution fixes the root at index 0, which must be the unique minimum to allow all other computers to unlock correctly.

terminal

Solution

Solution 1: Brain Teaser

Since the password for computer number $0$ is already unlocked, for any other computer $i$, if $\text{complexity}[i] \leq \text{complexity}[0]$, it is impossible to unlock computer $i$, so we return $0$. Otherwise, any permutation is valid, and there are exactly $(n - 1)!$ possible permutations.

1

2

3

4

5

6

7

8

9

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        mod = 10**9 + 7
        ans = 1
        for i in range(1, len(complexity)):
            if complexity[i] <= complexity[0]:
                return 0
            ans = ans * i % mod
        return ans

Continue Practicing

#3539 find sum of array product of magical sequences #3470 permutations iv #3428 maximum and minimum sums of at most size k subsequences