Solving Algorithmic Problems

Description   Solution: Math Alice wins with an odd number of flowers. Count all the combinations of creating an odd number. x  is odd,  y  is even. x  is even,  y  is odd. To find how many even numbers <=  n :  floor(n / 2) e.g.  n = 5  ->  [2,4]  ->  floor(n / 2) = 2 e.g.  n = 6  ->  [2,4,6]  ->  floor(n / 2) = 3 To find how many odd numbers <=  n :  ceil(n / 2) e.g.  n = 5  ->  [1,3,5]  ->  ceil(n / 2) = 3 e.g.  n = 6  ->  [1,3,5]  ->  ceil(n / 2) = 3 Time Complexity:  O(1) Space Complexity:  O(1) var flowerGame = function ( n, m ) { let oddEven = countOdd(n) * countEven(m); let evenOdd = countEven(n) * countOdd(m); return oddEven + evenOdd; }; function countOdd ( x ) { return Math .ceil(x / 2 ); } function countEven ( x ) { return Math .floor(x / 2 ); }

Description   Solution: Math & Segment Tree The equation  nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff  can be converted into  nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff . Go through each index  j . Record all past index  i 's differences ( nums1[i] - nums2[i] ). If  nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff , we have a found a pair. Use a segment tree to keep track of the count of each ( nums1[i] - nums2[i] ). For each index  j , find the number of previous index  i 's with difference in the range of  (min(nums1[i] - nums2[i]), nums1[j] - nums2[j] + diff) . Offset the segment tree by  min(nums1[i] - nums2[i]  so that we won't go into negative indexes. m = max(nums1[i] - nums2[i]) Time Complexity:  O(n log(m))  226ms Space Complexity:  O(m)  55.3MB var numberOfPairs = function ( nums1, nums2, diff ) { let offset = 0 , maxDiff = - Infinity , n = nums1.length; for ( let ...

Description   Solution: Last Index Keep track of the last index of each character in  s , on the fly. To get the number of subarrays each character appears in, the formula is  (n - i) * (i + 1) (i + 1)  -> number of starting subarrays ending with  arr[i] (n - i)  -> number of different ending subarrays after  arr[i] e.g: arr =  [1,2,3,4] Let's look for the number of times  arr[1]  appears in a subarray: (i + 1) = [[1,2],[2]] (n - i) = [[2],[2,3],[2,3,4]] (n - i) * (i + 1)  = all the combinations (6) -> [[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4]] However, we are only counting the distinct characters. To solve this, keep track of the last index of each character, then exclude counting the subarrays which overlap with the last occurance. The formula turns into:  (n - i) * (i - lastIdx) e.g: arr =  [1,2,3,2,4] Let's calculate the 'appeal' of  arr[3] . We only want to count these subarrays (don't include the earli...

Description Solution: Math - Permutations pickups: n! deliveries: (1 * 3 * 5 * 7 * ...) n times e.g: P1 P2 D1 D2 deliveries: 1 choice: P1 P2 -> put D2: only 1 choice -> P1 P2 D2 P2 P1 -> put D1: only 1 choice -> P2 P1 D1 3 choices: P1 P2 D2 -> put D1: 3 choices -> (P1 D1 P2 D2), (P1 P2 D1 D2), (P1 P2 D2 D1) P2 P1 D1 -> put D2: 3 choices -> (P2 D2 P1 D1), (P2 P1 D2 D1), (P2 P1 D1 D2) It can be proven that the total number of valid pickups/deliveries is n! * (1 * 3 * 5 * 7 * ...) n times deliveries: 0 -> 1 1 -> 3 2 -> 5 3 -> 7 The formula is (i * 2 + 1) for the deliveries Time Complexity: O(n) 101ms Space Complexity: O(1) 42.6MB var countOrders = function ( n ) { let ans = 1 , mod = 10 ** 9 + 7 ; for ( let i = 0 ; i < n; i++) { ans = (ans * (i + 1 )) % mod; ans = (ans * (i * 2 + 1 )) % mod; } return ans; }; javascript