Solving Algorithmic Problems

Description   Solution: DP Keep track of four states: prevPrevA : The max energy ending with drink A, at the previous previous index (needed when we switch to another drink type). prevPrevB : The max energy ending with drink B, at the previous previous index (needed when we switch to another drink type). prevA : The max energy ending with drink A, at the previous index. prevB : The max energy ending with drink B, at the previous index. For each index  i , we can either Stay with the same drink type and take the energy at the previous energy ending with the same type. Switch the drink type and take the energy at the previous previous energy ending with the other type. Update those four states as we go through each index. Time Complexity:  O(n) Space Complexity:  O(1) function maxEnergyBoost ( energyDrinkA, energyDrinkB ) { let prevPrevA = 0 , prevPrevB = 0 ; let prevA = 0 , prevB = 0 ; let n = energyDrinkA.length; for ( let i = 0 ; i < n; i++) { l...

Description   Solution 1: DP - Recursion w/ Memoization Memoize each  dp(zeros, ones, last) , where zeros = number of zeros in the array ones = number of ones in the array last = the last number in the array For each  dp(zeros, ones, last) , We must take some consecutive amount of the other binary number (not the last number). Go through each count up to limit and get the total number of ways over each. Time Complexity:  O(zero * one * limit * 2) Space Complexity:  O(zeros * one * 2) function numberOfStableArrays ( zero, one, limit ) { let memo = Array (zero + 1 ).fill( 0 ).map( () => Array (one + 1 ).fill( 0 ).map( () => Array ( 2 ).fill(- 1 ))); const MOD = 1000000007 ; return (dp( 0 , 0 , 0 ) + dp( 0 , 0 , 1 )) % MOD; function dp ( zeros, ones, last ) { if (zeros > zero || ones > one) return 0 ; if (zeros === zero && ones === one) return 1 ; if (memo[zeros][ones][last] !== - 1 ) return memo[zeros][ones][...