The Heap Space

  Concept:  We will be using two heaps - a min-heap and a max-heap to keep track of the median on every step. We will store the first half of the numbers in the max-heap and the second half of the numbers will be stored in the min-heap. If we get the same size of both heaps and we calculate the mean of the roots of min-heap and max-heap. If we get the different sizes of both heaps, the heap with the larger size will contain the median at its root. All this time, we have to make sure that we keep a balance among the sizes of both heaps in such a way that either both of them are equal in size or differ in size only by 1. This will ensure our median candidates always be at the root of both heaps. Note: To simulate the random generation and storage into an expanding array, I am passing a random number in insert() function after some sleep time. This way we can get a feeling that we are getting a stream of numbers continuously. Also, we calculate the median on every insert() Ti...

  What is Dynamic Programming? Dynamic Programming or DP is a method for solving a problem by breaking it into smaller sub-problems, solving the subproblems only once and storing the result of the sub-problems for future use so that we do not solve a sub-problem again and again (like we do in Divide and Conquer). Dynamic Programming is just an optimization of Divide and Conquer. In Divide and Conquer we may solve sub-problem multiple times, but DP prevents that by storing the result of a sub-problem once it is solved once, thus saving on run-time and compromising a little on space complexity. When Should we use the Dynamic Programming approach? When we see these both of these properties in a problem, we can use DP: Optimal Substructure   This property has already been explained in the post of Divide and Conquer , as Divide and Conquer also have this property. Overlapping Subproblems Any problem has overlapping sub-problems if finding its solution involves solving the same sub-...

What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...

  What is Activity Selection Problem? We are given 'n' activities with their start and finish times and we have to select the maximum number of activities that can be performed by a single person, assuming that the person can only work on a single activity at a time.      Activity  A1   A2   A3   A4   A5   A6   Start Time  0  3  1  5  5  8   End Time   6  4  2  8  7  9 How are we gonna solve this Activity Selection Problem?  [Time Complexity - O(nlogn)  Space Complexity - O(n)] As we want to cover the maximum number of tasks, we should complete all those tasks first that finish first. So our focus is going to be on the end time of tasks.  1. Sort the tasks by the end time 2. Always pick the first task and initialize a variable prevTaskTime = end time of the first task 3. For all other tasks:          4. if the current task...

  What is a Greedy Algorithm? A Greedy Algorithm is an algorithm or rather a technique, that always makes a choice that seems to be the best at the moment. This means that it makes a locally optimal choice assuming that this choice will result in a globally optimal solution of the given problem.  As a Greedy Algorithm assumes that the choice it made at the local level is the best choice available at that moment, hence the Greedy Algorithm has only one shot to compute the optimal solution of the given problem. The Greedy Solution never goes back and reverses its decision. Where Should we use a Greedy Algorithm? When we see that the given problem has Optimal Substructure  then we can use the Greedy Algorithm to solve that problem. Optimal Substructure means that optimal solution to the subproblems (optimal local solution) can lead to the optimal solution of the whole problem (optimal global solution). Common Greedy Algoritms Selection Sort Insertion Sort Topological Sort Kr...

  What is Prim's Algorithm? Like Kruskal's Algorithm, Prim's Algorithm is also a Greedy Algorithm and is used to find the Minimum Spanning Tree of a graph. In Prim's Algorithm, we will start from a source and then keep on selecting the next vertex which has minimum distance. Also, we avoid going into a cycle by marking the node which we have already processed as 'visited'. What is the difference between Prim's Algorithm and Kruskal's Algorithm? In Kruskal's Algorithm, our focus was on edges. But in Prim's algorithm, our focus will be on vertices/nodes of the graph. Prim's Algorithm [Time Complexity: O(ElogV), Spave Complexity: O(V)] 1. Take any vertex/node of the graph as starting vertex/node and mark its distance as 0. Also, mark the distance of all other nodes as infinity. 2. Push all the vertices in a min-heap. 3. Do till min-heap is not empty:          4. Extract min from minheap and mark that extracted node as visited.        ...

  What is Minimum Spanning Tree (MST)? A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected and weighted graph. Thus MST is a tree . MST connects all the vertices/nodes of the graph together.  MST does not contain any cycles . MST finds minimum edge weight . MST contains ( V-1) edges , where V is the number of vertices/nodes in the graph.  No. of Spanning Trees possible for a graph (caution: Here I am not talking about Minimum Spanning Tree, but Spanning Tree in general): [ |E|C|V-1| ] - [no. of cycles]       ( here C is Combination of pnc)  Kruskal's Algorithm uses a Disjoint Set Data Structure to find Minimum Spanning Tree. Kruskal's Algorithm is a greedy algorithm.   Kruskal's Algorithm 1. for each node perform makeSet() operation of disjoint set 2. sort each edge of the graph in non-decreasing order by weight  3. for each edge (u,v):          4. if findSet(u) != findSet(v)...

  In this implementation of the disjoint set using a tree, every node will have the following structure                    class Node{                              int rank;                              int data;                              Node parent;                    } Each node will contain a single element and will represent a disjoint set containing that single element. Union by rank  always attaches the shorter tree to the root of the taller tree. Thus, the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node. Time Complexity...

  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...

  Single Source Shortest Path Algorithms BFS Dijkstra's Algorithm Bellman Ford Algorithm Time Complexity O(V^2) O(V^2) O(E.V) Space Complexity O(E) O(V) O(V) Limitation Does not work for weighted graphs in general. If all weight is same in weighted graph or can be made same, then it will work for weighted graph as well Works for weighted as well as unweighted graph. Does not work is there is a negative cycle in the graph. Not able to detect negative cycle. No limitation for working. Works for all kinds of graph as well as able to detect negative cycle in the graph. Only disadvantage is it's runtime complexity is highest here as compared to BFS, Dijkstra and Floyd Warshall Working for Unweighted Graph use this as it is easy to implement Avoid it as we have to implement a min heap too in this case which will slow this down Avoid it as Time Complexity is not good Working for Weighted Graph (no negative cycle) Not supported can be used Avoid it as Time Complexity is not good Workin...