Siddharth Agarwal - OpenGenus IQ: Learn Algorithms, DL, System Design

Range Minimum query using segment tree [O(log N) update + O(log N) query]

In this article, we have solved the Range Minimum Query using Segment tree which takes O(log N) time for both update and range query. This is one of the best approaches to solve this problem.

Algorithms

Range Minimum query using square root decomposition [O(1) update + O(sqrt N) query]

In this article at OpenGenus, we have solved the Range Minimum Query problem using Square Root Decomposition which takes constant time O(1) for update and O(square root of N) time for range query.

Algorithms

Range Minimum query using Naive algorithm [O(1) update + O(N) query]

In the naive approach for range minimum query, we can execute the update query in constant time which is efficient and the best case but the query operation takes linear time O(N) which is slow depending upon number of elements and queries.

Algorithms

Find the number of subsets with given Bitwise OR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the Bitwise OR value of all elements in the subset. This can be solved using Dynamic Programming in polynomial time.

Algorithms

Find the number of subsets of an array having a given XOR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

Algorithms

Subset of maximum size with no pair sum divisible by 'K'

Our focus is to find the subset of largest size in which the sum of elements of a pair is not divisible by K. Using mathematical ideas, we solved it in linear time.

Algorithms

Find number of subsets with sum divisible by given number M

Find the number of subsets with sum divisible by given number M. We solved this using a Dynamic Programming approach with time complexity O(N * M).

Algorithms

Find if a Subset with sum divisible by m exist

In this article, we find if a Subset with sum divisible by m exist. A naive approach takes O(2^N) time while dynamic programming takes O(N*M) time

Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

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.

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