DATA STRUCTURES AND ALGORITHM

Order Notation
 Array

Vector in C++
#include <bits/stdc++.h>
[Link]

In C++, vector is a dynamic array with the ability to resize itself

automatically when an element is inserted or deleted
Decleration/Initilization

Functions
Dutch National Flag Algorithm
It is a programming problem proposed by Edsger Dijkstra. The flag of the
Netherlands consists of three colors: white, red, and blue. The task is to
randomly arrange balls of white, red, and blue in such a way that balls of the
same color are placed together. For DNF (Dutch National Flag), we sort an
array of 0, 1, and 2's in linear time that does not consume any extra space. We
have to keep in mind that this algorithm can be implemented only on an array
that has three unique elements.

Think of array at any state and it is divided into {sorted(with 0’s) sorted (with
1’s) ,unsorted(0,1,2) , sorted(with 2’s)} now start iterating from unsorted and
when 0 detected sorted(with 0’s )length increases and unsorted length
increases and when 1 is detected (sorted with 1’s length increase) and when 2
is detected sorted(with 2’s) length increase.

Explanation:[Link]

CASES :
○​ If array [mid] =0, then swap array [mid] with array [low] and
increment both pointers once.
○​ If array [mid] = 1, then no swapping is required. Increment mid
pointer once.
○​ If array [mid] = 2, then we swap array [mid] with array [high] and
decrement the high pointer once.

[Link] array of 0,1,2 in O(n) time.

Moore’s Voting Algorithm-
[Link]
Used to find the majority element (occurrence >n/2) in an array.

This is a two-step process:

●​ The first step gives the element that may be the majority
element in the array. If there is a majority element in an
array, then this step will definitely return majority
element, otherwise, it will return candidate for majority
element.
●​ Check if the element obtained from the above step is the
majority element. This step is necessary as there might be
no majority element.

[Link] Majority element.

unordered_map
an unordered_map is like a data structure of dictionary type that
stores elements in itself. It contains successive pairs (key, value),
which allows fast retrieval of an individual element based on its
unique key.
Binary Search

Lower Bound : Min. index i such that arr[i]>=x.

Upper Bound : Min index i such that arr[i]>x.

First Occurrence: lower_bound

Using C++ STL

Using Binary Search

Last Occurrence: upper_bound - 1

Using C++ STL

Using Binary Search

Sorting

sort() in C++ STL

Ascending order(default)

Descending order(can also use comparator greater<int>() )

1)Selection Sort-
Time complexity is O(n^2)

1)​ Bubble Sort

Time Complexity is O(n^2)

3)Insertion Sort : insert the element i.e shift the other element to right.

Time complexity: O(N^2)

4)Merge Sort:
5)Quick Sort
Time Complexity Analysis
SLIDING WINDOW

Sliding Window Technique is a method used to efficiently solve problems

that involve defining a window or range in the input data (arrays or
strings) and then moving that window across the data to perform some
operation within the window. This technique is commonly used in
algorithms like finding subarrays with a specific sum, finding the longest
substring with unique characters, or solving problems that require a
fixed-size window to process elements efficiently.

[Link]
ow-technique
 Kadane’s Algorithm
The idea of Kadane’s algorithm is to traverse over the array from left to
right and for each element, find the maximum sum among all subarrays
ending at that element. The result will be the maximum of all these
values.
This means that maxEnding at index i = max(maxEnding at index (i – 1)
+ arr[i], arr[i]) and the maximum value of maxEnding at any index will be
our answer.

[Link]
Modified Kadane’s Algorithm
To Calculate the maximum product sub array
●​ Create 3 variables, currMin, currMax and maxProd initialized to

the first element of the array.

●​ Iterate the indices 0 to N-1 and update the variables:

○​ currMax = maximum(arr[i], currMax * arr[i],

currMin * arr[i])

○​ currMin= minimum(arr[i], currMax * arr[i], currMin

* arr[i])

○​ update the maxProd with the maximum value for

each index.

●​ Return maxProd as the result.

[Link]
Sweep Line Algorithm:
The sweep line algorithm is an efficient method for solving problems
involving intervals or segment. The idea is to convert the arrival time and
departure time of each train in the form of (x, y) coordinate, and then apply
the sweep line algorithm to finding the maximum number of overlap at
any time.

Marking Indices:
Kind of checking if that index is present.

Due to %n past value of arr[i]-1 index can also be checked

[Link]
array-set-3/

Storing two Values at 1 index:

The idea is to use multiplication and modular arithmetic to store two
elements at each index. Assume M = maximum element in the array + 1.
Now, if we want to store two numbers say X and Y at any index, then we
can store X + (Y * M) at that index. This will work because using X + (Y *
M), we can get the first value by using modulo: (X + (Y * M)) mod M = X
and the second value by using (X + (Y * M)) / M = Y.

[Link]
-set-2-o1-extra-space/
 Strings

Hashing Function:
To uniquely identify a string

Two Hash value may match but it rarely happens which is called hash collision/spurious
hit.
Rabin-Karp Algorithm:

Based on the Hashing . It is used to compare if pattern string is in the main text or not.

Follow the above steps to calculate hashing then-

Note that pow() function is avoided because it is computationally inefficient as well as
overflow may occur. Also here q is INT_MAX to avoid
Collision and mod of q is done to avoid overflow.
Longest Prefix Suffix Array:

Given a string s, the task is to find the length of the longest proper prefix
which is also a suffix. A proper prefix is a prefix that doesn’t include
whole string. For example, prefixes of “abc” are “”, “a”, “ab” and “abc” but
proper prefixes are “”, “a” and “ab” only.

Examples:

Input: s = “aabcdaabc”​
Output: 4​
Explanation: The string “aabc” is the longest proper prefix which is also
the suffix.

Input: s= “ababab”​
Output: 4​
Explanation: The string “abab” is the longest proper prefix which is also
the suffix.

Input: s = “aaaa”​
Output: 3​
Explanation: The string “aaa” is the longest proper prefix which is also the
suffix.
Approach is to maintain an LPS array which at any i store the the longest
length of matching prefix and suffix.

lps[0] is always 0 since a string of length one has no non-empty proper

prefix. We store the value of the previous LPS in a variable len, initialized
to 0. As we traverse the pattern, we compare the current character at
index i, with the character at index len.

Case 1 – pat[i] = pat[len]: this means that we can simply extend the LPS
at the previous index, so increment len by 1 and store its value at lps[i].

Case 2 – pat[i] != pat[len] and len = 0: it means that there were no

matching characters earlier and the current characters are also not
matching, so lps[i] = 0.

Case 3 – pat[i] != pat[len] and len > 0: if at any index prefix and suffix (i.e i
and len) char is not equal then since string of [0 to len-1] may have the
matching prefix and suffix and we will check the lps value at that point i.e
(len-1) and move to that no. of suffix and again start matching.
[Link]
KMP Algorithm:
Given two strings txt and pat, the task is to return all indices of
occurrences of pat within txt.

We initialize two pointers, one for the text string and another for the
pattern. When the characters at both pointers match, we increment both
pointers and continue the comparison. If they do not match, we reset the
pattern pointer to the last value from the LPS array, because that portion
of the pattern has already been matched with the text string. Similarly, if
we have traversed the entire pattern string, we add the starting index of
occurrence of pattern in text, to the result and continue the search from
the lps value of last element of the pattern.

Let’s say we are at position i in the text string and position j in the pattern
string when a mismatch occurs:

●​ At this point, we know that pat[0..j-1] has already matched with

txt[i-j..i-1].

●​ The value of lps[j-1] represents the length of the longest proper

prefix of the substring pat[0..j-1] that is also a suffix of the same

substring.

●​ From these two observations, we can conclude that there’s no

need to recheck the characters in pat[0..lps[j-1]]. Instead, we can

directly resume our search from lps[j-1].

[Link]
 Bitwise Operator
[Link]
[Link]
[Link]
Interesting Facts About Bitwise Operators
1. The left-shift and right-shift operators should not be used for
negative numbers.

If the second operand(which decides the number of shifts) is a negative

number, it results in undefined behavior in C. For example, results of both
1 <<- 1 and 1 >> -1 are undefined. Also, if the number is shifted more than
the size of the integer, the behavior is undefined. For example, 1 << 33 is
undefined if integers are stored using 32 bits. Another thing is NO shift
operation is performed if the additive expression (operand that decides no
of shifts) is 0. See this for more details.

2. The bitwise OR of two numbers is simply the sum of those two

numbers if there is no carry involved; otherwise, you add their bitwise
AND.

Let’s say, we have a=5(101) and b=2(010), since there is no carry involved,
their sum is just a|b. Now, if we change ‘b’ to 6 which is 110 in binary, their
sum would change to a|b + a&b since there is a carry involved.

3. The & operator can be used to quickly check if a number is odd or

even.

The value of the expression (x & 1) would be non-zero only if x is odd,

otherwise, the value would be zero.

Get Bit:

This method is used to find the bit at a particular position(say i) of the

given number N. The idea is to find the Bitwise AND of the given number
and 2i that can be represented as (1 << i). If the value return is 1 then the
bit at the ith position is set. Otherwise, it is unset.
return ((num & (1 << i)) != 0);
 Set Bit:

This method is used to set the bit at a particular position(say i) of the given
number N. The idea is to update the value of the given number N to the
Bitwise OR of the given number N and 2i that can be represented as (1 <<
i). If the value return is 1 then the bit at the ith position is set. Otherwise, it
is unset.
return num | (1 << i);

Clear Bit:

This method is used to clear the bit at a particular position(say i) of the

given number N. The idea is to update the value of the given number N to
the Bitwise AND of the given number N and the compliment of 2i that can
be represented as ~(1 << i). If the value return is 1 then the bit at the ith
position is set. Otherwise, it is unset.
int mask = ~(1 << i);

return num & mask;

Define Masks

Note:-
 STACK , QUEUE & DEQUE

Stack: LIFO (Last In First Out) Principle

Declaration & Functions:

stack <int> stack;

[Link](22);
[Link]();
[Link]()
[Link]()
Queue: First in, First out" (FIFO)

Declaration & Functions:

queue<int> q;
[Link](10);
[Link]();
[Link]()
[Link]();
[Link]();
Deque:

Functions:
deque<int> gquiz;
gquiz.push_back(10);
gquiz.push_front(20);
[Link]();
[Link]();
gquiz.pop_front();
gquiz.pop_back();
Linked List
Floyd’s Cycle Finding / Hare-Tortoise algorithm

Detecting if loop exist in linked list:

When slow pointer enters the loop, the fast pointer must be inside the

loop. if we consider movements of slow and fast pointers, we can notice

that distance between them (from slow to fast) increase by one after

every iteration. As they continue to move within the cycle, this distance

will eventually equal the cycle length n. At this point, since the distance

wraps around the cycle and both pointers are moving within the same

cycle, they will meet.

Finding the start point of loop:
Distance travelled by fast pointer = 2 * (Distance travelled by slow
pointer)

(m + n*x + k) = 2*(m + n*y + k)

m + k = (x – 2y)*n

m = i*n – k
we reset one of the pointers – let’s say the slow pointer to the head of the
linked list. The other pointer, the fast pointer, remains at the point where
the two pointers initially met. Both pointers are then moved one node at a
time. As they traverse the list, the pointer that was reset to the head will
cover the distance m to the start of the loop. Since the total distance m + k
covered by the slow pointer is a multiple of the cycle length n, both
pointers will eventually converge at the start of the cycle. This
simultaneous movement ensures that the pointer starting from the head
meets the pointer at the start of the cycle, there by successfully
identifying the beginning of the loop.
 Binary Tree Data Structure

​ Creating Binary Tree:

Properties of Binary Tree
●​ The maximum number of nodes at level L of a binary tree is 2^L

●​ The maximum number of nodes in a binary tree of height H is

(2^H) – 1

●​ Total number of leaf nodes in a binary tree = total number of

nodes with 2 children + 1

●​ In a Binary Tree with N nodes, the minimum possible height or

the minimum number of levels is Log2(N+1)

●​ A Binary Tree with L leaves has at least | Log2L |+ 1 levels

The height of a tree is defined as the number of edges on the longest path from the
root to a leaf node. A leaf node is a node that does not have any children.

1. Traversal in Binary Tree

Depth-First Search (DFS) algorithms: DFS explores as far down a branch

as possible before backtracking. It is implemented using recursion. The
main traversal methods in DFS for binary trees are:

1)​ Preorder Traversal: Visits the node first, then left subtree, then
right subtree.
​ ​ ​ ​ OUTPUT: ABDEC
 2)​ Inorder Traversal: Visits left subtree, then the node, then the right
subtree.​
​ ​ ​ ​ OUTPUT: DBEAC

​
 3)​ Postorder Traversal: Visits left subtree, then right subtree, then
the node.
​ ​ ​ ​ OUTPUT: DEBCA

Breadth-First Search (BFS) algorithms: BFS explores all nodes at the

present depth before moving on to nodes at the next depth level. It is
typically implemented using a queue. BFS in a binary tree is commonly
referred to as Level Order Traversal.
Vertical Traversal:
Output: ​
4​
2​
1 5 6​
3 8​
7​
9
Morris Traversal:

Implementation for inorder

​ ​ BINARY SEARCH TREE

In a BST , at any node its left subtree contains values less than the node
and the right subtree contains values greater than the node.
Insertion in Binary Search Tree (BST)

A new key is always inserted at the leaf by maintaining the property of the
binary search tree. We start searching for a key from the root until we hit a
leaf node. Once a leaf node is found, the new node is added as a child of
the leaf node.
Deletion in Binary Search Tree (BST)

Deleting a leaf node simple in BST. Simply delete the leaf node.

Deleting a single child node is also simple in BST. Copy the child to the
node and delete the node.
Deleting a node with both children is not so simple. Here we have to
delete the node is such a way, that the resulting tree follows the
properties of a BST. The trick is to find the inorder successor of the node.
Copy contents of the inorder successor to the node, and delete the inorder
successor.
 RED BLACK TREE

A Red-Black Tree is a self-balancing binary search tree where each node

has an additional attribute: a color, which can be either red or black. The
primary objective of these trees is to maintain balance during insertions
and deletions, ensuring efficient data retrieval and manipulation.
​ ​ ​ ​ ​ HEAP
A Heap is a special Tree-based Data Structure that has the
following properties.
●​ It is a Complete Binary Tree.
●​ It either follows max heap or min heap property.

Max-Heap: The value of the root node must be the greatest

among all its descendant nodes and the same thing must be done
for its left and right sub-tree also.

Min-Heap: The value of the root node must be the smallest

among all its descendant nodes and the same thing must be done
for its left and right sub-tree also.
Heap can be implemented as array with following indices
properties:

Operations on Heap:
[Link]
Following are the implementation for max-heap::
●​ Insert: Adds a new element at the end of array and maintain heap

property by moving up iteratively and swapping if violated. O(logn).

 .

●​ Peek: Returns the minimum/maximum element without

removing it. O(1).

●​ Heapify: Reorganizes a subtree for a given node to ensure the

heap property [Link] places the index to its correct

[Link] of all it compares with its both child and

whichever child is disturbed recursively it again heapify for

that node.
●​ Extract Min/Max: Removes and returns the min/max element

from the heap.

●​ Increase/Decrease Key: Changes the value of an existing

element in the heap.

●​ Delete: Removes a specific element from the heap.

Build Heap (from given array):

Since leaf nodes don't have any child so we should not heapify that node i.e leaf nodes are
always from n/2 to n so iteratively call heapify from n/2 -1 to 0.

Time Complexity: O(N)

Auxiliary Space: O(N) (Recursive Stack Space)
Heap Sort
First convert the array into heap using build heap mechanism and then extract max and put
it to the last and do this for all elements.

Time Complexity: O(n log n)

Auxiliary Space: O(log n), due to the recursive call stack. However,
auxiliary space can be O(1) for iterative implementation.
​ ​ ​ Heap in C++ STL
[Link]

STL Functions for Heap Operations

1.​ make_heap(): Converts given range to a heap.

​ vector<int> v1 = { 20, 30, 40, 25, 15 };

​ make_heap([Link](), [Link]());
cout << [Link]() << endl;

2.​ push_heap(): Arrange the heap after insertion at the end.

vc.push_back(50);

push_heap([Link](), [Link]());

3.​ pop_heap(): Moves the max element at the end for deletion.

pop_heap([Link](), [Link]());

vc.pop_back();
 4.​ sort_heap(): Sort the elements of the max_heap to ascending

order.

​ ​ sort_heap([Link](), [Link]());

5.​ is_heap(): Checks if the given range is max_heap.

is_heap([Link](), [Link]())

6.​ is_heap_until(): Returns the largest sub-range that is max_heap.

​ ​ ​ auto it = is_heap_until([Link](), [Link]());

​
​ ​ ​ Priority Queue
Priority queue can be arranged w.r.t their priority at the time of insertion (can be read here )
but in c++ STL priority queue is implemented with the priority of the largest element so it is
implemented using maxHeap.

​ ​

Functions:

priority_queue<int> pq;
[Link](arr[i]);
[Link]();
[Link]();
[Link]()

Custom Priority-queue:
​ ​ Below is minHeap implementation-

​ ​ class cmp{
​ ​ ​ public:

​ ​ bool operator() (Node* a,Node * b){

return a->data>b->data; }
 };

​ ​ priority_queue <Node*,vector <Node*>,cmp> p;

Another method to declare custom comparator is to use lambda

function,both should be written in same function as shown below:

auto cmp = [&](pair<int,int> a,pair<int,int> b){

return mat[[Link]][[Link]]>mat[[Link]][[Link]];
};

priority_queue <pair<int,int>,vector<pair<int,int>>,decltype(cmp)>
p(cmp);
​ ​ ​ ​ ​ Graph

A Graph is composed of a set of vertices( V ) and a set of edges( E ).

The graph is denoted by G(V, E).

[Link]
and-algorithm-tutorials/
[Link]
Types Of Graphs
Representation of Graph Data Structure:

1)Adjacency Matrix :
[Link]
For a graph with V vertices, the adjacency matrix A is a V X V matrix or 2D
array.

●​ A[i][i] ​= 1, there is an edge between vertex i and vertex j.

●​ A[i][i] ​= 0, there is NO edge between vertex i and vertex j

2)Adjacency List:
[Link]
Basic Operations on Graph Data Structure:
Below are the basic operations on the graph:

●​ Insertion or Deletion of Nodes in the graph

○​ Add and Remove vertex in Adjacency List representation of

Graph

○​ Add and Remove vertex in Adjacency Matrix representation of

Graph

●​ Insertion or Deletion of Edges in the graph

○​ Add and Remove Edge in Adjacency List representation of a

Graph

○​ Add and Remove Edge in Adjacency Matrix representation of a

Graph

Difference between Tree and Graph:

Tree is a restricted type of Graph Data Structure, just with some more
rules. Every tree will always be a graph but not all graphs will be trees.
Linked List, Trees, and Heaps all are special cases of graphs.
Traversal in Graph

1)​Breadth First Search ( BFS ) :

In BFS first all neighbours of node are visited then next neighbour of all neighbours is
[Link] is very similar to level order traversal of tree.
2) Depth First Search ( DFS ) :

DFS can be implemented via Backtracking and recursion . It can also be implemented using
stack. Below is a recursive implementation of DFS algo.
Topological Sorting:
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering
of vertices such that for every directed edge u-v, vertex u comes before v
in the ordering.

Note: Topological Sorting for a graph is not possible if the graph is not a
DAG. Topological Sorting is not unique.

Output: 5 4 2 3 1 0

Topological Sorting Using DFS.

Kahn’s algorithm for Topological Sorting

In-degree : number of incoming edges to a node is defined as indegree.

Kahn’s Algorithm : based on BFS.

Add all nodes with in-degree 0 to a queue.
●​ While the queue is not empty:

○​ Remove a node from the queue.

○​ For each outgoing edge from the removed node,

decrement the in-degree of the destination node

by 1.

○​ If the in-degree of a destination node becomes 0,

add it to the queue.

●​ If the queue is empty and there are still nodes in the graph, the

graph contains a cycle and cannot be topologically sorted.

●​ The nodes in the queue represent the topological ordering of the

graph.
Dense Graph vs. Sparse Graph

●​ Dense Graph:

○​ Has a large number of edges, close to the

maximum possible.

○​ Typical edge count is O(V^2).

○​ Example: A complete graph where every vertex is

connected to every other vertex.

●​ Sparse Graph:

○​ Has relatively few edges.

○​ Typical edge count is O(V) or slightly more.

○​ Example: A road network where only a few cities

are directly connected by roads

Sink Node

Those nodes such that no edges emerge out from them or nodes with 0
outdegree.

1 and 3 are sink node

Dijkstra’s Algorithm
This algorithm is used for finding the shortest path in a non-negative weighted [Link] is
based on the fact calculating the min dist next to any point from the existing min distance.

Time Complexity: O(E * logE). Auxiliary Space: O(V+E).

●​ Dijkstra’s algorithm doesn’t work for graphs with negative weight.

●​ For dense graphs T.C is O(V^2logV).Therefore it is best suited for Sparse

graphs.

●​ We can implement this in O(V^2) without a priority queue using_Method1

which will be beneficial for dense graphs.

Connected Components:
Group of nodes in undirected-graphs which are reachable from each
[Link] Connected components is simple and can be done by simple
DFS/BFS.

Strongly Connected Components (SCC):

In a directed graph, a Strongly Connected Component is a subset of
vertices where every vertex in the subset is reachable from every other
vertex in the same subset by traversing the directed edges.
Kosaraju’s Algorithm:
Here’s a simplified version of Kosaraju’s Algorithm:

1.​ DFS on Original Graph: Record finish times /topological sorting.

2.​ Transpose the Graph: Reverse all edges.

3.​ DFS on Transposed Graph: Process nodes in order of decreasing

finish times to find SCCs.

Eulerian path and circuit for directed graph:
Eulerian Path is a path in a graph that visits every edge exactly once.
Eulerian Circuit/Cycle is an Eulerian Path that starts and ends on the same
vertex. ​

​
Eulerian Cycle

An undirected graph has Eulerian cycle if following two conditions are

true.

1.​ All vertices with non-zero degree are connected. We don’t care

about vertices with zero degree because they don’t belong to

Eulerian Cycle or Path (we only consider all edges).

2.​ All vertices have even degree.

Eulerian Path

An undirected graph has Eulerian Path if following two conditions are true.

1.​ Same as condition (1) for Eulerian Cycle.

2.​ If zero or two vertices have odd degree and all other vertices have

even degree.

Single node graph is always eulerian.

Euler Circuit in a Directed Graph

A directed graph has an eulerian cycle if following conditions are true

1.​ All vertices with nonzero degree belong to a single strongly

connected component. SCC can be checked as:

●​ Traverse DFS/BFS, if any of them is non visited

then not SCC.

●​ Reverse the edges and again do DFS/BFS if all of

them are visited then SCC otherwise not.

2.​ In degree is equal to the out degree for every vertex.

Floyd Warshall Algorithm

It is used to find the shortest paths between all pairs of nodes in a
weighted graph. This algorithm is highly efficient and can handle graphs
with both positive and negative edge weights.
It calculates path b/w source and dest using intermediate nodes and
iterating for all possible combinations.

Time Complexity: O(V^3) Auxiliary Space: O(1),

●​ This algorithm works for both the directed and undirected weighted

graphs. But, it does not work for the graphs with negative cycles

(where the sum of the edges in a cycle is negative).

●​ If a negative cycle is there then diagonal values will be negative

(ideally should be 0 )which indicate the negative cycle.

●​ No matter how many edges are there in the graph the Floyd

Warshall Algorithm runs for O(V3) times therefore it is best suited

for Dense graphs.

Bellman–Ford Algorithm
Bellman-Ford is a single source shortest path algorithm for directed
graphs. It effectively works in the cases of negative edges and is able to
detect negative cycles as well. It works on the principle of relaxation of
the edges.

Principle of Relaxation of Edges

●​ Relaxation means updating the shortest distance to a node if a

shorter path is found through another node. For an edge (u, v)

with weight w:

○​ If going through u gives a shorter path to v from

the source node (i.e., distance[v] > distance[u] +

w), we update the distance[v] as distance[u] + w.

●​ In the bellman-ford algorithm, this process is repeated (V – 1)

times for all the edges.

Time Complexity : O(V*E)

Bridges
An edge in an undirected connected graph is a bridge if removing it
disconnects the graph. For a disconnected undirected graph, the definition
is similar, a bridge is an edge removal that increases the number of
disconnected components.

Tarjan’s Algorithm:
To implement this algorithm, we need the following data structures –

●​ visited[ ] = to keep track of the visited vertices to implement DFS

●​ disc[ ] = to keep track when for the first time that particular vertex

is reached

●​ low[ ] = to keep track of the lowest possible time by which we

can reach that vertex ‘other than parent’ so that if edge from

parent is removed can the particular node can be reached other

than parent
Find Bridges in a graph using Tarjan’s Algorithm:

We will traverse nodes using DFS and will mark disc and low time to each
node.

While traversing adjacent nodes (say ‘v’ ) of a particular node (say ‘u’ ),
then 3 cases arise –

1. v is parent of u then,

●​ skip that iteration.

2. v is visited then,

●​ update the low of u i.e. low[u] = min( low[u] , disc[v]) this arises

when a node can be visited by more than one node, but low is to

keep track of the lowest possible time so we will update it.

3. v is not visited then,

●​ call the DFS to traverse ahead

●​ now update the low[u] = min( low[u], low[v] ) as we know v can’t

be parent cause we have handled that case first.

●​ now check if ( low[v] > disc[u] ) i.e. the lowest possible to time to

reach ‘v’ is greater than ‘u’ this means we can’t reach ‘v’ without

‘u’ so the edge u -> v is a bridge.

Find SCC’s in a graph using Tarjan’s Algorithm:
Minimum Spanning Tree (MST)
A spanning tree is a subset of the edges of the graph that forms a tree
(acyclic) where every node of the graph is a part of the tree.
The minimum spanning tree has all the properties of a spanning tree with
an added constraint of having the minimum possible weights among all
possible spanning trees. Like a spanning tree, there can also be many
possible MSTs for a graph.
Prim’s Algorithm
Prim’s Algorithm is used to obtain a minimum spanning tree.​In this algorithm we
create a priority queue and push the vertex with weight and select the top element.

Time Complexity: O(E*log(E))

Auxiliary Space: O(V+E)
 Dynamic Programming

It is mainly an optimization over plain recursion. Wherever we see a

recursive solution that has repeated calls for the same inputs, we can
optimize it using Dynamic [Link] idea is to simply store the
results of subproblems so that we do not have to re-compute them when
needed later. This simple optimization typically reduces time complexities
from exponential to polynomial.

Top-Down Approach (Memoization):

In the top-down approach, also known as memoization, we keep the
solution recursive and add a memoization table to avoid repeated calls of
same subproblems.

●​ Before making any recursive call, we first check if the

memoization table already has solution for it.

●​ After the recursive call is over, we store the solution in the

memoization table.
Bottom-Up Approach (Tabulation):

In the bottom-up approach, also known as tabulation, we start with the

smallest subproblems and gradually build up to the final solution.

●​ We write an iterative solution (avoid recursion overhead) and

build the solution in bottom-up manner.

●​ We use a dp table where we first fill the solution for base cases

and then fill the remaining entries of the table using recursive

formula.

●​ We only use recursive formula on table entries and do not make

recursive calls.

Space Optimization:

The idea is to store only the values that are necessary to generate the

result for the current state of the DP [Link] storing the states that

do not contribute to the current state.

 Greedy Approach
[Link]

A greedy algorithm is a problem-solving technique that makes the best

choice at each step, based on the current situation, without considering the
overall problem. The goal is to reach a globally optimal solution by making
a series of locally optimal choices.

Some common ways to solve Greedy Problems:

1). Sorting
2). Using Priority Queue or Heaps
3). Arbitrary