Scale Engineer

Count the Number of Computer Unlocking Permutations

Med
#3185Time: O(N^2) due to nested loops for the preliminary check, calculation of `m`, and the main product calculation.Space: O(N) to store the minimum prerequisite complexities `m`.
Patterns
MathCombinatorics
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on a combinatorial insight derived from building the permutation incrementally. We determine the number of valid permutations for computers {0, ..., i} based on the number of valid permutations for {0, ..., i-1}. The key is to find how many valid positions computer i can be inserted into a permutation of {0, ..., i-1}. This number turns out to be independent of the specific permutation and can be expressed as i - |K_i|, where K_i is the set of computers {k | k < i} that could potentially form a valid prefix of a permutation without needing any of i's prerequisites. The total number of permutations is then the product of these counts for i from 1 to n-1.

Algorithm

  1. Preliminary Check: Iterate from i = 1 to n-1. For each i, check if there exists at least one j < i such that complexity[j] < complexity[i]. If this condition fails for any i, no computer i can ever be unlocked, so no full permutation is possible. Return 0.
  2. Calculate Prerequisites: For each computer k from 0 to n-1, we need to find the minimum complexity among its prerequisites. Let's denote this as m[k]. A prerequisite j for k satisfies j < k and complexity[j] < complexity[k]. So, m[k] = min({complexity[j] | j < k and complexity[j] < complexity[k]}). If k has no prerequisites, we can consider m[k] to be infinity. This step takes O(n^2) time.
  3. Iterative Calculation: The core idea is that the total number of valid permutations can be built iteratively. Let f(i) be the number of valid permutations for the first i computers {0, ..., i-1}. The number of permutations for {0, ..., i} can be found by determining the number of valid positions to insert computer i into any valid permutation of {0, ..., i-1}. It can be shown that this number of insertion spots is i - |K_i|, where K_i is a specific subset of computers {0, ..., i-1}.
  4. Identify K_i: The set K_i consists of computers k < i that do not depend on any of i's prerequisites. Formally, K_i = {k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}. We calculate the size of this set, |K_i|, for each i from 1 to n-1.
  5. Calculate Total Permutations: The final answer is the product of the number of choices at each step. Initialize ans = 1. Iterate i from 1 to n-1. In each step, calculate |K_i| by iterating k from 0 to i-1. The number of ways to place computer i is i - |K_i|. Update the answer: ans = (ans * (i - |K_i|)) % MOD. The total time complexity for this part is O(n^2).
  6. Return Result: Return the final calculated ans.

Walkthrough

The algorithm proceeds as follows:

First, we perform a basic check. For any computer i > 0 to be unlockable, it must have at least one prerequisite j < i with complexity[j] < complexity[i]. We can iterate through each i from 1 to n-1 and check if such a j exists. If not, we return 0. This check takes O(n^2).

Next, we define m[k] as the minimum complexity among all prerequisites of computer k. We can compute m[k] for all k from 0 to n-1 with a nested loop, which also takes O(n^2).

The main logic calculates the result ans as the product ans = product_{i=1 to n-1} (i - |K_i|). The set K_i is defined as {k < i | complexity[k] >= complexity[i] and m[k] >= complexity[i]}. We can compute |K_i| for each i by iterating k from 0 to i-1 and checking the conditions. This nested loop structure results in an O(n^2) complexity for the main calculation.

class Solution {    public int countPermutations(int[] complexity) {        int n = complexity.length;        long MOD = 1_000_000_007;         // Preliminary check: O(n^2)        for (int i = 1; i < n; i++) {            boolean hasPrereq = false;            for (int j = 0; j < i; j++) {                if (complexity[j] < complexity[i]) {                    hasPrereq = true;                    break;                }            }            if (!hasPrereq) {                return 0;            }        }         // Precompute m[k]: min complexity of prerequisites for k: O(n^2)        long[] m = new long[n];        for (int k = 0; k < n; k++) {            m[k] = Long.MAX_VALUE;            for (int j = 0; j < k; j++) {                if (complexity[j] < complexity[k]) {                    m[k] = Math.min(m[k], complexity[j]);                }            }        }         long ans = 1;        // Main calculation: O(n^2)        for (int i = 1; i < n; i++) {            int countKi = 0;            for (int k = 0; k < i; k++) {                if (complexity[k] >= complexity[i] && m[k] >= complexity[i]) {                    countKi++;                }            }            long choices = i - countKi;            ans = (ans * choices) % MOD;        }         return (int) ans;    }}

Complexity

Time

O(N^2) due to nested loops for the preliminary check, calculation of `m`, and the main product calculation.

Space

O(N) to store the minimum prerequisite complexities `m`.

Trade-offs

Pros

  • The logic is relatively straightforward to understand and implement.

  • It correctly solves the problem for smaller values of n.

Cons

  • The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), and will result in a Time Limit Exceeded (TLE) error.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem