Backtracking: Find combination sum of k numbers that sum up to n
Problem Statement: You are given two numbers K and N, you need to find all valid combinations of k numbers that sum up to n. Such that only the numbers 1 to 9 are used and at-most only once. Example Input: k = 3, n = 7 Output: [[1,2,4]] Because 1 + 2 + 4 […]
Backtracking: Get the k combination from an array of 1 to n
Problem Statement: You are given 2 integers n and k, you need to return all possible combination of K numbers from the range [1, n] Example Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Solution We will use backtracking approach to solve this problem. We will call […]
Backtracking: You are given an array with repeated elements and a key element, find all unique combination to the key
Problem Statement: You are given an array with repeated elements, and a key element. You need to return the unique combination in that array where the sum is equal to the target. Example Input: array = [2,5,2,1,2], key = 5 Output: [ [1,2,2], [5] ] Solution This problem can be solved by backtracking. One thing […]
Backtracking: Partition string into its palindrome
Problem Statement: You are given a string. You need to partition the string in such a way that, each substring is a palindrome. Example Input: s = “abb” Output: [[“a”,”b”,”b”], [“a”,”bb”]] Solution The solution in very simple. We will use backtracking approach to solve this problem. First we loop through the string and check if […]
Greedy: Find maximum sum possible equal sum of three stacks
Problem Statement: You are given 3 arrays that represents a stack. You need to remove the top elements of the stack such that the sum of all the stacks are equal. Example stack1[ ] = {4, 3, 2} stack2[ ] = {3, 2, 1, 1, 1} stack3[ ] = {1, 1, 4, 1} Output: 5 […]
Greedy: Connect ropes with minimum cost.
Problem Statement: You are given n ropes of different length. You need to connect these ropes into one rope. The cost of connecting two ropes is equal to the sum of their lengths. Example Input : {4, 3, 2, 6} Output: 29 Connect 2, 3 resultant array {4, 6, 5} Next connect 4, 5 resultant […]
Greedy: String break problem
Problem Statement: You are given 2 string and you need to check if some permutation of s1 can break s2 or vice-versa. A string can break another string if s1[i] >= s2[i] for all i from 0 to n-1 Example Input: s1 = “abc”, s2 = “xya” Output: true Because you can permute s2 = […]
Greedy: Reduce the array size to the half
Problem Statement: You are given an array with repeated elements. You can choose set of integers and remove all the occurrence of the integers from the array You need to return the minimum size of the set so that half of the array is removed Example Input: arr = [6, 6, 6, 6, 6, 6, […]
Greedy: Remove covered intervals.
Problem Statement: You are given a list of intervals, you need to remove all the intervals that are covered by other intervals and return the number of intervals remaining. Example Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 The interval [3,6] is covered by [2,8], hence can be removed. Solution We use greedy approach, we greedily sort […]
Greedy: Add minimum to make parentheses valid.
Problem Statement: You are given a string of ‘(‘ and ‘)’. You need to return the minimum number of parentheses to make the string valid. Example Input: “())” Output: 1 Solution Solution is simple. We take 2 variables, “open” will represent ‘(‘ to add it to left. “close” will represent ‘)’ to add it to […]