Edge Types With DFS traversal of Graph, only some edges will be traversed. These edges will form a tree, called the depth-first-search tree starting at the given root, and the edges in this tree are called tree edges. We can classify the various edges of the graph based on the [...]
Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute an item's index in the final, sorted array. Counting sort assumes that each of the n input elements in a list has a key value ranging from 0 [...]
Articulation Point Let G= (V, E) be a connected undirected graph. An articulation point (or cut vertex) of G is a vertex whose removal disconnects G. In other words a vertex v is an articulation point if removing v increases the number of connected components. Nodes having color red in [...]
A directed acyclic graph(or DAG for short) is a directed graph that contains no cycles. In a DAG, a source is a vertex without incoming edges; a sink is a vertex without outgoing edges. Each DAG contains at least one source and one sink. Important points :- After removing a [...]
Introduction Segment Tree data structure allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. This includes finding the sum of consecutive array elements a[l…r], or finding the minimum element in a such a range in O(logn) time. Segment Tree is a [...]
Introduction A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a red-black tree's node structure would be: enum Colour{ red, black }; [...]
Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n). For example Input : arr[] = {1, 10, 5} Output : 5 Sorted array would be {1, 5, 10} and maximum adjacent difference would be 10 - 5 [...]
Introduction In this article, we’ll show several algorithms for searching for a pattern in a text. The fundamental string searching (matching) problem is defined as follows: given two strings – a text and a pattern, determine whether the pattern appears in the text. Naive Method For every position in the [...]
Rotation of the array means that each element is shifted right or left by one index. In case of right rotation the last element of the array is moved to the first place. For example Input : Given array A = [3, 8, 9, 7, 6] and K = 3 [...]
The analysis of the non-recursive version of Depth First Search is identical to Breadth First Search. We first consider a rough analysis of the algorithm in order to develop some intuition. We then build on this analysis to provide a more accurate estimate. Here is the pseudocode for the algorithm along with [...]