Skip to main content
Talentd

Count the Number of Computer Unlocking Permutations - Solution & Explanation

MediumArrayMathBrainteaserCombinatorics7 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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 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])
  • To decrypt the password for computer 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:

  • [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 <= 105
  • 1 <= 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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Permutation CheckO(n!)O(n)For understanding constraints or very small n
Combinatorics / Brain Teaser FormulaO(n)O(1)Optimal approach for large n using permutation counting

Video Solution

Count the Number of Computer Unlocking Permutations | Simplest Explanation | Leetcode 3577 | MIK • codestorywithMIK • 5,075 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Computer Unlocking Permutations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Clumsy Factorial