Algorithms that run our Universe

Number of times characters of a string is present in another string

In this article, we have explored the algorithm to find the Number of times characters of a string is present in another string. This can be solved in O(N^2) time.

Algorithms

Transitive Closure Of A Graph using Graph Powering

In this article, we will begin our discussion by briefly explaining about transitive closure and graph powering. We will also see the application of graph powering in determining the transitive closure of a given graph.

Data Structures

Sort a stack using another stack

In this article, we have explored an algorithm to sort a stack using another stack that is by using stack operations like push and pop only. The time complexity of this approach is O(N^2) and space complexity is O(N).

Software Engineering

Idea behind Load Balancer

Load Balancer is placed between the clients and the server accepting incoming requests and distributing the traffic across multiple backend servers using different algorithms.

Algorithms

Transitive Closure Of A Graph using Floyd Warshall Algorithm

In this article, we will begin our discussion by briefly explaining about transitive closure and the Floyd Warshall Algorithm. We will also see the application of Floyd Warshall in determining the transitive closure of a given graph.

Algorithms

Gale Shapley Algorithm for Stable Matching problem

Gale Shapley Algorithm is an efficient algorithm that is used to solve the Stable Matching problem. It takes O(N^2) time complexity where N is the number of people involved.

Algorithms

Minimum Increment and Decrement operations to make array elements equal

We are given an array, we need to find the minimum number of increment and decrement operations (by 1) required to make all the array elements equal. We have explored two approaches where brute force approach take O(N^2) time while the efficient approach O(N logN) time.

Algorithms

Minimum number of increment (by 1) operations to make elements of an array unique

We are given a sorted array which might have duplicate elements, our task is to find the minimum number of increment (by 1) operations needed to make the elements of an array unique. We have solved this using two approaches one using two pointers and other using hashmap.

Algorithms

Hashed Array Tree: Efficient representation of Array

Hashed Array Tree is an improvement over Dynamic Arrays where there can be a large amount of unused allocated memory at a time. This can be visualized as a 2 dimensional array and has been developed by Robert Sedgewick, Erik Demaine and others.

Algorithms

First Unique Character in a String

In this article, we need to find first unique i.e non-repeating character in a given string and return the index or else if no such character exists we return -1.

Algorithms

Reverse alternate groups of K nodes in a Singly Linked List

We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

Algorithms

Divide and Conquer Optimization in Dynamic Programming

Divide and conquer optimization is used to optimize the run-time of a subset of Dynamic Programming problems from O(N^2) to O(N logN). We have demonstrated it with an example.

Algorithms

2-SAT problem

Boolean satisfiability is a NP-complete problem but, a special case of it can be solved in polynomial time. This special case is called case 2-SAT or 2-Satisfiability. We have explained the basic knowledge to understand this problem with depth along with solution.

Algorithms

Applications of Catalan Numbers

In this article, we have explored different applications of Catalan Numbers such as number of valid parenthesis expressions, number of rooted binary trees with n internal nodes, number of ways are there to cut an (n+2)-gon into n triangles and many more.

Algorithms

Knuth's optimization in Dynamic Programming

Knuth's optimization is used to optimize the run-time of a subset of Dynamic programming problems from O(N^3) to O(N^2). We have explained this with a sample problem.

Algorithms

Tim Sort

Tim Sort is a hybrid stable sorting algorithm that takes advantage of common patterns in data, and utilizes a combination of an improved Merge sort and Binary Insertion sort along with some internal logic to optimize the manipulation of large scale real-world data.

Algorithms

Overview of Maximum Flow Problem

The aim of the max flow problem is to calculate the maximum amount of flow that can reach the sink vertex from the source vertex keeping the flow capacities of edges in consideration.

Algorithms

Algorithm to find the maximum power of N that divides M factorial (M!)

We are given two numbers M and N. Our aim is to find the highest power of N that divides Factorial of M (M!). First we have discussed about the Brute Force approach and then we will be discussing this problem using Legendre’s formula.

Algorithms

Maximum houses a Robber can rob

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money the robber can rob tonight without alerting the police. We have solved this problem using Dynamic Programming.

Software Engineering

Implementing Binary search in C++

We have explained in depth how to implement Binary Search in C++. We have covered 3 approaches: Recursive implementation, Iterative implementation and using STL functions.

Algorithms

Kadane's Algorithm for largest subarray sum

Kadane's Algorithm is commonly known for Finding the largest sum of a subarray in linear time O(N). We have presented 3 variants of Kadane's Algorithm along with in-depth explanation of basic ideas.

Algorithms

Binary GCD Algorithm

Binary GCD algorithm or Stein's algorithm is an algorithm that calculates two non-negative integer's largest common divisor by using simpler arithmetic operations than the standard euclidean algorithm and it reinstates division by numerical shifts, comparisons, and subtraction operations.

Algorithms

Finding the Largest Element in an Array

We are given an integer array of size N or we can say number of elements is equal to N. We have to find the largest/ maximum element in an array. The time complexity to solve this is linear O(N) and space complexity is O(1).

Algorithms

Postman Sort

Postman sort works by sorting the integers of an array from their most significant digits to their least significant digits. It is a variant of radix sort.

Algorithms

Number of substrings divisible by 8 but not 3

We need to find total number of substrings that are divisible by 8 but not 3 in the given string. We have solved this problem using Dynamic Programming in linear time O(N) where the brute force approach takes O(N^2) time.