Dynamic Programming: Permutation Coefficient
Problem Statement: you are given 2 numbers n & k, you need to find permutation coefficient. What is Permutation Coefficient? Permutation Coefficient is number of ways to order “r” things out of “n” different things. It means, that if we have n elements and choose “r” elements from it, we need to find the ways […]
Dynamic Programming: Binomial Coefficiet Problem
Problem Statement: You are given 2 values, n & k. You need to find the binomial coefficient of the values. Binomial Coefficient is calculated by formula: C (n,k) = n!/((n-k)! *k!) Example 3C2 = 3!/((3-2)!*2!) = 3!/(1! *2!) = 3!/2! = 6/2 = 3 Solution We can solve this problem in 2 ways: 1. Naive […]
0 1 Knapsack Problem using Dynamic Programming
Solution Before we start with with the solution. Let us understand the basic of DP in series of points as below: 1. DP will be built on top of recursion. 2. So to understand DP you need to first find the recursion solution and from there you can move to DP. 3. We can identify […]
Detect a cycle in a undirected graph
Problem Statement: You are given a undirected graph. You need to find out if the graph contains cycle or not. Example Solution We can use DFS to solve this problem. For this we have a recursive stack and an array to hold the vertex that are visited. For every non visited vertex, mark the current […]
Detect a cycle in a directed graph
Problem Statement: You are given a directed graph. You need to find out if the graph contains cycle or not. Example Solution We shall use DFS to solve this problem: 1. We apply DFS for each vertex and keep track of visiting the vertices in recursion stack. 2. Then if we get a vertex that […]
Heaps: Merge âKâ sorted arrays
Problem Statement: You are given k sorted arrays of size n each. You need to merge them and print the sorted output. Example k = 3, n = 4 arr[][] = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; Output: 0 1 2 3 4 5 6 7 8 […]
Heaps: Find kth smallest in an unsorted array
Problem Statement: You are given an array and a number K, you need to find the kth smallest element. Example Input: arr[] = {5, 20, 10, 7, 1}, N = 5, K = 2 Output: 5 Solution We will use max heap to solve this problem. 1. We create priority queue for first k elements. […]
Heaps: Sort an Array using heap
Problem Statement: Given an array, sort it by using heap sort. Solution Relationship between array and heap elements. As we know that heaps are complete binary trees and they satisfy the below property: If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and […]
Heaps: Build Min Heap from an Array
Problem Statement: You are given N array elements. You need to build a Min Heap. Solution Min Heap: The root element is greater than its children. In this approach, we will heapify for every element inserted. Changing the structure of the heap to meet the heap property is called as heapify. Heap Property: Left child […]
Next Smaller Element
Problem Statement: YOu are given an unsorted array, you need to find the next smaller element for all the elements. Next smaller element for an item ‘x’ is the first smaller element on the right side of x in that array Example arr = [5, 9, 6, 3, 20] Element NSE 5 –> 3 9 […]