3577. Count the Number of Computer Unlocking Permutations

Problem Description

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 $10^9 + 7$ .

Note that the password for the computer with label 0 is decrypted, and not the computer with the first position in the permutation.

Explanation:

The problem provides an array representing the complexity of each computer’s password.
Only computer 0 is initially unlocked.
Each computer i > 0 can only be unlocked after at least one computer with both a smaller label (j < i) and a strictly smaller complexity (complexity[j] < complexity[i]) is unlocked.
The task is to find how many unlocking orders (permutations) are possible, subject to the above constraint, modulo $10^9 + 7$ .

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

First, notice that since computer 0 is the only one that is initially unlocked, every other computer must eventually be unlocked by something that traces back to computer 0. For computer i to be unlocked, there must be a previously unlocked computer j < i with a strictly lower complexity value.

If any complexity[i] is less than or equal to complexity[0], then computer 0 cannot unlock computer i (since its complexity would not be lower), and since j must be less than i, there is no earlier computer with lower complexity, making it impossible.

If all other computers have greater complexity than complexity[0], then, for any computer, the possible choices for which computer unlocked it are always present in the set of already unlocked computers. This means the ordering only has to ensure computer 0 goes first, and all other computers can be placed in any order. So, the total number of valid permutations is (n - 1)!.

Solution Approach

The solution starts by checking a necessary condition: for every computer i > 0, it must have complexity[i] > complexity[0]. If not, it's impossible to unlock that computer, so we return 0 immediately.

If the above condition is satisfied, computer 0 can always be used (directly or indirectly) to unlock any other computer, because 0 is always among the already unlocked computers for every step. That means, after ensuring the computers with higher complexities, the unlocking process imposes no additional restrictions.

So, after unlocking computer 0, there are n-1 computers left. These can be unlocked in any possible order, since the rules are always satisfied. The number of ways to permute the remaining n-1 computers is (n-1)!.

To compute this efficiently, loop through indices from 1 to n-1:

If complexity[i] <= complexity[0], return 0.
Otherwise, multiply the answer by i for each position (this calculates (n-1)! using a loop).
Since the answer could become very large, take the result modulo 10^9 + 7 at each step.

This approach uses a simple for-loop and multiplication. No advanced data structures are needed; only an integer accumulator and the modulus operation are used for efficiency.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach:

Suppose complexity = [1, 3, 5], so n = 3.

Let's walk through the steps:

Check the Necessary Condition
- Computer 1: complexity[1] = 3 > 1 = complexity[0]. Condition satisfied.
- Computer 2: complexity[2] = 5 > 1 = complexity[0]. Condition satisfied.
All computers (other than 0) have a higher complexity than 0. Conclusion: Every computer can (directly or via a chain) be unlocked after computer 0. The only requirement is that computer 0 is unlocked first.
Counting Valid Permutations
- We can arrange the other n - 1 = 2 computers (1 and 2) in any order.
- The number of valid permutations is (n - 1)! = 2! = 2.
Possible Orders
- [0, 1, 2]: Unlock computer 1 after 0, then 2.
- [0, 2, 1]: Unlock computer 2 after 0, then 1.
Result
- The answer is 2 (modulo $10^9 + 7$ ).

Let's see what happens if the condition is violated:

Suppose complexity = [4, 2, 6].

Computer 1: complexity[1] = 2 < 4 = complexity[0]. This is NOT allowed according to the rule. Computer 1 cannot be unlocked.
Result: The answer is 0.

Key Takeaway: Check all complexity[i] > complexity[0] for i > 0. If satisfied, output (n-1)!; otherwise, output 0.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countPermutations(self, complexity: List[int]) -> int:
5        mod = 10**9 + 7  # Define the modulus for the answer to prevent overflow
6        ans = 1  # Initialize answer
7
8        # Iterate from the second element to the last
9        for i in range(1, len(complexity)):
10            # If any element is less than or equal to the first element, return 0
11            if complexity[i] <= complexity[0]:
12                return 0
13
14            # Multiply the current answer by i and take modulus
15            ans = ans * i % mod
16
17        return ans  # Return the final answer
18

1class Solution {
2    public int countPermutations(int[] complexity) {
3        // Modulo value to prevent overflow
4        final int MOD = (int) 1e9 + 7;
5
6        // Initialize answer to 1, since factorial starts from 1
7        long ans = 1;
8
9        // Iterate over complexity array starting from index 1
10        for (int i = 1; i < complexity.length; ++i) {
11            // If current complexity is less than or equal to the first element, no valid permutations
12            if (complexity[i] <= complexity[0]) {
13                return 0;
14            }
15            // Multiply by current index (number of ways to permute so far)
16            ans = (ans * i) % MOD;
17        }
18        // Return the final answer cast to int
19        return (int) ans;
20    }
21}
22

1class Solution {
2public:
3    int countPermutations(std::vector<int>& complexity) {
4        // Define modulo for the answer
5        const int MOD = 1e9 + 7;
6        long long ans = 1;
7        int n = complexity.size();
8        // Check that each subsequent complexity is greater than the first
9        for (int i = 1; i < n; ++i) {
10            if (complexity[i] <= complexity[0]) {
11                // If not, return 0 as no valid permutations exist
12                return 0;
13            }
14            // Multiply ans by current index (i), modulo MOD
15            ans = (ans * i) % MOD;
16        }
17        // Return the total count of valid permutations
18        return static_cast<int>(ans);
19    }
20};
21

1/**
2 * Calculates the number of valid permutations where for every i > 0,
3 * complexity[i] > complexity[0]. Returns 0 if any complexity[i] <= complexity[0].
4 * @param complexity Array of complexity values.
5 * @returns Number of valid permutations modulo 10^9 + 7.
6 */
7function countPermutations(complexity: number[]): number {
8    const MOD = 1_000_000_007; // Modulo value for large numbers
9    let result = 1; // Store the result (number of valid permutations)
10
11    // Iterate through the array starting from the second element
12    for (let i = 1; i < complexity.length; i++) {
13        // If any complexity[i] is not strictly greater than complexity[0], return 0
14        if (complexity[i] <= complexity[0]) {
15            return 0;
16        }
17        // Multiply the result by i, modulo MOD, for valid positions
18        result = (result * i) % MOD;
19    }
20
21    return result;
22}
23

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the complexity array, because the code iterates through the array once in a for loop.

The space complexity is O(1), as only a constant amount of additional space is used for variables like mod and ans.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls