Watch 10 video solutions for Count the Number of Computer Unlocking Permutations, a medium level problem involving Array, Math, Brainteaser. This walkthrough by codestorywithMIK has 4,947 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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])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:
complexity[0] < complexity[1].complexity[1] < complexity[2].complexity[0] < complexity[2].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 <= 1051 <= complexity[i] <= 109Problem Overview: You are given n computers and rules that restrict the order in which they can be unlocked. The task is to count how many permutations of computers produce a valid unlocking sequence. Instead of simulating every order, the key is recognizing that the constraints reduce the problem to counting valid permutations using combinatorics.
Approach 1: Brute Force Permutation Enumeration (O(n!))
The most direct idea is to generate every permutation of the n computers and check whether the order satisfies the unlocking rule. This uses standard permutation generation (backtracking or next permutation) and validates each order step‑by‑step. While conceptually simple, the runtime grows as O(n!) and space is O(n) for recursion or permutation storage. This approach is only useful for understanding the constraints on valid orders and quickly becomes infeasible even for moderate values of n.
Approach 2: Combinatorics / Brain Teaser (O(n) time, O(1) space)
The unlocking constraint creates a structure where certain computers must appear before others in the permutation. Instead of generating permutations, count the number of valid placements directly. Treat the unlocking process as progressively adding computers to the sequence while maintaining the rule. At each step, only a limited number of positions remain valid, which leads to a multiplicative counting formula. The final answer becomes a closed‑form product involving factorial or permutation terms.
This works because permutations with ordering constraints can be counted using combinatorial reasoning rather than explicit enumeration. You iterate from 1 to n, multiply the number of valid choices at each step, and compute the result using standard math and combinatorics techniques. The algorithm runs in O(n) time if you compute the product iteratively, and uses O(1) extra space.
Recommended for interviews: Interviewers expect the combinatorics insight. Brute force shows you understand the problem but fails scalability constraints. The brain‑teaser solution demonstrates the ability to translate ordering constraints into permutation counting using array reasoning and combinatorial formulas.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Check | O(n!) | O(n) | For understanding constraints or very small n |
| Combinatorics / Brain Teaser Formula | O(n) | O(1) | Optimal approach for large n using permutation counting |