Tejav
#3577

Count the Number of Computer Unlocking Permutations

Medium
ArrayMathBrainteaserCombinatoricsDynamic ProgrammingSorting
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n²)
Space
O(1)
O(n)
💡

Intuition

Time O(n²)Space O(n)

Use dynamic programming to count valid unlock sequences based on previously unlocked computers. This reduces the complexity significantly by avoiding full permutation generation.

⚙️

Algorithm

3 steps
  1. 1Step 1: Sort computers by complexity while keeping track of their original indices.
  2. 2Step 2: Use a DP array where dp[i] counts valid unlock sequences ending at computer i.
  3. 3Step 3: For each computer, sum valid sequences from previously unlocked computers with lower complexity.
solution.py10 lines
1def countUnlockingPermutations(complexity):
2    n = len(complexity)
3    dp = [0] * n
4    dp[0] = 1
5    sorted_indices = sorted(range(n), key=lambda i: complexity[i])
6    for i in range(1, n):
7        for j in range(i):
8            if complexity[sorted_indices[j]] < complexity[sorted_indices[i]]:
9                dp[sorted_indices[i]] += dp[sorted_indices[j]]
10    return sum(dp) % (10**9 + 7)
ℹ

Complexity note: The time complexity is O(n²) due to the nested loops for counting valid sequences, while space complexity is O(n) for the dp array.

  • 1Unlocking depends on previously unlocked computers.
  • 2Sorting helps in efficiently counting valid sequences.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.