Is Special Permutations easy or hard?

Special Permutations is generally considered a medium-to-hard dynamic programming problem. The challenge comes from recognizing that brute-force permutations are too slow and switching to subset DP with bitmask optimization.

How to solve Special Permutations in O(n^2 * 2^n)?

Use dynamic programming with a bitmask representing which indices are used. Maintain dp[mask][last] as the count of permutations ending at index 'last'. Transition by adding unused elements that satisfy the divisibility condition with the last element.

What is the best approach for Special Permutations?

Dynamic programming with bitmask state compression is the most efficient approach. It tracks which elements are already used with a bitmask and stores results in dp[mask][last]. This reduces the complexity to O(n^2 * 2^n), which works well for n up to about 14.

Is Special Permutations asked at Google/Amazon/Meta?

The problem style appears frequently in interviews at large tech companies because it combines permutation generation with dynamic programming and bitmask optimization. Similar subset DP problems are common at companies like Google, Amazon, and Meta.

What data structure is used in Special Permutations?

The core data structure is a DP table indexed by bitmask and the last chosen index. Bitmasks efficiently represent subsets of the array, while the DP table stores counts of valid permutations for each state.

What is the time complexity of Special Permutations?

The optimal DP with state compression runs in O(n^2 * 2^n) time and uses O(n * 2^n) space. A naive permutation approach with backtracking can reach O(n! * n) time because it explores nearly all permutations in the worst case.

Special Permutations Python or Java solution approach?

Both Python and Java implementations typically use the same DP with bitmask strategy. The solution maintains a 2D DP array or memoized recursion where states are defined by the used-element mask and the last selected index.

Description Hints 2 Solution Video 17:54

2741. Special Permutations

Medium29.4% acceptance

You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if:

For all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

Return the total number of special permutations. As the answer could be large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.

Example 2:

Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.

Constraints:

2 <= nums.length <= 14
1 <= nums[i] <= 10⁹

Topics

Hints open one at a time

Hint 1

Can we solve this problem using DP with bit masking?

Hint 2

You just need two states in DP which are last_ind in the permutation and the mask of numbers already used.

17:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def specialPerm(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,3,6]

Input

[1,4,3]

Your code is saved on this device.Solution