Solving Algorithmic Problems

Description   Solution: Combinatorics We can use at most  1  more decrement operation than jumps. Go through each amount of jumps until we reach a stair where we don't have enough decrement operations to go back to  k . For each amount of jumps, we reach a stair  nextStair , and  nextStair - k  decrement operations to go back to  k . The decrement operations can be performed in any order as long as they are not consecutive. There are a total of  jumps + 1  positions where a decrement operation can be performed. Use the n-choose-r formula to calculate the number of combinations of putting  r  decrement operations in  jumps + 1  different positions. e.g.  k = 6 , and we use  2  jumps 1 -> 2 -> 4 -> 8 decrement operations = 8 - 6 = 2 positions: 1 _ 2 _ 4 _ 8 _  ( 4  available positions for  2  decrement operations) 4 choose 2 = 6 Time Complexity:  O(log2(k)) Space Complexi...

Description   Solution: Two Pointers Find the number of groups. All occurances of a number must be contained in the same group. Use two pointers to find the number of groups: Record the indices of the last occurance of each number. Extend the right pointer of the group to  lastIndex[nums[i]] , until the left pointer reaches the right pointer. Calculate the number of different partitions of these groups. Each group has two choices: Either join the current group with the previous group, or start a new partition. Since the first group has only one choice, it can be calculated as:  2^(groups - 1) . Calculate this on the fly. Time Complexity:  O(n) Space Complexity:  O(n) var numberOfGoodPartitions = function ( nums ) { let n = nums.length, lastIndex = {}; for ( let i = 0 ; i < n; i++) { lastIndex[nums[i]] = i; } let i = 0 , foundFirstGroup = false ; let ans = 1n , MOD = 1000000007n ; while (i < n) { let j = lastIndex[nums[i]]; w...

Description   Solution: Multiply Index Differences Collect the indexes of all 1's. Multiply the index difference between each adjacent pair of 1's. e.g: 010001 The difference between the first pair of 1's = 4 This indicates 4 different places to split: 01|0001 010|001 0100|01 01000|1 We do the same for each other adjacent pair of 1's and multiply the differences together to get the total combinations. Time Complexity:  O(n) Space Complexity:  O(n) var numberOfGoodSubarraySplits = function ( nums ) { let n = nums.length, MOD = 10 ** 9 + 7 , ones = []; for ( let i = 0 ; i < n; i++) { if (nums[i] === 1 ) ones.push(i); } if (!ones.length) return 0 ; let ans = 1 ; for ( let i = 1 ; i < ones.length; i++) { let ways = ones[i] - ones[i - 1 ]; ans = (ans * ways) % MOD; } return ans; };