Kosaraju’s algorithm is a linear time algorithm for finding all strongly connected components (SCCs) in a directed graph. The algorithm was developed by S. Rao Kosaraju in 1978, and it is widely used due to its simplicity and efficiency. The algorithm works by performing two depth-first searches (DFS) on the graph. First, it performs a … Read more
Tarjan’s algorithm is a graph algorithm that finds strongly connected components (SCCs) in a directed graph. A strongly connected component is a subset of nodes in a graph where every node is reachable from every other node in the subset. The algorithm works by performing a depth-first search on the graph, maintaining a stack of … Read more
In a tree data structure, a leaf node (also called a terminal node) is a node that does not have any children. In other words, a leaf node is a node that is at the end of a branch and has no further sub-nodes. A leaf node is also commonly referred to as a “terminal” … Read more
Permutations and combinations are two fundamental concepts in combinatorics, which is the branch of mathematics concerned with counting and arranging objects. Permutations are arrangements of objects in a specific order. In other words, a permutation is a selection of objects from a set, where the order of selection matters. For example, if we have three … Read more
Detecting cycles in directed graphs is a bit more complicated than in undirected graphs because there are two types of edges – forward and backward – that need to be considered. One way to detect cycles in a directed graph is to use depth-first search (DFS) and maintain a stack of visited vertices. To detect … Read more
In an undirected graph, a cycle is a path that starts and ends at the same vertex, and consists of at least one other vertex that is visited more than once. To detect cycles in an undirected graph, one approach is to use the Depth-First Search (DFS) algorithm. The DFS algorithm starts at a vertex … Read more
In computer science, a binary tree is a tree data structure where each node can have at most two children, referred to as the left child and the right child. The height of a binary tree is the length of the longest path from the root node to a leaf node. In other words, the … Read more
A prime number is a positive integer greater than one that has no positive integer divisors other than one and itself. In simpler terms, a prime number is a number that can only be divided evenly by 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are all prime numbers. On the … Read more
The Maximum Product Subarray problem is a classic problem in computer science that involves finding the maximum product that can be obtained from any contiguous subarray of an input array of numbers. Given an array of n integers, the problem is to find the subarray that has the maximum product of its elements. For example, … Read more
The Rain Water Trapping problem is a classic problem in computer science that involves calculating the amount of water that can be trapped between bars of different heights in a bar chart. In this problem, the bar chart is represented as an array of non-negative integers, where each element represents the height of a bar. … Read more
