Algorithms that run our Universe

Find the Largest lexicographic array with at most K consecutive swaps

For a given array, find the largest lexicographic array which can be obtained from it after performing at most K consecutive swaps.

Problems on Binary Tree

Sum of k smallest elements in Binary Search Tree

Given a binary search tree and a integer k our task is to find out sum of all the elements which is less or equal to the k th smallest element

Problems on Binary Tree

Find k-th smallest element in Binary Search Tree

Given root of the tree and k as input, output K th smallest element. We reduce the time complexity from O(N) to O(log N).

Problems on Binary Tree

Algorithm to convert Binary Search Tree into Balanced Binary Search Tree

In this article, we will explore an algorithm to convert a Binary Search Tree (BST) into a Balanced Binary Search Tree in linear time O(N).

Problems on Binary Tree

Copy a binary tree where each node has a random pointer

We explored an algorithm to copy a binary tree with an additional pointer which points to any random node in the tree. We explored two techniques Naive solution using 2 traversals and Efficient solution using hashing.

Algorithms

Find Maximum Subarray Sum using divide and conquer

We are interested in to find maximum subarray sum (contiguous) of given 1-D array. Array may contain negative and positive numbers which makes this a difficult problem. Brute force will take O(N^2) time while a divide and conquer approach will take O(N log N) time.

Algorithms

Converting Postfix to Infix using Stack

We have explored an algorithm to convert a Postfix expression to Infix expression using Stack. This takes linear time O(N)

Problems on Binary Tree

Learn how to traverse a Binary Tree (Inorder , Preorder , Postorder)

In this article we will learn three Depth first traversals namely inorder, preorder and postorder and their use. These three types of traversals generally used in different types of binary tree. In summary, Inorder: left, root, right; Preorder: root, left, right and Postorder: left, right, root

Algorithms

Find the maximum sum bitonic subsequence

Given a sequence of numbers in an array A[0.......N]. Find the sum of the maximum bitonic subsequence in the array. naive algorithm will take exponential time O(N * (2^N)) but we can reduced it to O(N^2) using Dynamic programming. We will explore naive approach and go into the dynamic programming

Data Structures

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

Problems on Binary Tree

Algorithm for finding minimum or maximum element in Binary Search Tree【O(log V) / O(V)】

Binary Search Tree is a node-based binary tree data structure and finding the maximum or minimum element take O(log N) in average and can take O(N) in the worst case to O(1) in the best case.

Problems on Binary Tree

Algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree

We developed an algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree. The Idea is do the inorder traversal of binary tree and store it in an array.Then find the minimum number of swaps require to sort an array which is the output we want.

Algorithms

Find and print all the paths between two vertices in a graph【O((2^V)*(V+E))】

Given a directed graph, a vertex ‘v1’ and a vertex ‘v2’, print all paths from given ‘v1’ to ‘v2’. The idea is to do Depth First Traversal of given directed graph. Start the traversal from v1. Keep storing the visited vertices in an array say path[]. If we reach the vertex v2, pathExist becomes true

Algorithms

Find Mother Vertex in a Graph【O(V+E)】

mother vertex in a graph is a vertex from which we can reach all the nodes in the graph through directed path. If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).

Algorithms

Kosaraju's Algorithm for Strongly Connected Components 【O(V+E)】

Kosaraju algorithm is a DFS based algorithm used to find Strongly Connected Components(SCC) in a graph. It is based on the idea that if one is able to reach a vertex v starting from vertex u, then one should be able to reach vertex u starting from vertex v

Algorithms

Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming【O(M*N)】

Count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down. Brute force approach takes exponential time while dynamic programming takes O(M*N) time complexity

Algorithms

Using Farach Colton and Bender Algorithm to solve LCA【O(V) query】

The basic idea of Farach Colton and Bender Algorithm is to traverse all the nodes using the Depth First Search graph traversal and keep a record of all the visited nodes and there corresponding heights. This allows to answer LCA queries in O(V) time complexity

Algorithms

Finding the Lexicographical Next Permutation in O(N) time complexity

In Lexicographical Permutation Algorithm we will find the immediate next smallest Integer number or sequence permutation. Finding all permutations take O(N!) time complexity but we present an efficient algorithm which can solve this in O(N) time complexity

Algorithms

Heap’s algorithm for generating permutations

Heap's Algorithm is used to generate all the possible permutation of n-decimals of a number. It generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. For N numbers, it takes O(N!) time complexity

Algorithms

Algorithm to find cliques of a given size k【O(n^k) time complexity】

We can find all the 2-cliques by simply enumerating all the edges. To find k+1-cliques, we can use the previous results. Compare all the pairs of k-cliques. If the two subgraphs have k-1 vertices in common and graph contains the missing edge, we can form a k+1-clique.

Algorithms

Minimum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the minimum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)

Algorithms

Maximum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the maximum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)

Data Structures

Understanding Bit mask/ Bit map in depth

A bit mask is a data structure, usually an integer or array of bits, that represent a bit pattern which signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

Algorithms

Greedy approach to find a single maximal clique in O(V^2) time complexity

There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm in O(V^2) time complexity

Algorithms

Johnson Algorithm to find the shortest paths between all pair of vertices

Johnson Algorithm is used to find shortest paths between every pair of vertices in a given weighted directed graph and here weights may be negative. Johnson Algorithm uses both Dijkstra and Bellman-Ford algorithms as subroutines.