Special Permutations - DP w/ Bitmasks [JS]

By on

Description 

Solution: DP w/ Bitmasks

Memoize each dp(mask, prevIndex), where

  • mask = bitmask which indicates which numbers we have used so far
  • prevIndex = index of the previous number in the permutation

For each dp(mask, prevIndex), go through each number and try each unused number that is valid for the current sequence.
Count the total number of ways.

Time Complexity: O(2^n * n^2)
Space Complexity: O(2^n * n)

var specialPerm = function(nums) {
  let n = nums.length, fullMask = (1 << n) - 1;
  let memo = Array(1 << n).fill(0).map(() => Array(n).fill(-1)), MOD = 10 ** 9 + 7, res = 0;
  for (let i = 0; i < n; i++) {
    res = (res + dp(1 << i, i)) % MOD;
  }
  return res;
  
  function dp(mask, prevIndex) {
    if (mask === fullMask) return 1;
    if (memo[mask][prevIndex] !== -1) return memo[mask][prevIndex];

    let ans = 0;
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) continue; 
      if ((nums[i] % nums[prevIndex] === 0) || (nums[prevIndex] % nums[i] === 0)) {
        let newMask = mask | (1 << i);
        ans = (ans + dp(newMask, i)) % MOD;
      }
    }
    return memo[mask][prevIndex] = ans;
  }  
};
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Beautiful Towers II - Monotonic Increasing Stack [JS]

By on
Description   Solution: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  left[i]  = sum of heights from ( 0, ..., i ) such that they are descending from index  i  to  0 . right :  right[i]  = sum of heights from ( i, ..., n - 1 ) such that they are descending from index  i  to  n - 1 . Use a monotonic increasing stack to store indices of  maxHeights  such that they are smaller than  maxHeights[i] . left to right: We know that from index  i  to  stack[stack.length - 1] , all heights are smaller than  maxHeights[i] . Take the existing sum up to  stack[stack.length - 1]  ( left[stack[stack.length - 1]] ) and add the sum for the current range ( maxHeights[i] * (i - stack[stack.length - 1]) ) Then, do the same from right to left. Take each  maxHeights[i]  as the peak of the mountain and use the results from  ...
Read more

Minimum Number of Operations to Sort a Binary Tree by Level - BFS & Cycle Counting Explained [JS]

By on
Description   Solution: BFS & Cycle Counting BFS level-by-level and get minimum swaps for the node values at each level. How to calculate the minimum swaps to sort an array: Get the index of each number in its sorted position (store in a hashmap  indexes ) For each  nums[i] , store the number we need to swap with to place  nums[i]  in its sorted position (store in a hashmap  next ) Find the size of each cycle. Get the total sum of each ( cycle size - 1 ). Why sum of ( cycle size - 1 ) is correct: If cycle size =  1 , we don't need any swaps. If cycle size =  2 , we only need 1 swap. If cycle size =  3 , we need 2 swaps. ---  Main Proof  --- Starting from the smallest number in the cycle, swap each  nums[i]  (where  nums[i]  is in the cycle) into its sorted position. Since the number is now in the correct position, it is no longer in the cycle and this leaves us with a cycle of size ( n - 1 ), where  n = ...
Read more

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

By on
Description  Solution: Sliding Window w/ Two Pointers & Set Maintain a sliding window of unique numbers with maximum size of  k . We can store the numbers in the window in a hashset. When we move the right pointer up, move the left pointer up until: all numbers in the window are unique the window size  <= k Time Complexity:  O(n)  246ms Space Complexity:  O(k)  71.5MB var maximumSubarraySum = function ( nums, k ) { let set = new Set (), sum = 0 ; let ans = 0 , n = nums.length; for ( let j = 0 , i = 0 ; j < n; j++) { sum += nums[j]; while (set.has(nums[j]) || j - i >= k) { sum -= nums[i]; set.delete(nums[i]); i++; } set.add(nums[j]); if (j - i + 1 === k) ans = Math .max(ans, sum); } return ans; };
Read more

Maximum Score After Applying Operations on a Tree - DFS [JS]

By on
Description   Solution: Post-order DFS Choose one node value to keep per leaf node path. Use post-order DFS to find the minimum sum of node values taking one node per path (at the end, the result is  total sum - dfs(0, -1) ) For each  dfs(node) , we have two choices: Take the node: We get to keep all the subtree values except the current node. Skip the node: Each child subtree needs to choose one value to keep. n = number of nodes ,  m = number of edges Time Complexity:  O(n + m) Space Complexity:  O(n + m) var maximumScoreAfterOperations = function ( edges, values ) { let n = values.length, graph = Array (n).fill( 0 ).map( () => []); for ( let [a, b] of edges) { graph[a].push(b); graph[b].push(a); } let totalSum = values.reduce( ( sum, value ) => sum + value); return totalSum - dfs( 0 , - 1 ); function dfs ( node, parent ) { if (graph[node].length === 1 && graph[node][ 0 ] === parent) { return va...
Read more

Divide Nodes Into the Maximum Number of Groups - Union Find & BFS [JS]

By on
Description   Solution: Union Find & BFS Build the graph and connect nodes using union find. Find the groups of connected nodes. Find the maximum groups to divide for each connected group. Use level-by-level BFS to find the maximum depth of the group. How to detect an odd-lengthed cycle: Cycles are bound to meet in the middle since we are traversing level-by-level, so if the level of a neighbor node is equal to the current level, the cycle is odd-lengthed. n = number of nodes ,  m = number of edges Time Complexity:  O(n * (n + m))  639ms Space Complexity:  O(n + m)  64.6MB var magnificentSets = function ( n, edges ) { let uf = new UnionFind(n + 1 ); let graph = Array (n + 1 ).fill( 0 ).map( () => []); for ( let [a, b] of edges) { // 1. Build graph, connect nodes graph[a].push(b); graph[b].push(a); uf.union(a, b); } let groups = {}; for ( let i = 1 ; i <= n; i++) { // 2. Find groups of connected nodes let...
Read more