Solving Algorithmic Problems

Description   Solution: Digit DP Memoize each  dp(i, prev, stateLow, stateHigh) , where i  = the number of digits we currently have prev  = the previous character in the sequence stateLow  = whether the current number is tracking smaller, the same, or greater than  low  ( 0 = smaller, 1 = same, 2 = greater ) stateHigh  = whether the current number is tracking smaller, the same, or greater than  high  ( 0 = smaller, 1 = same, 2 = greater ) For each  dp(i, prev, stateLow, stateHigh) , we have two possible next digits:  [prev - 1,prev + 1] . Calculate and return the total combinations. n = length of high Time Complexity:  O(n * 90) Space Complexity:  O(n * 90) var countSteppingNumbers = function ( low, high ) { let n = high.length, memo = Array (n).fill( 0 ).map( () => Array ( 10 ).fill( 0 ).map( () => Array ( 3 ).fill( 0 ).map( () => Array ( 3 ).fill(- 1 )))); // [n][10][3][3] let ans = 0 , MOD = 10 ...

Description   Solution: Digit DP Memoize each  dp(i, state1, state2, digitSum) , where i = index of current digit state1 = state of current number compared to num1 (0 = smaller, 1 = equal, 2 = greater) state2 = state of current number compared to num2 (0 = smaller, 1 = equal, 2 = greater) digitSum = current digit sum For each  dp(i, state1, state2, digitSum) , try each possible digit as the next digit. Compute the new states compared to  num1  and  num2 . Time Complexity:  O(len(num2) * max_sum * 9) Space Complexity:  O(len(num2) * max_sum * 9) var count = function ( num1, num2, min_sum, max_sum ) { let memo = new Map (), MOD = 10 ** 9 + 7 ; return dp( 0 , 1 , 1 , 0 ); function dp ( i, state1, state2, digitSum ) { if (i === num2.length) return state1 > 0 && state2 < 2 && digitSum >= min_sum && digitSum <= max_sum ? 1 : 0 ; let key = ` ${i} , ${state1} , ${state2} , ${digitSum} ` ; ...

Description   Solution: Digit DP Memoize each  dp(i, mask, state, hasRepeat) , where i = the ith digit mask = bitmask which indicates which digit we have already used state = indicates whether the current number is tracking smaller, equal, or greater than n 0 = smaller 1 = equal 2 = greater hasRepeat = whether we have a repeated digit If  hasRepeat  is true (1), count it as 1 way. For each state, count the total number of ways after appending each digit ( 0 - 9 ). state : If  digit < n[index] , update state to  0  (smaller) if state is currently  1  (equal). If  digit === n[index] , keep state the same. If  digit > n[index] , update state to  2  (greater) if state is currently  1  (equal). d = number of digits in n Time Complexity:  O(d * 2^10 * 3 * 2 * 10)  488ms d * 2^10 * 3 * 2  = the number of different states we can have 10  = at each state we have  10  options for digits...