Algorithms that run our Universe

Xiaolin Wu's Line Drawing Algorithm

Xiaolin Wu's Line Drawing Algorithm is a recognized Line Drawing Algorithm in Computer Graphics which is used to produce Anti-aliased lines. In this article, we have explored this in depth.

Algorithms

Make String Stable [using Stack]

Given a string with opening and closing braces, our problem is to find the minimum number of operations to make the string stable. This can be solved efficiently using Stack.

Algorithms

Check if a string is a subsequence of another string

In this problem, we will see how we can check whether a string is a subsequence of another string. We have solved this in O(N) time using an efficient approach.

List of Mathematical Algorithms

Find index such that sum of left sub-array = right sub-array (Equilibrium Index)

For a given array, we need to find an index such that sum of left sub-array = right sub-array also called the Equilibrium Index. We solve this using brute force approach O(N^2) and using prefix array in linear O(N) time.

Algorithms

Finding LCM of an array of numbers

Find the LCM of the given array of positive numbers. We have explored 2 approaches: one using GCD and other without using GCD.

Algorithms

Finding 2 elements with difference k in a sorted array

This article discusses how to check the existence of and find 2 elements with difference k in sorted array. We have explored 3 approaches and solved it in linear time O(N).

Algorithms

Minimum number of nodes to be removed such that no subtree has more than K nodes

The article contains editorial + implementation for Finding minimum number of nodes to be removed such that no sub tree has more than K nodes.

Algorithms

Number of substrings with exactly k distinct characters

In this problem, we are given a string and our job is to count the total number of substrings of the given string that contains exactly k distinct characters. We have explored 3 approaches to solve this.

Algorithms

Different ways to sort a Queue

We will be discussing 4 different ways to sort a queue. This involves sorting a Queue using auxiliary array, O(1) space, using recursion and using a stack.

Algorithms

Implementing two stacks in one array

We will demonstrate how to implement 2 stacks in one array. Both stacks are independent but use the same array. We need to make sure one stack does not interfere with the other stack and support push and pop operation accordingly.

Algorithms

Reverse first K elements of Queue using Stack

To reverse the first K elements of a queue, we can use an auxiliary stack. We push the first k elements in the stack and pop() them out so and add them at the end of the queue.

Algorithms

Time Complexity of Insertion Sort

The average code and worst case time complexity of Insertion Sort is O(N^2) and the best case time complexity is O(N). The space complexity is O(N) for N elements.

Algorithms

Intersection point of two linked lists

Given two linked lists, where the tail of the second list points to a node in the first list, find the node where both the lists intersect. We need to find the intersection point.

Algorithms

Column Sort Algorithm

Column Sort Algorithm is a non-traditional sorting algorithm for Distributed Memory Clusters (DMC) (means multiple processors). It is a generalization of odd-even merge sort and is used in a parralel system where multiple CPUs are available for use.

Algorithms

Shift OR algorithm for String Matching

Shift OR algorithm uses bitwise techniques to check whether the given pattern is present in the string or not. It is efficient if the pattern length is lesser than the memory-word size of the machine

Algorithms

Move the first element of the linked list to the end

In this problem, given a linked list, we move the first element of the linked list to the end of the linked list.

Problems on Binary Tree

Construct Binary Tree from Inorder and Preorder traversal

We present two approaches to Construct Binary Tree from Inorder and Preorder traversal. We start with background information on constructing Binary Tree from a given traversal or a set of traversals.

Algorithms

Variants of Stable Marriage Problem

We have explored the variants of stable marriage problem like Egalitarian Stable Matching, Minimum Regret Stable Matching, Stable marriage with ties, Stable marriage with incomplete lists and others.

Algorithms

Convert one string to another by changing all occurrence of a character to another

We will be solving Check if one string can be converted to another by changing all occurrence of a character to another character problem using the Union and Find algorithm.

Algorithms

Maximum XOR of two numbers in an array using Trie

Given a list of numbers we need to identify a pair of numbers in the list such that the XOR of those numbers is the maximum possible over all the pairs.

Algorithms

Find k-th smallest element using QuickSelect algorithm

Quickselect is an approach where we use divide and conquer and find the k th smallest element in an average O(N) time.

Algorithms

Longest Alternating Subsequence

Given an array, find the length of the longest alternating subsequence. We solve this using two approaches: Dynamic Programming and Efficient Approach.

Algorithms

Find length of the longest Fibonacci subsequence

We have a strictly increasing array of positive integers. Our task is to find the length of the longest Fibonacci subsequence possible. We will solve this using Brute force and Dynamic Programming.

Algorithms

Next Larger/ Smaller element (using Monotonic Queue)

In this problem, we are given an array and our task is to find the next larger/ smaller element for each element in the array. We have covered brute force approach and Monotonic Queue.

String Algorithms

Minimum number of operations to convert binary string to self-destructing

We will explore algorithms to find the Minimum number of operations to convert a binary string to a self-destructing string.