Count the Number of Beautiful Subarrays - Prefix Bitmasks & Hashmap [JS]

By on

Description 

Solution: Prefix Bitmasks & Hashmap

Keep track of the running prefix bitmask as we go through nums.
Since we only need to know whether the number of 1 bits at each position is even or odd, we can use 0 to represent an even number of bits, and 1 to represent an odd number of bits.
For each index i, count the number of previous prefix bitmasks with the exact same state as the current bitmask.
If the bitmasks are the same, that means each bit has an even count for the subarray between index i and the previous bitmask.
Use a hashmap to count the occurances of each bitmask.

Time Complexity: O(n)
Space Complexity: O(n)

var beautifulSubarrays = function(nums) {
  let mask = 0, count = new Map(), ans = 0;
  count.set(0, 1);
  for (let i = 0; i < nums.length; i++) {
    mask = mask ^ nums[i];
    ans += (count.get(mask) || 0);
    count.set(mask, (count.get(mask) || 0) + 1);
  }
  return 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

Check if There is a Valid Partition For The Array - Two Approaches - DP & Recursion w/ Memoization [JS]

By on
Description   Solution 1: DP - Recursion w/ Memoization Memoize each  dp(i) , where  dp(i) = whether it is possible to have a valid partition from index i to n . For each index  i , try to make it part of a valid partition (one of the three cases): Two equal elements Three equal elements Three consecutive elements Time Complexity:  O(n)  158ms Space Complexity:  O(n)  59.9MB var validPartition = function ( nums ) { let n = nums.length, memo = Array (n).fill(- 1 ); return dp( 0 ); function dp ( i ) { if (i === n) return true ; if (i === n - 1 ) return false ; if (memo[i] !== - 1 ) return memo[i]; if (nums[i] === nums[i + 1 ] && dp(i + 2 )) return memo[i] = true ; if (i < n - 2 ) { if (!dp(i + 3 )) return memo[i] = false ; let hasThreeEqual = nums[i] === nums[i + 1 ] && nums[i + 1 ] === nums[i + 2 ]; let hasThreeConsecutive = nums[i] + 1 === nums[i + 1 ] && nu...
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

Count Elements With Maximum Frequency - Hashmap [JS]

By on
Description   Solution: Hashmap Store the counts of elements in a hashmap. Keep track of the running max frequency. If a count exceeds the max frequency, reset the total count. If a count is equal to the max frequency, add to the total count. Time Complexity:  O(n) Space Complexity:  O(n) var maxFrequencyElements = function ( nums ) { let maxFreq = 0 , countMap = {}, ans = 0 ; for ( let num of nums) { countMap[num] = (countMap[num] || 0 ) + 1 ; let count = countMap[num]; if (count > maxFreq) { ans = count; maxFreq = count; } else if (count === maxFreq) { ans += count; } } return ans; };
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