Count the Number of Computer Unlocking Permutations solution and explanation
Google
9 more videos on this problem
Count the Number of Computer Unlocking Permutations | Simplest Explanation | Leetcode 3577 | MIKcodestorywithMIK · 20:10 · 5K views
Count the Number of Computer Unlocking Permutations | LeetCode 3577 | Complete Intuition ExplainedSanyam IIT Guwahati · 14:00 · 1K views
Count the Number of Computer Unlocking Permutations 🔥 Leetcode 3577 | Optimal Approach Study Placement · 12:42 · 862 views
3577. Count the Number of Computer Unlocking Permutations | Leetcode Daily - PythonLeetcode Daily · 9:39 · 620 views
3577. Count the Number of Computer Unlocking Permutations | Weekly 453 | 2nd ProblemTech Courses · 5:51 · 510 views
Daily Leetcode #2080: Dec 10, 2025 - 3577. Count the Number of Computer Unlocking PermutationsProgramming Live with Larry · 10:17 · 407 views
3577. Count the Number of Computer Unlocking Permutations (Leetcode Medium)Programming Live with Larry · 9:25 · 406 views
Count the Number of Computer Unlocking Permutations | LeetCode 3577 - Pythonimpoldev · 7:55 · 253 views
Count the Number of Computer Unlocking Permutations | LeetCode 3577 | Java Code | Developer CoderDeveloper Coder · 20:37 · 138 views
LeetCode 3577 – Count the Number of Computer Unlocking Permutations | Full Explanation + Edge CasesTeeLCode · 9:37 · 132 views
The problem
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:
- You can decrypt the password for the computer
iusing the password for computerj, wherejis any integer less thaniwith a lower complexity. (i.e.j < iandcomplexity[j] < complexity[i]) - To decrypt the password for computer
i, you must have already unlocked a computerjsuch thatj < iandcomplexity[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:
- [0, 1, 2]
- Unlock computer 0 first with root password.
- Unlock computer 1 with password of computer 0 since
complexity[0] < complexity[1]. - Unlock computer 2 with password of computer 1 since
complexity[1] < complexity[2].
- [0, 2, 1]
- Unlock computer 0 first with root password.
- Unlock computer 2 with password of computer 0 since
complexity[0] < complexity[2]. - Unlock computer 1 with password of computer 0 since
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] <= 109
Approach overview
Problem 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.
Solution
Since the password for computer number 0 is already unlocked, for any other computer i, if complexity[i] leq 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.
The time complexity is O(n), where n is the length of the complexity array. The space complexity is O(1).
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 ansclass Solution {
public int countPermutations(int[] complexity) {
final int mod = (int) 1e9 + 7;
long ans = 1;
for (int i = 1; i < complexity.length; ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
ans = ans * i % mod;
}
return (int) ans;
}
}class Solution {
public:
int countPermutations(vector<int>& complexity) {
const int mod = 1e9 + 7;
long long ans = 1;
for (int i = 1; i < complexity.size(); ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
ans = ans * i % mod;
}
return ans;
}
};function countPermutations(complexity: number[]): number {
const mod = 1e9 + 7;
let ans = 1;
for (let i = 1; i < complexity.length; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
ans = (ans * i) % mod;
}
return ans;
}public class Solution {
public int CountPermutations(int[] complexity) {
const int mod = (int) 1e9 + 7;
long ans = 1;
for (int i = 1; i < complexity.Length; ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
ans = ans * i % mod;
}
return (int) ans;
}
}func countPermutations(complexity []int) int {
mod := int64(1e9 + 7)
ans := int64(1)
for i := 1; i < len(complexity); i++ {
if complexity[i] <= complexity[0] {
return 0
}
ans = ans * int64(i) % mod
}
return int(ans)
}impl Solution {
pub fn count_permutations(complexity: Vec<i32>) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut ans = 1i64;
for i in 1..complexity.len() {
if complexity[i] <= complexity[0] {
return 0;
}
ans = ans * i as i64 % MOD;
}
ans as i32
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Count the Number of Computer Unlocking Permutations easy or hard?
The problem is rated Medium because the implementation is simple once the pattern is recognized, but discovering the combinatorics insight can be tricky. Candidates who attempt brute force often miss the key observation that the answer can be derived mathematically.
Count the Number of Computer Unlocking Permutations Python/Java solution
The typical implementation computes the combinatorial product directly. In Python, Java, C++, Go, or other languages, iterate from 1 to n and multiply the number of valid choices at each step. The code is short because the heavy lifting comes from the mathematical insight rather than data structures.
How to solve Count the Number of Computer Unlocking Permutations in O(n)?
Observe that the unlocking constraints limit where each computer can appear in the sequence. Instead of constructing permutations, count how many valid choices exist at each step and multiply them together. Iterating from 1 to n while updating the result gives an O(n) solution with constant extra space.
What is the best approach for Count the Number of Computer Unlocking Permutations?
The best approach uses combinatorics. Instead of generating every permutation, analyze the ordering constraints and derive a counting formula for valid unlock sequences. This reduces the problem to computing a multiplicative expression (often factorial-based) in O(n) time and O(1) space.
Is Count the Number of Computer Unlocking Permutations asked at Google/Amazon/Meta?
Problems involving permutation counting and combinatorics frequently appear in interviews at companies like Google, Amazon, and Meta. Variants typically test whether candidates can convert ordering constraints into mathematical counting instead of brute-force permutation generation.
What data structure is used in Count the Number of Computer Unlocking Permutations?
The optimal solution does not rely on complex data structures. It primarily uses basic variables and arithmetic operations with combinatorics formulas. Arrays may appear only for representing the initial inputs or constraints.
What is the time complexity of Count the Number of Computer Unlocking Permutations?
The optimal combinatorics solution runs in O(n) time because it iteratively computes a product or factorial-based expression for n computers. Space complexity is O(1) since only a few variables are needed. A naive brute-force permutation approach would take O(n!) time and is not practical.