Added LC 322 and 927.

anxious-coder-lhs · anxious-coder-lhs · commit d93c6bbfb3f0 · 2020-11-28T20:33:30.000+05:30
diff --git a/README.md b/README.md
@@ -62,6 +62,8 @@ Happy to accept any contributions to this in any langugage.
 27. [Microsoft OA - Min Moves to Make String without 3 Identical Chars](https://molchevskyi.medium.com/microsoft-interview-tasks-min-moves-to-make-string-without-3-identical-consecutive-letters-abe61ed51a10) | [Solution](./level_medium/MinMovesToMakeStringWithout3IdenticalChars.ts)
 28. [Android Unlock Patterns](https://leetcode.com/problems/android-unlock-patterns/) | [Solution 1](./level_medium/LeetCode_351_Android_Unlock.ts) | [Solution 2](/level_medium/LeetCode_351_Android_Unlock_1.ts)
 29. [Leet Code 1573 - Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/) | [Solution 1](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String_1.ts) | [Solution](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String.ts)
+30. [Leet Code 322: Coin Change](https://leetcode.com/problems/coin-change/) | [Solution](./level_medium/LeetCode_322_Coins_Change_1.ts) | [Sol 2](./level_medium/LeetCode_322_Coins_Change_2.TS) | [Sol 3](./level_medium/LeetCode_322_Coins_Change.ts)
+31. [Leet Code 927 - 3 Equal Parts](https://leetcode.com/problems/three-equal-parts/) | [Solution 1](./level_medium/LeetCode_927_Three_Equal_Parts.ts) | [Solution 1](./level_medium/LeetCode_927_Three_Equal_Parts_1.ts)
 
 
 ## Hard
diff --git a/level_medium/LeetCode_322_Coins_Change.ts b/level_medium/LeetCode_322_Coins_Change.ts
@@ -0,0 +1,41 @@
+/**
+ * Leet Code 322
+ * 
+ * Solution uses dynamic programming to compute the results for making all target amount from 0 till max for all
+ * the possible coins denominations from 0 to end. This is because the problem can be divided into sub problems
+ * as picking a coin leaves up the same problem as original with less target sum.
+ * 
+ * Brute force
+ * 
+ * Time: O(m^n) where n is the number of coin denominations and m is the target sum.
+ * Space: O(n*m) for storing all possible results.
+ * 
+ * @param coins 
+ * @param amount 
+ */
+function coinChange(coins: number[], amount: number): number {
+    const totalChange = coinChangeHelper(coins, amount, 0);
+    return totalChange === Infinity ? -1 : totalChange;
+};
+
+function coinChangeHelper(coins: number[], amount: number, current: number): number {
+    
+    // Return 0 if target amount is 0
+    if (amount <= 0) return 0;
+    
+    // All the amount is done using this coin.
+    if (coins[current] === amount) return 1;
+    
+    // All the coins are done processing and we do not have a result
+    if (current >= coins.length) return Infinity;
+    
+    let coinsWithInclusion = Infinity, coinsWithoutInclusion = Infinity;
+    if (amount >= coins[current]) {
+        // A number of current coin denominations can be used.
+        coinsWithInclusion = 1 + coinChangeHelper(coins, amount - coins[current], current);
+    }
+    
+    coinsWithoutInclusion = coinChangeHelper(coins, amount, current + 1);
+    
+    return Math.min(coinsWithInclusion, coinsWithoutInclusion);
+}
diff --git a/level_medium/LeetCode_322_Coins_Change_1.ts b/level_medium/LeetCode_322_Coins_Change_1.ts
@@ -0,0 +1,45 @@
+/**
+ * Leet Code 322
+ * 
+ * Solution uses dynamic programming to compute the results for making all target amount from 0 till max for all
+ * the possible coins denominations from 0 to end. This is because the problem can be divided into sub problems
+ * as picking a coin leaves up the same problem as original with less target sum.
+ * 
+ * The solution uses the top down approach to compute all the results.
+ * 
+ * Time: O(n*m) where n is the number of coin denominations and m is the target sum.
+ * Space: O(n*m) for storing all possible results.
+ * 
+ * @param coins 
+ * @param amount 
+ */
+function coinChange(coins: number[], amount: number): number {
+    const cache: number[][] = Array.from({length: coins.length + 1}, () => Array(amount));
+    const totalChange = coinChangeHelper(coins, amount, 0, cache);
+    return totalChange === Infinity ? -1 : totalChange;
+};
+
+function coinChangeHelper(coins: number[], amount: number, current: number, cache: number[][]): number {
+    
+    // Return 0 if target amount is 0
+    if (amount <= 0) return 0;
+    
+    // All the amount is done using this coin.
+    if (coins[current] === amount) return 1;
+    
+    // All the coins are done processing and we do not have a result
+    if (current >= coins.length) return Infinity;
+    
+    if (cache[current][amount] !== undefined) return cache[current][amount];
+    
+    let coinsWithInclusion = Infinity, coinsWithoutInclusion = Infinity;
+    if (amount >= coins[current]) {
+        // A number of current coin denominations can be used.
+        coinsWithInclusion = 1 + coinChangeHelper(coins, amount - coins[current], current, cache);
+    }
+    
+    coinsWithoutInclusion = coinChangeHelper(coins, amount, current + 1, cache);    
+    
+    cache[current][amount] = Math.min(coinsWithInclusion, coinsWithoutInclusion);
+    return cache[current][amount];
+}
diff --git a/level_medium/LeetCode_322_Coins_Change_2.TS b/level_medium/LeetCode_322_Coins_Change_2.TS
@@ -0,0 +1,49 @@
+/**
+ * Leet Code 322
+ * 
+ * Solution uses dynamic programming to compute the results for making all target amount from 0 till max for all
+ * the possible coins denominations from 0 to end. This is because the problem can be divided into sub problems
+ * as picking a coin leaves up the same problem as original with less target sum.
+ * 
+ * The solution uses the bottoms up approach to compute all the results.
+ * 
+ * Time: O(n*m) where n is the number of coin denominations and m is the target sum.
+ * Space: O(n*m) for storing all possible results.
+ * 
+ * @param coins 
+ * @param amount 
+ */
+function coinChange(coins: number[], amount: number): number {
+    
+    // Create a DP Table
+    const dpTable: number[][] = Array.from({length: coins.length + 1}, () => Array(amount + 1).fill(Infinity));
+    
+    // For all the amount with a single coin, we calculate the initial min coins.
+    for (let amt = 1; amt <= amount; amt++) {
+        if (amt % coins[0] === 0) {
+            dpTable[0][amt] = Math.floor(amt / coins[0]);
+        } else {
+            dpTable[0][amt] = Infinity;
+        }
+    }
+    
+    // For amount 0, we need 0 coins.
+    for (let coin = 0; coin < coins.length; coin++) dpTable[coin][0] = 0;
+    
+    // Calculate rest of the figures.
+    for (let coin = 1; coin < coins.length; coin++) {
+        for (let amt = 1; amt <= amount; amt++) {
+            
+            // Only if the new amount is greater than the coin.
+            if (amt >= coins[coin]) {
+                dpTable[coin][amt] = 1 + dpTable[coin][amt - coins[coin]];
+            }
+            
+            // Also try without adding the current coin.
+            dpTable[coin][amt] = Math.min(dpTable[coin][amt], dpTable[coin - 1][amt])
+        }
+    }
+    
+    const result = dpTable[coins.length - 1][amount];
+    return result === Infinity ? -1 : result;
+};
diff --git a/level_medium/LeetCode_927_Three_Equal_Parts.ts b/level_medium/LeetCode_927_Three_Equal_Parts.ts
@@ -0,0 +1,27 @@
+function threeEqualParts(A: number[]): number[] {
+    for (let left = 0; left < A.length - 2; left++) {
+        for (let right = left + 2; right < A.length; right++) {
+            if (haveEqualParts(left, right, A)) {
+                return [left, right];
+            }
+        }
+    }
+    
+    return [-1, -1];
+};
+
+function haveEqualParts(left: number, right: number, A: number[]): boolean {
+    const decimalVal1 = binaryToDecimal(A, 0, left);
+    const decimalVal2 = binaryToDecimal(A, left + 1, right - 1);
+    const decimalVal3 = binaryToDecimal(A, right, A.length - 1);
+    return decimalVal1 === decimalVal2 && decimalVal2 === decimalVal3;
+}
+
+function binaryToDecimal(A: number[], left: number, right: number) {
+    let total = 0, base = 1;
+    for (let val = right; val >= left; val--) {
+        total += base * A[val];
+        base *= 2;
+    }
+    return total;
+}
diff --git a/level_medium/LeetCode_927_Three_Equal_Parts_1.ts b/level_medium/LeetCode_927_Three_Equal_Parts_1.ts
@@ -0,0 +1,81 @@
+/**
+ * Leet Code 927
+ * 
+ * Solution is based on the fact that the number of 1s will be equal and hence there boundaries can be identified
+ * using a single iteration. We just need to identify the number of zeroes in between and ignore those (assign to the right).
+ * 
+ * Time: O(n), space: O(1)
+ * 
+ * @param A 
+ */
+function threeEqualParts(A: number[]): number[] {
+    
+    // Return negative, cannot be divided.
+    const totalOnes = countOnes(A);
+    if (totalOnes % 3 !== 0) return [-1, -1];
+    if (totalOnes === 0) return [0, A.length - 2];
+    
+    const maxPartOnes = totalOnes/3;
+    
+    // Critical Path will return {left, right} + zeros.
+    const cp = findCriticalPath(A, maxPartOnes);
+    if (cp === undefined) return [-1, -1];
+    
+    // Middle Critical Path will return {left, right}
+    const midCp = matchCriticalPath(A, cp);
+    if (midCp === undefined) return [-1, -1];
+    
+    // Left Critical Path will return {left, right}
+    const leftCp = matchCriticalPath(A, midCp);
+    if (leftCp === undefined || hasMostSigOne(A, leftCp.left - 1)) return [-1, -1];
+        
+    return [leftCp.right, midCp.right + 1];
+};
+
+function hasMostSigOne(A: number[], start: number) {
+    for (let pos = start; pos >= 0; pos--) if (A[pos] !== 0) return true
+}
+
+// Matches the critical path of the current part to the right part. Do the adjustments for any gaps of zeros.
+function matchCriticalPath(A: number[], {left, right, zeros}) {
+    
+    // Get all the leading zeros so far.
+    let newPos = left - 1, thisZeros = 0;
+    while(A[newPos] === 0) {
+        thisZeros++;
+        newPos--;
+    }
+
+    // Break if not matching with enough trailing zeros.
+    if (thisZeros < zeros) return undefined;
+      
+    // Break if the critical path is not matching.
+    for (let oldPos = right - zeros; oldPos >= left; oldPos--) {
+        if (A[newPos--] !== A[oldPos]) return undefined;
+    }
+    
+    // All fine, adjust the bounds and return;
+    return {
+        left: newPos + 1,
+        right: (left - 1) - (thisZeros - zeros),
+        zeros,
+    }
+}
+
+function findCriticalPath(A: number[], maxPartOnes: number) {
+    let ones = 1, zeros = 0, pos = A.length - 1;
+    while(A[pos--] === 0) zeros++;
+    while(ones < maxPartOnes) {
+        if (A[pos--] === 1) {
+            ones++;
+        }
+    }
+    
+    return {left: pos + 1, right: A.length - 1, zeros};
+}
+
+function countOnes(A: number[]) {
+    return A.filter(val => val === 1).length;
+}
+
+console.log(threeEqualParts([1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0]));
