Data Structures - Lecture - 2

Lecture – 2
Data Structures
Introduction
Data Structures are essential components that help organize and store data efficiently in
computer memory. They provide a way to manage and manipulate data effectively,
enabling faster access, insertion, and deletion operations.
Common data structures include arrays, linked lists, stacks, queues, trees, and graphs,
each serving specific purposes based on the requirements of the problem. Understanding
data structures is fundamental for designing efficient algorithms and optimizing software
performance.
Data Structure
1.2 Data Structure

A data structure is a way of organizing and storing data in a computer so that it can be accessed
and used efficiently. It defines the relationship between the data and the operations that can be
performed on the data.
1.3 Why are Data Structures Important?

Data structures are essential for the following reasons:
 Efficient Data Management: They enable efficient storage and retrieval of data,
reducing processing time and improving performance.
 Data Organization: They organize data in a logical manner, making it easier to
understand and access.
 Data Abstraction: They hide the implementation details of data storage, allowing
programmers to focus on the logical aspects of data manipulation.
 Reusability: Common data structures can be reused in multiple applications, saving
time and effort in development.
 Algorithm Optimization: The choice of the appropriate data structure can
significantly impact the efficiency of algorithms that operate on the data.
1.4 Classification of Data Structures
Data structures can be classified into two main categories:
 Linear Data Structures: These structures store data in a sequential order this
allowing for easy insertion and deletion operations. Examples include arrays, linked
lists, and queues.
 Non-Linear Data Structures: These structures store data in a hierarchical or
interconnected manner this allowing for more complex relationships between data
elements. Examples include trees, graphs, and hash tables.
1.5 Types of Data Structures
Basically, data structures are divided into two categories:
1.5.1 Linear Data Structures:
 Array: A collection of elements of the same type stored in contiguous memory
locations.
 Linked List: A collection of elements linked together by pointers, allowing for
dynamic insertion and deletion.
 Queue: A First-In-First-Out (FIFO) structure where elements are added at the end
and removed from the beginning.
 Stack: A Last-In-First-Out (LIFO) structure where elements are added and removed
from the top.
1.5.2 Non-Linear Data Structures:
 Tree: A hierarchical structure where each node can have multiple child nodes.
 Graph: A collection of nodes connected by edges, representing relationships between
data elements.
 Hash Table: A data structure that uses a hash function to map keys to values,
allowing for fast lookup and insertion.
1.6 Applications of Data Structures

Data structures are widely used in various applications, including:
 Database Management Systems: To store and manage large amounts of structured
data.
 Operating Systems: To manage memory, processes, and files.
 Compiler Design: To represent source code and intermediate code.
 Artificial Intelligence: To represent knowledge and perform reasoning.
 Graphics and Multimedia: To store and process images, videos, and audio data.
Learn Basics of Data Structure:
1.7 Introduction to Linear Data Structures
A data structure refers to organizing and storing data in a computer's memory in a way that
enables efficient access, manipulation, and retrieval of the data. Data structures are fundamental
concepts in computer science and are extensively used in programming and software
development to solve various computational problems.
There are two categories of data structure - linear data structure and non-linear data structure. In
real life, linear data structure is used to develop software, and non-linear data structure is used in
image processing and artificial intelligence.
In this article, we will understand the difference between linear and non-linear data structures.
1.7.1 Linear data structure
A linear data structure is a type of data structure that stores the data linearly or sequentially. In
the linear data structure, data is arranged in such a way that one element is adjacent to its
previous and the next element. It includes the data at a single level such that we can traverse all
data into a single run.
The implementation of the linear data structure is always easy as it stores the data linearly. The
common examples of linear data types are Stack, Queue, Array, LinkedList, and Hashmap, etc.
Here, we have briefly explained every linear data type below:
a. Stack
Users can push/pop data from a single end of the stack. Users can insert the data into the stack
via push operation and remove data from the stack via pop operation. The stack follows the rule
of LIFO (last in first out). Users can access all the stack data from the top of the stack in a linear
manner.
In real-life problems, the stack data structure is used in many applications. For example, the All
web browser uses the stack to store the backward/forward operations.
b. Queue
Queue data structure stores the data in a linear sequence. Queue data structure follows the FIFO
rule, which means first-in-first-out. It is similar to the stack data structure, but it has two ends. In
the queue, we can perform insertion operations from the rear using the Enqueue method and
deletion operations from the front using the deque method.
Escalator is one of the best real-life examples of the queue.
c. Array
The array is the most used Linear data type. The array stores the objects of the same data type in
a linear fashion. Users can use an array to construct all linear or non-linear data structures. For
example, Inside the car management software to store the car names array of the strings is useful.
We can access the element of the array by the index of elements. In an array, the index always
starts at 0. To prevent memory wastage, users should create an array of dynamic sizes.
d. LinkedList
LinkedList data structure stores the data in the form of a node. Every linked list node contains
the element value and address pointer. The address pointer of the LinkedList consists of the
address of the next node. It can store unique or duplicate elements.
1.7.2 Non-linear data structure?
In a non-linear data structure, data is connected to its previous, next, and more elements like a
complex structure. In simple terms, data is not organized sequentially in such a type of data
structure.
It is one type of Non-primitive data structure. In non-linear data structures, data is not stored
linear manner. There are multiple levels of nonlinear data structures. It is also called a multilevel
data structure. It is important to note here that we can't implement non-linear data structures as
easily as linear data structures.
a. Tree
A tree data structure is an example of a nonlinear data structure. It is a collection of nodes where
each node consists of the data element. Every tree structure contains a single root node.
In the tree, every child node is connected to the parent node. Every parent and child node has a
parent-child node relationship. In the tree, Nodes remaining at the last level are called leaf nodes,
and other nodes are called internal nodes.
Types of trees:
1. Binary tree
2. Binary search tree
3. AVL tree
4. Red-black tree
The Heap data structure is also a non-linear tree-based data structure, and it uses the complete
binary tree to store the data.
b. Graph
The graph contains vertices and edges. Every vertex of the graph stores the data element. Edges
are used to build a vertices relationship. Social networks are real-life examples of graph data
structure.
Here, we can consider the user as a vertex, and the relation between him/her with other users is
called an edge. There is no limitation for building the relationship between any two vertexes of
the graph like a tree. We can implement the graph data structure using the array or LinkedList.
Types of the graph:
 Simple Graph
 Un-directed Graph
 Directed Graph
 Weighted Graph
c. Hashmap
Hashmaps store data as key-value pairs. It can be either linear or non-linear data structure. We
can use the hashmap to map the value with its keys and search value efficiently from it.
The above-explained data structures are fundamental data structures.
Difference between linear data structure and non-linear data structure
Here, we have explained the key difference between linear and non-linear data structure in the
table format.
Linear data structure Non-linear data structure
The linear relationship is present between Data elements have a hierarchical

data elements. relationship.
Every element makes a connection to only Every element makes a connection to more
its previous and next elements. than two elements.
We can traverse it in a single run as it is We can't traverse it in a single run as it is a

linear. non-linear structure.
It is a single-level data structure. It is a multi-level data structure.
The utilization of memory is not efficient. Memory utilization is efficient.
Time complexity increases if we need to Time complexity doesn't change much if we

traverse through a large dataset. need to traverse through the large input size.
All Social networks, telephone networks,

It is used to build an operating system and
Artificial intelligence, and image processing
compiler design.
are using non-linear data structures.
Example: Graph, map, tree, heap data

Examples: Array, stack, queue, LinkedList
structure
It is complex to implement. However, we can
implement it easily, as nonlinear data
It is easy to implement.
structures include a powerful algorithm to
implement them.
The main use of the data structure is to build efficient algorithms such as sorting algorithms.
Stack, queue, array, etc., have a linear relationship between the data elements, while graph, tree,
hashmap, etc., have a complex relationship with the data.
1.8 Introduction to Hierarchical Data Structure

In this article following Data Structures are discussed.
a. Binary Tree
b. Binary Search Tree
c. Binary Heap
d. Hashing
a. Binary Tree
Unlike Arrays, Linked Lists, Stack, and queues, which are linear data structures, trees are
hierarchical data structures.
A binary tree is a tree data structure in which each node has at most two children, which are
referred to as the left child and the right child. It is implemented mainly using Links.
Binary Tree Representation: A tree is represented by a pointer to the topmost node in the tree.
If the tree is empty, then the value of the root is NULL. A Binary Tree node contains the
following parts.
1. Data
2. Pointer to left child
3. Pointer to the right child
A Binary Tree can be traversed in two ways:
Depth First Traversal: Inorder (Left-Root-Right), Preorder (Root-Left-Right), and Postorder
(Left-Right-Root)
Breadth-First Traversal: Level Order Traversal
Binary Tree Properties:

The maximum number of nodes at level ‘l’ = 2l.
Maximum number of nodes = 2h + 1 – 1.
Here h is height of a tree. Height is considered as the maximum number of edges on a path from
root to leaf.
Minimum possible height = ceil(Log2(n+1)) - 1
In Binary tree, number of leaf nodes is always one more than nodes with two children.
Time Complexity of Tree Traversal: O(n)
Basic Operation On Binary Tree:

 Inserting an element.
 Removing an element.
 Searching for an element.
 Traversing an element.
Auxiliary Operation On Binary Tree:
 Finding the height of the tree.
 Find the level of the tree.
 Finding the size of the entire tree.
Applications of Binary Tree:

 Huffman coding trees are used in data compression algorithms.
 Priority Queue is another application of binary tree that is used for searching maximum or
minimum in O(logn) time complexity.
 In compilers, Expression Trees are used which is an application of binary tree.
Binary Tree Traversals:

 Preorder Traversal: Here, the traversal is : root – left child – right child. It means that the
root node is traversed first then its left child and finally the right child.
 Inorder Traversal: Here, the traversal is : left child – root – right child. It means that the left
child is traversed first then its root node and finally the right child.
 Postorder Traversal: Here, the traversal is : left child – right child – root. It means that the
left child is traversed first then the right child and finally its root node.
Examples: One reason to use binary trees or trees, in general, is for the things that form a
hierarchy. They are useful in File structures where each file is located in a particular directory
and there is a specific hierarchy associated with files and directories. Another example where
Trees are useful is storing hierarchical objects like JavaScript Document Object Model considers
HTML page as a tree with nesting of tags as parent-child relations.
b. Binary Search Tree

Binary Search Tree (BST) is a tree whose main function is to search a specific element.
Binary Search Tree is a Binary Tree with the following additional properties:
1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.
Binary Search Tree Declaration

struct BinarySearchTree{
int data;
struct BinarySearchTree* left;
struct BinarySearchTree* right;
};
Since it is a Binary Tree, its declaration is similar to the Binary Tree.
Primary BST Operations:

 Finding minimum or maximum element.
 Deleting a particular element from the tree.
 Inserting a particular element in the tree.
Auxiliary BST Operations:

 Finding kth smallest element.
 To identify whether the given binary tree is a BST or not.
Time Complexities:
Search : O(h)
Insertion : O(h)
Deletion : O(h)
Extra Space : O(n) for pointers
h: Height of BST
n: Number of nodes in BST
If Binary Search Tree is Height Balanced,
then h = O(Log n)
Self-Balancing BSTs such as AVL Tree, Red-Black
Tree and Splay Tree make sure that height of BST
remains O(Log n)
BST provides moderate access/search (quicker than Linked List and slower than arrays).
BST provides moderate insertion/deletion (quicker than Arrays and slower than Linked Lists).
Examples: Its main use is in search applications where data is constantly entering/leaving and
data needs to be printed in sorted order. For example in implementation in E-commerce websites
where a new product is added or product goes out of stock and all products are listed in sorted
order.
c. Binary Heap
A Binary Heap is a Binary Tree with the following properties.
1) It’s a complete tree (All levels are completely filled except possibly the last level and the last
level has all keys as left as possible). This property of Binary Heap makes them suitable to be
stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root
must be minimum among all keys present in Binary Heap. The same property must be
recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap. It is
mainly implemented using an array.
Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n) [Or Decrease Key in Max Heap]
Insert: O(Log n)
Delete: O(Log n)
Here is the algorithm to implement a binary heap:

1. Create a binary heap class that has a private array for storing the elements of the heap and
a private method for maintaining the heap property.
2. The class should have a constructor method for initializing the heap and a method for
adding a new element to the heap. The add method should start by inserting the new element at
the end of the array and then compare it with its parent node. If the value of the new element is
larger (for a max-heap) or smaller (for a min-heap) than the value of its parent, then the two
elements should be swapped. This process should be repeated until the heap property is
satisfied.
3. The class should also have a method for removing the root element from the heap. The
remove method should start by replacing the root element with the last element in the array
and then compare it with its children. If the value of the root element is smaller (for a max-
heap) or larger (for a min-heap) than the value of one of its children, then the two elements
should be swapped. This process should be repeated until the heap property is satisfied.
4. The class should also have a method for checking if the heap is empty.
5. To implement the binary heap efficiently, it is recommended to use an array-based
implementation where the parent, left child, and right child of a node at index i are stored at
indices (i-1)/2, 2i+1, and 2i+2 respectively.
Example: Used in implementing efficient priority queues, which in turn are used for scheduling
processes in operating systems. Priority Queues are also used in Dijkstra’s and Prim’s graph
algorithms.
The Heap data structure can be used to efficiently find the k smallest (or largest) elements in an
array, merging k sorted arrays, a median of a stream, etc.
Heap is a special data structure and it cannot be used for searching a particular element.
d. Hashing: Hashing is a popular technique for storing and retrieving data as fast as
possible. The main reason behind using hashing is that it gives optimal results as it performs
optimal searches.
Why the Need for Hashing:

If you observe carefully, in a balanced binary search tree, if we try to search , insert or delete any
element then the time complexity for the same is O(logn). Now there might be a situation when
our applications want to do the same operations in a faster way i.e. in a more optimized way and
here hashing comes into play. In hashing, all the above operations can be performed in O(1) i.e.
constant time. It is important to understand that the worst case time complexity for hashing
remains O(n) but the average case time complexity is O(1).
A hash function is a function that takes an input (or “message”) and returns a fixed-size string of
characters, which is typically a “digest” that is unique to the unique values of the input.
A good hash function should have the following properties:

 Deterministic: The same input will always produce the same hash value.
 Efficiently computable: The hash function should be easy to compute, even for large inputs.
 Uniform distribution: The hash values should be distributed uniformly across the range of
possible values.
Here is an example algorithm for implementing a simple hash function:
 C++
 Java
 Python
 C#
 Javascript
#include <iostream>
#include <string>
class HashFunction {
public:
static int hash_function(std::string input_string)
{
// initialize a variable to store the hash value

int hash_value = 0;
// loop over each character in the input string

for (int i = 0; i < input_string.length(); i++) {
// add the ASCII value of the character to the hash
value
hash_value += static_cast<int>(input_string[i]);
}
// return the hash value modulo some large prime

number
return hash_value % 101;
}
};
int main()
{
// Given input string
std::string input_string = "Hello, World!";
// Function call
int hash_value =
HashFunction::hash_function(input_string);
// Print the hash value

std::cout << hash_value << std::endl;
return 0;
}
Output
18
Irreversible: It should be difficult to generate the original input given only the hash value.
Hash Function: A function that converts a given big phone number to a small practical integer
value. The mapped integer value is used as an index in hash table. So, in simple terms we can say
that a hash function is used to transform a given key into a specific slot index. Its main job is to
map each and every possible key into a unique slot index. If every key is mapped into a unique
slot index, then the hash function is known as a perfect hash function. It is very difficult to create
a perfect hash function but our job as a programmer is to create such a hash function with the
help of which the number of collisions are as few as possible. Collision is discussed ahead.
A good hash function should have following properties:

1) Efficiently computable.
2) Should uniformly distribute the keys (Each table position equally likely for each key) .
3)Should minimize collisions
4)Should have a high load factor(number of items in table divided by size of the table).
For example for phone numbers a bad hash function is to take first three digits. A better function
is consider last three digits. Please note that this may not be the best hash function. There may be
better ways.
Hash Table: An array that stores pointers to records corresponding to a given phone number. An
entry in hash table is NIL if no existing phone number has hash function value equal to the index
for the entry. In simple terms, we can say that hash table is a generalization of array. Hash table
gives the functionality in which a collection of data is stored in such a way that it is easy to find
those items later if required. This makes searching of an element very efficient.
Collision Handling: Since a hash function gets us a small number for a key which is a big
integer or string, there is the possibility that two keys result in the same value. The situation
where a newly inserted key maps to an already occupied slot in the hash table is called collision
and must be handled using some collision handling technique. Following are the ways to handle
collisions:
Chaining: The idea is to make each cell of the hash table point to a linked list of records that
have the same hash function value. Chaining is simple but requires additional memory outside
the table.
Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table
entry contains either a record or NIL. When searching for an element, we one by one examine
table slots until the desired element is found or it is clear that the element is not in the table.
Space : O(n)
Search : O(1) [Average] O(n) [Worst case]
Insertion : O(1) [Average] O(n) [Worst Case]
Deletion : O(1) [Average] O(n) [Worst Case]
Hashing seems better than BST for all the operations. But in hashing, elements are unordered
and in BST elements are stored in an ordered manner. Also, BST is easy to implement but hash
functions can sometimes be very complex to generate. In BST, we can also efficiently find floor
and ceil of values.
Example: Hashing can be used to remove duplicates from a set of elements. Can also be used to
find the frequency of all items. For example, in web browsers, we can check visited URLs using
hashing. In firewalls, we can use hashing to detect spam. We need to hash IP addresses. Hashing
can be used in any situation where want search() insert() and delete() in O(1) time.
1.9 Overview of Graph, Trie, Segment Tree and Suffix Tree Data
Structures
Introduction:
a. Graph: A graph is a collection of vertices (nodes) and edges that represent relationships
between the vertices. Graphs are used to model and analyze networks, such as social
networks or transportation networks.
b. Trie: A trie, also known as a prefix tree, is a tree-like data structure that stores a
collection of strings. It is used for efficient searching and retrieval of strings, especially in
the case of a large number of strings.
c. Segment Tree: A segment tree is a tree-like data structure that stores information about
ranges of values. It is used for range queries and range updates, such as finding the sum
of an array or finding the minimum or maximum value in an array.
d. Suffix Tree: A suffix tree is a tree-like data structure that stores all suffixes of a given
string. It is used for efficient string search and pattern matching, such as finding the
longest repeated substring or the longest common substring.
a. Graph: Graph is a data structure that consists of the following two components:
1. A finite set of vertices is also called nodes.
2. A finite set of ordered pairs of the form (u, v) is called an edge. The pair is ordered because (u,
v) is not the same as (v, u) in the case of a directed graph(di-graph). The pair of forms (u, v)
indicates that there is an edge from vertex u to vertex v. The edges may contain
weight/value/cost.
V -> Number of Vertices. E -> Number of Edges. The graph can be classified on the basis of
many things, below are the two most common classifications :
1. Direction: Undirected Graph: The graph in which all the edges are bidirectional.Directed
Graph: The graph in which all the edges are unidirectional.
2. Weight: Weighted Graph: The Graph in which weight is associated with the
edges.Unweighted Graph: The Graph in which there is no weight associated with the edges.
Algorithm to implement graph –
The general algorithmic steps to implement a graph data structure:
 Create a class for the graph: Start by creating a class that represents the graph data structure.
This class should contain variables or data structures to store information about the vertices
and edges in the graph.
 Represent vertices: Choose a data structure to represent the vertices in the graph. For
example, you could use an array, linked list, or dictionary.
 Represent edges: Choose a data structure to represent the edges in the graph. For example,
you could use an adjacency matrix or an adjacency list.
 Add vertices: Implement a method to add vertices to the graph. You should store information
about the vertex, such as its name or identifier.
 Add edges: Implement a method to add edges between vertices in the graph. You should store
information about the edge, such as its weight or direction.
 Search for vertices: Implement a method to search for a specific vertex in the graph.
 Search for edges: Implement a method to search for a specific edge in the graph.
 Remove vertices: Implement a method to remove vertices from the graph.
 Remove edges: Implement a method to remove edges from the graph.
 Traverse the graph: Implement a method to traverse the graph and visit each vertex. You
could use algorithms like depth-first search or breadth-first search.
This algorithm provides a basic structure for implementing a graph data structure in any
programming language. You can adjust the implementation to meet the specific needs of your
application.
Graphs can be represented in many ways, below are the two most common representations: Let
us take the below example graph to see two representations of the graph.
Adjacency Matrix Representation of the above graph

Adjacency List Representation of the above Graph
Time Complexities in case of Adjacency Matrix :

Traversal :(By BFS or DFS) O(V^2)
Space : O(V^2)
Time Complexities in case of Adjacency List :

Traversal :(By BFS or DFS) O(V + E)
Space : O(V+E)
Examples: The most common example of the graph is to find the shortest path in any network.
Used in google maps or bing. Another common use application of graphs is social networking
websites where the friend suggestion depends on the number of intermediate suggestions and
other things.
b. Trie
Trie is an efficient data structure for searching words in dictionaries, search complexity with Trie
is linear in terms of word (or key) length to be searched. If we store keys in a binary search tree,
a well-balanced BST will need time proportional to M * log N, where M is the maximum string
length and N is the number of keys in the tree. Using trie, we can search the key in O(M) time.
So it is much faster than BST. Hashing also provides word search in O(n) time on average. But
the advantages of Trie are there are no collisions (like hashing) so the worst-case time
complexity is O(n). Also, the most important thing is Prefix Search. With Trie, we can find all
words beginning with a prefix (This is not possible with Hashing). The only problem with Tries
is they require a lot of extra space. Tries are also known as radix trees or prefix trees.
The Trie structure can be defined as follows :
struct trie_node
{
int value; /* Used to mark leaf nodes */
trie_node_t *children[ALPHABET_SIZE];
};
root
/ \ \
t a b
| | |
h n y
| | \ |
e s y e
/ | |
i r w
| | |
r e e
|
r
The leaf nodes are in blue.
Insert time : O(M) where M is the length of the string.

Search time : O(M) where M is the length of the string.
Space : O(ALPHABET_SIZE * M * N) where N is number of
keys in trie, ALPHABET_SIZE is 26 if we are
only considering upper case Latin characters.
Deletion time: O(M)
Algorithm to implement tree –
Here is a general algorithmic step to implement a tree data structure:
 Create a class for the tree: Start by creating a class that represents the tree data structure.
This class should contain variables or data structures to store information about the nodes in
the tree.
 Represent nodes: Choose a data structure to represent the nodes in the tree. For example, you
could use an array, linked list, or dictionary.
 Add nodes: Implement a method to add nodes to the tree. You should store information about
the node, such as its value or identifier.
 Add relationships: Implement a method to add relationships between nodes in the tree. For
example, you could define a parent-child relationship between nodes.
 Search for nodes: Implement a method to search for a specific node in the tree.
 Remove nodes: Implement a method to remove nodes from the tree.
 Traverse the tree: Implement a method to traverse the tree and visit each node. You could use
algorithms like in-order, pre-order, or post-order traversal.
This algorithm provides a basic structure for implementing a tree data structure in any
programming language. You can adjust the implementation to meet the specific needs of your
application.
Example: The most common use of Tries is to implement dictionaries due to prefix search
capability. Tries are also well suited for implementing approximate matching algorithms,
including those used in spell checking. It is also used for searching Contact from Mobile Contact
list OR Phone Directory.
c. Segment Tree
This data structure is usually implemented when there are a lot of queries on a set of values.
These queries involve minimum, maximum, sum, .. etc on an input range of a given set. Queries
also involve updating values in the given set. Segment Trees are implemented using an array.
Construction of segment tree : O(N)

Query : O(log N)
Update : O(log N)
Space : O(N) [Exact space = 2*N-1]
Example: It is used when we need to find the Maximum/Minimum/Sum/Product of numbers in a
range.
d. Suffix Tree
The suffix tree is mainly used to search for a pattern in a text. The idea is to preprocess the text
so that the search operation can be done in time linear in terms of pattern length. The pattern
searching algorithms like KMP, Z, etc take time proportional to text length. This is really a great
improvement because the length of the pattern is generally much smaller than the text. Imagine
we have stored the complete work of William Shakespeare and preprocessed it. You can search
any string in the complete work in time just proportional to the length of the pattern. But using
Suffix Tree may not be a good idea when text changes frequently like text editor, etc. A suffix
tree is a compressed trie of all suffixes, so the following are very abstract steps to build a suffix
tree from given text. 1) Generate all suffixes of the given text. 2) Consider all suffixes as
individual words and build a compressed trie.
Example: Used to find all occurrences of the pattern in a string. It is also used to find the longest
repeated substring (when the text doesn’t change often), the longest common substring and the
longest palindrome in a string.
Graphs:
Advantages:
 Represent complex relationships: Graphs can be used to represent complex

relationships between objects, making it a suitable data structure for many real-world
scenarios.
 Efficient searching: Graphs can be searched efficiently using algorithms like depth-first
search and breadth-first search.
 Flexibility: Graphs can be easily modified by adding or removing vertices and edges,
making them a flexible data structure.
 Supports weighted edges: Graphs can support weighted edges, which is useful when
representing relationships with different levels of importance or cost.
 Can represent directed and undirected relationships: Graphs can represent both
directed and undirected relationships, making it a versatile data structure.
 Model real-world relationships and connections
 Allow for efficient searching and navigation through the network
 Can handle large and complex datasets
Disadvantages:
 Space complexity: Storing the information about vertices and edges in a graph can be
memory-intensive.
 More complex algorithms: The algorithms used to traverse a graph and search for
specific vertices or edges can be more complex than other data structures like arrays or
linked lists.
 Slower operations: Operations like adding or removing vertices or edges can be slower
than with other data structures.
 Difficult to implement: Implementing a graph data structure can be more difficult than
other data structures, requiring a good understanding of graph theory and algorithms.
 May not be suitable for some use cases: For certain use cases, a graph data structure
may not be the best option and another data structure like an array or linked list may be
more suitable.
 May require significant computational resources
 Finding the optimal path between nodes can be a challenging problem
Tries:
Advantages:
 Fast search and retrieval of strings

 Space-efficient storage of strings
 Can be used for text processing tasks such as spell-checking
Disadvantages:
 Can have a high memory overhead for large datasets

 Insertions and deletions can be slow and complex
Segment Trees:
Advantages:
 Efficient range queries and updates

 Can be used for a variety of range-based problems
Disadvantages:
 Can require significant memory overhead

 The creation of the tree can be a time-consuming process
Suffix Trees:
Advantages:
 Fast string search and pattern matching

 Can be used for a variety of string-based problems
Disadvantages:
 Can have a high memory overhead

 The creation of the tree can be a time-consuming process
 Not suitable for all string-based problems, such as regular expression matching.
1.10 Abstract Data Types -Most Popular Data Structures:
Below are some most popular Data Structure:
1. Array:
Array is a linear data structure that stores a collection of elements of the same data type. Elements
are allocated contiguous memory, allowing for constant-time access. Each element has a unique
index number.
Search, Insert, and Delete in an Unsorted Array | Array Operations

In this post, a program to search, insert, and delete operations in an unsorted array is discussed.
Search Operation:
In an unsorted array, the search operation can be performed by linear traversal from the first
element to the last element.
Coding implementation of the search operation:
 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
// C++ program to implement linear

// search in unsorted array
#include <bits/stdc++.h>
using namespace std;
// Function to implement search operation

int findElement(int arr[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
// If the key is not found

return -1;
}
// Driver's Code
int main()
{
int arr[] = { 12, 34, 10, 6, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
// Using a last element as search element

int key = 40;
// Function call
int position = findElement(arr, n, key);
if (position == -1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;
return 0;
}
// This code is contributed

// by Akanksha Rai
Output
Element Found at Position: 5
Time Complexity: O(N)

Auxiliary Space: O(1)
Insert Operation:
1. Insert at the end:

In an unsorted array, the insert operation is faster as compared to a sorted array because we don’t
have to care about the position at which the element is to be placed.
Coding implementation of inserting an element at the end:
 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
#include <iostream>
// Inserts a key in arr[] of given capacity.

// n is the current size of arr[]. This
// function returns n + 1 if insertion
// is successful, else n.
int insertSorted(int arr[], int n, int key, int capacity)
{
// Cannot insert more elements if n is
// already more than or equal to capacity
if (n >= capacity)
return n;
arr[n] = key;
return (n + 1);
}
int main()
{
int arr[20] = { 12, 16, 20, 40, 50, 70 };
int capacity = sizeof(arr) / sizeof(arr[0]);
int n = 6;
int i, key = 26;
cout << "Before Insertion: ";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
// Inserting key
n = insertSorted(arr, n, key, capacity);
cout << "\nAfter Insertion: ";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output
Before Insertion: 12 16 20 40 50 70
After Insertion: 12 16 20 40 50 70 26
Time Complexity: O(1)

2. Insert at any position
Insert operation in an array at any position can be performed by shifting elements to the right,
which are on the right side of the required position
Coding implementation of inserting an element at any position:

 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
// C++ Program to Insert an element
// at a specific position in an Array
// Function to insert element

// at a specific position
void insertElement(int arr[], int n, int x, int pos)
{
// shift elements to the right
// which are on the right side of pos
for (int i = n - 1; i >= pos; i--)
arr[i + 1] = arr[i];
arr[pos] = x;
}
// Driver's code
int main()
{
int arr[15] = { 2, 4, 1, 8, 5 };
int n = 5;
cout<<"Before insertion : ";

for (int i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<endl;
int x = 10, pos = 2;
// Function call
insertElement(arr, n, x, pos);
n++;
cout<<"After insertion : ";

for (int i = 0; i < n; i++)
cout<<arr[i]<<" ";
return 0;
}
Output
Before insertion : 2 4 1 8 5
After insertion : 2 4 10 1 8 5
Time complexity: O(N)

Delete Operation:
In the delete operation, the element to be deleted is searched using the linear search, and then the
delete operation is performed followed by shifting the elements.
 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
// C++ program to implement delete operation in a

// unsorted array
#include <iostream>
// To search a key to be deleted

int findElement(int arr[], int n, int key);
// Function to delete an element

int deleteElement(int arr[], int n, int key)
{
// Find position of element to be deleted
int pos = findElement(arr, n, key);
if (pos == -1) {
return n;
}
// Deleting element
int i;
for (i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
return n - 1;
}
// Function to implement search operation

int findElement(int arr[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
// Driver's code
int main()
{
int i;
int arr[] = { 10, 50, 30, 40, 20 };

int key = 30;
cout << "Array before deletion\n";
for (i = 0; i < n; i++)
cout << arr[i] << " ";
// Function call
n = deleteElement(arr, n, key);
cout << "\n\nArray after deletion\n";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// This code is contributed by shubhamsingh10

Output
Array before deletion
10 50 30 40 20
Array after deletion

10 50 40 20

Search, Insert, and Delete in an Sorted Array | Array Operations
How to Search in a Sorted Array?

In a sorted array, the search operation can be performed by using binary search.
Below is the implementation of the above approach:
 C++
 C
 Java
 Python3
 C#
 PHP
 Javascript
// C++ program to implement binary search in sorted
array
int binarySearch(int arr[], int low, int high, int key)

{
if (high < low)
return -1;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
/* Driver code */
int main()
{
// Let us search 3 in below array
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = sizeof(arr) / sizeof(arr[0]);
key = 10;
// Function call
cout << "Index: " << binarySearch(arr, 0, n - 1, key)
<< endl;
return 0;
}
// This code is contributed by NamrataSrivastava1

Output
Index: 5
Time Complexity: O(log(n)) Using Binary Search
Auxiliary Space: O(log(n)) due to recursive calls, otherwise iterative version uses Auxiliary
Space of O(1).
How to Insert in a Sorted Array?
In a sorted array, a search operation is performed for the possible position of the given element
by using Binary search, and then an insert operation is performed followed by shifting the
elements. And in an unsorted array, the insert operation is faster as compared to the sorted array
because we don’t have to care about the position at which the element is placed.
 C++
 C
 Java
 Python3
 C#
 Javascript
// C++ program to implement insert operation in
// an sorted array.
// Inserts a key in arr[] of given capacity. n is current

// size of arr[]. This function returns n+1 if insertion
// is successful, else n.
int insertSorted(int arr[], int n, int key, int capacity)
{
// Cannot insert more elements if n is already
// more than or equal to capacity
if (n >= capacity)
return n;
int i;
for (i = n - 1; (i >= 0 && arr[i] > key); i--)
arr[i + 1] = arr[i];
arr[i + 1] = key;
return (n + 1);
}
/* Driver code */
int main()
{
int arr[20] = { 12, 16, 20, 40, 50, 70 };
int capacity = sizeof(arr) / sizeof(arr[0]);
int n = 6;
int i, key = 26;
cout << "\nBefore Insertion: ";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
// Function call
n = insertSorted(arr, n, key, capacity);
cout << "\nAfter Insertion: ";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// This code is contributed by SHUBHAMSINGH10

Output
Before Insertion: 12 16 20 40 50 70
After Insertion: 12 16 20 26 40 50 70
Time Complexity: O(N) [In the worst case all elements may have to be moved]
How to Delete in a Sorted Array?
In the delete operation, the element to be deleted is searched using binary search, and then the
delete operation is performed followed by shifting the elements.
Performing delete operation
 C++
 C
 Java
 Python3
 C#
 Javascript
// C++ program to implement delete operation in a
// sorted array
// To search a key to be deleted

int binarySearch(int arr[], int low, int high, int key);
/* Function to delete an element */

int deleteElement(int arr[], int n, int key)
{
// Find position of element to be deleted
int pos = binarySearch(arr, 0, n - 1, key);
if (pos == -1) {
return n;
}
// Deleting element
int i;
for (i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
return n - 1;
}
int binarySearch(int arr[], int low, int high, int key)

{
if (high < low)
return -1;
int mid = (low + high) / 2;
return mid;
if (key > arr[mid])
}
// Driver code
int main()
{
int i;
int arr[] = { 10, 20, 30, 40, 50 };

int key = 30;
cout << "Array before deletion\n";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
// Function call
n = deleteElement(arr, n, key);
cout << "\n\nArray after deletion\n";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
}
// This code is contributed by shubhamsingh10

Output
Array before deletion

10 20 30 40 50
Array after deletion

10 20 40 50
Time Complexity: O(N). In the worst case all elements may have to be moved
Auxiliary Space: O(log N). An implicit stack will be used
 Write a program to reverse an array

Array Reverse in C/C++/Java/Python/JavaScript
Last Updated : 17 Apr, 2024
Array reverse or reverse a array means changing the position of each number of the given
array to its opposite position from end, i.e. if a number is at position 1 then its new position will
be Array.length, similarly if a number is at position 2 then its new position will be Array.length –
1, and so on.
Array Reverse in C/C++/Java/Python/JavaScript
Given an array (or string), the task is to reverse the array/string.

Examples:
Input: original_array[] = {1, 2, 3} Output: array_reversed[] = {3, 2, 1}
Input: original_array[] = {4, 5, 1, 2}
Output: array_reversed[] = {2, 1, 5, 4}
Table of Content
 1. Array Reverse Using an Extra Array (Non In-place):
 2. Array Reverse Using a Loop (In-place):
 3. Array Reverse Inbuilt Methods (Non In-place):
 4. Array Reverse Recursion (In-place or Non In-place):
 5. Array Reverse Stack (Non In-place):
1. Array Reverse Using an Extra Array (Non In-place):
 Create a new array of the same size as the original array.
 Copy elements from the original array to the new array in reverse order.
C++CJavaPython3C#JavaScript
#include <iostream>;
void reverseArrayExtraArray(int arr[], int size)

{
int reversedArr[size];
for (int i = 0; i < size; i++) {
reversedArr[i] = arr[size - i - 1];
}
// Print reversed array

cout << "Reversed Array: ";
std::cout << reversedArr[i] << " ";
}
}
int main()
{
int originalArr[] = { 1, 2, 3, 4, 5 };
int size = sizeof(originalArr) / sizeof(originalArr[0]);
reverseArrayExtraArray(originalArr, size);
}
Output
Reversed Array: 5 4 3 2 1
 Time Complexity: O(n)
 Copying elements to a new array is a linear operation.
 Auxiliary Space Complexity: O(n)
 Additional space is used to store the new array.
2. Array Reverse Using a Loop (In-place):
 Iterate through the array using two pointers (start and end).
 Swap elements at the start and end pointers.
 Move the start pointer towards the end and the end pointer towards the start until they meet or
cross each other.
Below is the implementation of the above approach :
C++CJavaPython3C#JavaScriptPHP
// Iterative C++ program to reverse an array
#include <bits/stdc++.h>;
/* Function to reverse arr[] from start to end*/

void reverseArray(int arr[], int start, int end)
{
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
/* Utility function to print an array */

void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;

}
/* Driver function to test above functions */

int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
// To print original array

printArray(arr, n);
// Function calling
reverseArray(arr, 0, n - 1);
cout << "Reversed array is" << endl;
// To print the Reversed array

printArray(arr, n);
return 0;
}
Output
1 2 3 4 5 6
Reversed array is
6 5 4 3 2 1

 The loop runs through half of the array, so it’s linear with respect to the array size.
 Auxiliary Space Complexity: O(1)
 In-place reversal, meaning it doesn’t use additional space.
3. Array Reverse Inbuilt Methods (Non In-place):
 Use inbuilt methods like reverse in Python or Array.Reverse in C#.
C++JavaPython3C#JavaScript
#include <algorithm> // for std::reverse

#include <iostream>
int main()
{
int originalArray[] = { 1, 2, 3, 4, 5 };
int length
= sizeof(originalArray) / sizeof(originalArray[0]);
// Using inbuilt method in C++

std::reverse(originalArray, originalArray + length);
// Print the reversed array

for (int i = 0; i < length; i++) {
std::cout << originalArray[i] << " ";
}
return 0;
}
Output
5 4 3 2 1
 Time Complexity: O(n) The reverse method typically has linear time complexity.
Additional space is used to store the reversed array.

4. Array Reverse Recursion (In-place or Non In-place):
 Define a recursive function that takes an array as input.
 Swap the first and last elements.
 Recursively call the function with the remaining subarray.
// Recursive C++ program to reverse an array

#include <bits/stdc++.h>;
/* Function to reverse arr[] from start to end*/

void reverseArray(int arr[], int start, int end)
{
if (start >= end)
return;
int temp = arr[start];

arr[start] = arr[end];
arr[end] = temp;
// Recursive Function calling

reverseArray(arr, start + 1, end - 1);
}
/* Utility function to print an array */

{
cout << arr[i] << " ";
cout << endl;

}
/* Driver function to test above functions */

int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
// To print original array

printArray(arr, 6);
// Function calling
reverseArray(arr, 0, 5);
cout << "Reversed array is" << endl;
// To print the Reversed array

printArray(arr, 6);
return 0;
}
Output
1 2 3 4 5 6
Reversed array is
6 5 4 3 2 1
 Time Complexity: O(n). The recursion goes through each element once, so it’s linear.
 Auxiliary Space Complexity: O(n) for non in-place, O(log n) for in-place (due to recursion
stack).
5. Array Reverse Stack (Non In-place):
 Push each element of the array onto a stack.
 Pop elements from the stack to form the reversed array.
#include <iostream>;
#include <stack>;
#include <vector>;
void reverseArrayUsingStack(int arr[], int size)

{
std::stack<int> stack;
// Push elements onto the stack

stack.push(arr[i]);
}
// Pop elements from the stack to reverse the array

arr[i] = stack.top();
stack.pop();
}
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
reverseArrayUsingStack(arr, size);
std::cout << "Reversed Array: ";

std::cout << arr[i] << " ";
}
return 0;
}
Output
Reversed Array: 5 4 3 2 1
 Pushing and popping each element onto/from the stack requires linear time.
 Additional space is used to store the stack.
Leaders in an array


Write a program to print all the LEADERS in the array. An element is a leader if it is greater
than all the elements to its right side. And the rightmost element is always a leader.
For example:
Input: arr[] = {16, 17, 4, 3, 5, 2},
Output: 17, 5, 2
Input: arr[] = {1, 2, 3, 4, 5, 2},
Output: 5, 2
Recommended Problem
Naive Approach: The problem can be solved based on the idea mentioned below:
Use two loops. The outer loop runs from 0 to size – 1 and one by one pick all elements from left
to right. The inner loop compares the picked element to all the elements on its right side. If the
picked element is greater than all the elements to its right side, then the picked element is the
leader.
Follow the below steps to implement the idea:
 We run a loop from the first index to the 2nd last index.
 And for each index, we run another loop from the next index to the last index.
 If all the values to the right of that index are smaller than the index, we simply add
the value in our answer data structure.
Below is the implementation of the above approach.
 C
 C++
 Java
 Python3
 C#
 PHP
 Javascript
/*C Function to print leaders in an array */
#include <stdio.h>
void printLeaders(int arr[], int size)

{
int i, j;
for (i = 0; i < size; i++) {
for (j = i + 1; j < size; j++) {
if (arr[i] <= arr[j])
break;
}
if (j == size) // the loop didn't break
printf("%d ", arr[i]);
}
}
/* Driver program to test above function */

int main()
{
int arr[] = { 16, 17, 4, 3, 5, 2 };
printLeaders(arr, n);
return 0;
}
Output
17 5 2
Time Complexity: O(N * N)
Find Leader by finding suffix maximum:
The idea is to scan all the elements from right to left in an array and keep track of the maximum
till now. When the maximum changes its value, print it.
Follow the below illustration for a better understanding
Illustration:
Let the array be arr[] = {16, 17, 4, 3, 5, 2}
 arr[] = {16, 17, 4, 3, 5, 2} , max_from_right = 2 , ans[] = { 2 }
 arr[] = {16, 17, 4, 3, 5, 2} , max_from_right = 5 , ans[] = { 2, 5 }
 arr[] = {16, 17, 4, 3, 5, 2} , max_from_right = 17 , ans[] = { 2, 5, 17 }
Follow the steps mentioned below to implement the idea:
 We start from the last index position. The last position is always a leader, as there are no
elements towards its right.
 And then we iterate on the array till we reach index position = 0.
 Each time we keep a check on the maximum value
 Every time we encounter a maximum value than the previous maximum value
encountered, we either print or store the value as it is the leader
 C
 C++
 Java
 Python3
 C#
 PHP
 Javascript
#include <stdio.h>
/* C Function to print leaders in an array */

{
int max_from_right = arr[size - 1];
/* Rightmost element is always leader */

printf("%d ", max_from_right);
for (int i = size - 2; i >= 0; i--) {

if (max_from_right < arr[i]) {
max_from_right = arr[i];
printf("%d ", max_from_right);
}
}
}
/* Driver program to test above function*/
int main()
{
int arr[] = { 16, 17, 4, 3, 5, 2 };
return 0;
}
Output
2 5 17
Time Complexity: O(n)
Find leaders and print them in the same order as they are:
In the previous method, we get time linear complexity, but the output we get is not in the same
order as the elements that appear in our input array, so to get out output in the same order as in
the input array, we can use stack data structure.
Illustration:
Let the array be arr[] = {16, 17, 4, 3, 5, 2}, we will store the ans in a stack to print in the same
order.
 arr[] = {16, 17, 4, 3, 5, 2} , max_from_right = 2 , ans[] = { 2 }
 We start from the last index position. The last position is always a leader, as there are no
elements towards its right.
 And then we iterate on the array till we reach index position = 0.
 Each time we keep a check on the maximum value
 Every time we encounter a maximum value than the previous maximum value
encountered, we will store the value in the stack as it is the leader
 We will iterate on the stack and print the values
 C
 C++
 Java
 Python3
 C#
 Javascript
#include <stdio.h>
#include <stdlib.h>
/* C Function to print leaders in an array */

{
/* create stack to store leaders*/
int* sk = (int*)malloc(size * sizeof(int));
int top = -1;
sk[++top] = arr[size - 1];
for (int i = size - 2; i >= 0; i--) {
if (arr[i] >= sk[top]) {
sk[++top] = arr[i];
}
}
/* print stack elements*/

/* run loop till stack is not empty*/
while (top != -1) {
printf("%d ", sk[top--]);
}
free(sk);
}
/* Driver program to test above function*/

int main()
{
int arr[] = { 16, 17, 4, 3, 5, 2 };
return 0;
}
Output
17 5 2
Time complexity: O(n)
Auxiliary space: O(n)
 Given an array A[] and a number x, check for pair in A[] with sum as x
Check if pair with given Sum exists in Array (Two Sum)
Given an array A[] of n numbers and another number x, the task is to check whether or not there
exist two elements in A[] whose sum is exactly x.
Examples:
Input: arr[] = {0, -1, 2, -3, 1}, x= -2
Output: Yes
Explanation: If we calculate the sum of the output,1 + (-3) = -2
Input: arr[] = {1, -2, 1, 0, 5}, x = 0
Output: No
Recommended Problem
Two Sum using Naive Approach:

The basic approach to solve this problem is by nested traversal.
 Traverse the array using a loop
 For each element:
 Check if there exists another in the array with sum as x
 Return true if yes, else continue
 If no such pair is found, return false.
// C++ program for the above approach


// Function to find and print pair
bool chkPair(int A[], int size, int x)
{
for (int i = 0; i < (size - 1); i++) {
for (int j = (i + 1); j < size; j++) {
if (A[i] + A[j] == x) {
return 1;
}
}
}
return 0;
}
// Driver code
int main()
{
int A[] = { 0, -1, 2, -3, 1 };
int x = -2;
int size = sizeof(A) / sizeof(A[0]);
if (chkPair(A, size, x)) {

cout << "Yes" << endl;
}
else {
cout << "No" << x << endl;
}
return 0;
}
// This code is contributed by Samim Hossain Mondal.

Output
Yes
Time Complexity: O(N2), Finding pair for every element in the array of size N.
Two Sum using Sorting and Two-Pointers technique:
The idea is to use the two-pointer technique. But for using the two-pointer technique, the array
must be sorted. Once the array is sorted the two pointers can be taken which mark the beginning
and end of the array respectively. If the sum is greater than the sum of those two elements, shift
the right pointer to decrease the value of the required sum and if the sum is lesser than the
required value, shift the left pointer to increase the value of the required sum.
Illustration:
Let an array be {1, 4, 45, 6, 10, -8} and sum to find be 16
After sorting the array
A = {-8, 1, 4, 6, 10, 45}
Now, increment ‘l’ when the sum of the pair is less than the required sum and decrement ‘r’
when the sum of the pair is more than the required sum.
This is because when the sum is less than the required sum then to get the number which could
increase the sum of pair, start moving from left to right(also sort the array) thus “l++” and vice
versa.
Initialize l = 0, r = 5
A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 4
A[l] + A[r] ( -8 + 10) increment l. Now l = 1
A[l] + A[r] ( 1 + 10) increment l. Now l = 2
A[l] + A[r] ( 4 + 10) increment l. Now l = 3
A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)
Note: If there is more than one pair having the given sum then this algorithm reports only one.
Can be easily extended for this though.
Follow the steps below to solve the problem:
 hasArrayTwoCandidates (A[], ar_size, sum)
 Sort the array in non-decreasing order.
 Initialize two index variables to find the candidate
elements in the sorted array.
 Initialize first to the leftmost index: l = 0

 Initialize second the rightmost index: r = ar_size-1
 Loop while l < r.
If (A[l] + A[r] == sum) then return 1


Else if( A[l] + A[r] < sum ) then l++

Else r–

 No candidates in the whole array – return 0
// C++ program to check if given array

// has 2 elements whose sum is equal
// to the given value
// Function to check if array has 2 elements

// whose sum is equal to the given value
bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;
/* Sort the elements */

sort(A, A + arr_size);
/* Now look for the two candidates in

the sorted array*/
l = 0;
r = arr_size - 1;
while (l < r) {
if (A[l] + A[r] == sum)
return 1;
else if (A[l] + A[r] < sum)
l++;
else // A[l] + A[r] > sum
r--;
}
return 0;
}

int main()
{
int A[] = { 1, 4, 45, 6, 10, -8 };
int n = 16;
int arr_size = sizeof(A) / sizeof(A[0]);
// Function calling
if (hasArrayTwoCandidates(A, arr_size, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Output
Yes
Time Complexity: O(NlogN), Time complexity for sorting the array
Two Sum using Binary Search:
Sort the array, then traverse the array elements and perform binary search for (target – a[i]) on
the remaining part
Follow the below steps to solve the problem:
 Sort the array in non-decreasing order.
 Traverse from 0 to N-1
 Initialize searchKey = sum – A[i]
 If(binarySearch(searchKey, A, i + 1, N) == True
 Return True
 Return False
C++JavaPython3C#JavaScript
bool binarySearch(int A[], int low, int high, int searchKey)

{
while (low <= high) {

int m = low + (high - low) / 2;
// Check if searchKey is present at mid

if (A[m] == searchKey)
return true;
// If searchKey greater, ignore left half

if (A[m] < searchKey)
low = m + 1;
// If searchKey is smaller, ignore right half

else
high = m - 1;
}
// if we reach here, then element was
// not present
return false;
}
bool checkTwoSum(int A[], int arr_size, int sum)

{
int l, r;
/* Sort the elements */

sort(A, A + arr_size);
// Traversing all element in an array search for

// searchKey
for (int i = 0; i < arr_size - 1; i++) {
int searchKey = sum - A[i];

// calling binarySearch function
if (binarySearch(A, i + 1, arr_size - 1, searchKey)
== true) {
return true;
}
}
return false;
}

int main()
{
int A[] = { 1, 4, 45, 6, 10, -8 };
int n = 14;
// Function calling
if (checkTwoSum(A, arr_size, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Output
Yes
Time Complexity: O(NlogN)
Two Sum using Hashing:
This problem can be solved efficiently by using the technique of hashing. Use a hash_map to
check for the current array value x(let), if there exists a value target_sum-x which on adding to
the former gives target_sum. This can be done in constant time.
Illustration:
arr[] = {0, -1, 2, -3, 1}
sum = -2
Now start traversing:
Step 1: For ‘0’ there is no valid number ‘-2’ so store ‘0’ in hash_map.
Step 2: For ‘-1’ there is no valid number ‘-1’ so store ‘-1’ in hash_map.
Step 3: For ‘2’ there is no valid number ‘-4’ so store ‘2’ in hash_map.
Step 4: For ‘-3’ there is no valid number ‘1’ so store ‘-3’ in hash_map.
Step 5: For ‘1’ there is a valid number ‘-3’ so answer is 1, -3
unordered_set s
for(i=0 to end)
if(s.find(target_sum – arr[i]) == s.end)
insert(arr[i] into s)
else
print arr[i], target-arr[i]
 Initialize an empty hash table s.
 Do the following for each element A[i] in A[]
 If s[x – A[i]] is set then print the pair (A[i], x – A[i])

 Insert A[i] into s.

void printPairs(int arr[], int arr_size, int sum)

{
unordered_set<int> s;
for (int i = 0; i < arr_size; i++) {
int temp = sum - arr[i];
if (s.find(temp) != s.end()) {
cout << "Yes" << endl;
return;
}
s.insert(arr[i]);
}
cout << "No" << endl;
}
/* Driver Code */
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int n = 16;
// Function calling
printPairs(A, arr_size, n);
return 0;
}
Output
Yes
Time Complexity: O(N), As the whole array is needed to be traversed only once.
Auxiliary Space: O(N), A hash map has been used to store array elements.
Note: The solution will work even if the range of numbers includes negative numbers + if the
pair is formed by numbers recurring twice in array eg: array = [3,4,3]; pair = (3,3); target sum =
6.
Two Sum Using remainders of the elements less than x:
The idea is to count the elements with remainders when divided by x, i.e 0 to x-1, each remainder
separately. Suppose we have x as 6, then the numbers which are less than 6 and have remainders
which add up to 6 gives sum as 6 when added. For example, we have elements, 2,4 in the array
and 2%6 = 2 and 4%6 =4, and these remainders add up to give 6. Like that we have to check for
pairs with remainders (1,5),(2,4),(3,3). if we have one or more elements with remainder 1 and
one or more elements with remainder 5, then surely we get a sum as 6. Here we do not consider
(0,6) as the elements for the resultant pair should be less than 6. when it comes to (3,3) we have
to check if we have two elements with remainder 3, then we can say that “There exists a pair
whose sum is x”.
 1. Create an array with size x.
 2. Initialize all rem elements to zero.
 3. Traverse the given array
 Do the following if arr[i] is less than x:
 r=arr[i]%x which is done to get the remainder.
 rem[r]=rem[r]+1 i.e. increasing the count of elements that have remainder r when
divided with x.
 4. Now, traverse the rem array from 1 to x/2.
 If(rem[i]> 0 and rem[x-i]>0) then print “YES” and come out of the loop. This means that we
have a pair that results in x upon doing.
 5. Now when we reach at x/2 in the above loop
 If x is even, for getting a pair we should have two elements with remainder x/2.
 If rem[x/2]>1 then print “YES” else print “NO”
 If it is not satisfied that is x is odd, it will have a separate pair with x-x/2.
 If rem[x/2]>0 and rem[x-x/2]>0 , then print “Yes” else, print”No”;
// Code in cpp to tell if there exists a pair in array whose
// sum results in x.
#include <iostream>
// Function to print pairs

void printPairs(int a[], int n, int x)
{
int i;
int rem[x];
// initializing the rem values with 0's.
for (i = 0; i < x; i++)
rem[i] = 0;
// Perform the remainder operation only if the element
// is x, as numbers greater than x can't be used to get
// a sum x. Updating the count of remainders.
for (i = 0; i < n; i++)
if (a[i] < x)
rem[a[i] % x]++;
// Traversing the remainder list from start to middle to

// find pairs
for (i = 1; i < x / 2; i++) {
if (rem[i] > 0 && rem[x - i] > 0) {
// The elements with remainders i and x-i will
// result to a sum of x. Once we get two
// elements which add up to x , we print x and
// break.
cout << "Yes\n";
break;
}
}
// Once we reach middle of remainder array, we have to

// do operations based on x.
if (i >= x / 2) {
if (x % 2 == 0) {
// if x is even and we have more than 1 elements
// with remainder x/2, then we will have two
// distinct elements which add up to x. if we
// dont have more than 1 element, print "No".
if (rem[x / 2] > 1)
cout << "Yes\n";
else
cout << "No\n";
}
else {
// When x is odd we continue the same process
// which we did in previous loop.
if (rem[x / 2] > 0 && rem[x - x / 2] > 0)
cout << "Yes\n";
else
cout << "No\n";
}
}
}
/* Driver Code */
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int n = 16;
// Function calling
printPairs(A, arr_size, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)

Output
Yes
Time Complexity: O(N+X), Traversing over the array of size N and Checking for remainders
till X
Auxiliary Space: O(X), Space for storing remainders
Related Problems:
 Given two unsorted arrays, find all pairs whose sum is x
 Count pairs with given sum
 Count all distinct pairs with difference equal to k
Please write comments if you find any of the above codes/algorithms incorrect, or find other
ways to solve the same problem.
 Majority Element
Find the majority element in the array. A majority element in an array A[] of size n is an
element that appears more than n/2 times (and hence there is at most one such element).
Examples :
Input : A[]={3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is 5 which is greater than the half of the size of the array size.
Input : A[] = {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element
Explanation: There is no element whose frequency is greater than the half of the size of the
array size.
Recommended Problem
Naive Approach:
The basic solution is to have two loops and keep track of the maximum count for all different
elements. If the maximum count becomes greater than n/2 then break the loops and return the
element having the maximum count. If the maximum count doesn’t become more than n/2 then
the majority element doesn’t exist.
Illustration:
arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8
For i = 0:
 count = 0
 Loop over the array, whenever an element is equal to arr[i] (is 3), increment count
 count of arr[i] is 2, which is less than n/2, hence it can’t be majority element.
For i = 1:
 count = 0
 Loop over the array, whenever an element is equal to arr[i] (is 4), increment count
 count of arr[i] is 5, which is greater than n/2 (i.e 4), hence it will be majority element.
Hence, 4 is the majority element.
Follow the steps below to solve the given problem:
 Create a variable to store the max count, count = 0
 Traverse through the array from start to end.
 For every element in the array run another loop to find the count of similar elements in the
given array.
 If the count is greater than the max count update the max count and store the index in another
variable.
 If the maximum count is greater than half the size of the array, print the element. Else print
there is no majority element.
Below is the implementation of the above idea:

C++CJavaPython3C#JavascriptPHP
// C++ program to find Majority

// element in an array
// Function to find Majority element

// in an array
void findMajority(int arr[], int n)
{
int maxCount = 0;
int index = -1; // sentinels
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// update maxCount if count of

// current element is greater
if (count > maxCount) {
maxCount = count;
index = i;
}
}
// if maxCount is greater than n/2

// return the corresponding element
if (maxCount > n / 2)
cout << arr[index] << endl;
else
cout << "No Majority Element" << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
// Function calling
findMajority(arr, n);
return 0;
}
Output
1
Time Complexity: O(n*n), A nested loop is needed where both the loops traverse the array from
start to end.
Auxiliary Space: O(1), No extra space is required.
Majority Element using Binary Search Tree
Insert elements in BST one by one and if an element is already present then increment the count
of the node. At any stage, if the count of a node becomes more than n/2 then return.
Illustration:
 Create a binary search tree, if the same element is entered in the binary search tree the
frequency of the node is increased.
 traverse the array and insert the element in the binary search tree.
 If the maximum frequency of any node is greater than half the size of the array, then perform
an inorder traversal and find the node with a frequency greater than half
 Else print No majority Element.
CJavaPython3C#JavascriptC++14
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
int c;
struct node* left;
struct node* right;
};
struct node* newNode(int item) {

struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->c = 1;
temp->left = NULL;
temp->right = NULL;
return temp;
}
struct node* insert(struct node* node, int key, int* ma) {

if (node == NULL) {
if (*ma == 0)
*ma = 1;
return newNode(key);
}
if (key < node->key)

node->left = insert(node->left, key, ma);
else if (key > node->key)
node->right = insert(node->right, key, ma);
else
node->c++;
*ma = (*ma > node->c) ? *ma : node->c;

return node;
}
void inorder(struct node* root, int s) {

if (root != NULL) {
inorder(root->left, s);
if (root->c > (s / 2))

printf("%d \n", root->key);
inorder(root->right, s);
}
}
int main() {
int a[] = { 1, 3, 3, 3, 2 };
int size = sizeof(a) / sizeof(a[0]);
struct node* root = NULL;

int ma = 0;

root = insert(root, a[i], &ma);
}
if (ma > (size / 2))

inorder(root, size);
else
printf("No majority element\n");
return 0;
}
// This code is contributed by Vaibhav Saroj.
Output
Time Complexity: If a Binary Search Tree is used then time complexity will be O(n²). If a self-
balancing-binary-search tree is used then it will be O(nlogn)
Auxiliary Space: O(n), As extra space is needed to store the array in the tree.
Majority Element Using Moore’s Voting Algorithm:
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.
Illustration:
arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8
maj_index = 0, count = 1
At i = 1: arr[maj_index] != arr[i]
 count = count – 1 = 1 – 1 = 0
 now count == 0 then:
 maj_index = i = 1
 count = count + 1 = 0 + 1 = 1
 count = count – 1 = 1 – 1 = 0
 count = count + 1 = 0 + 1 = 1
 count = count – 1 = 1 – 1 = 0
 count = count + 1 = 0 + 1 = 1
 count = count – 1 = 1 – 1 = 0
 count = count + 1 = 0 + 1 = 1
At i = 5: arr[maj_index] == arr[i]
 count = count + 1 = 1 + 1 = 2
 count = count + 1 = 2 + 1 = 3
 count = count + 1 = 3 + 1 = 4
Therefore, the arr[maj_index] may be the possible candidate for majority element.
Now, Again traverse the array and check whether arr[maj_index] is the majority element or not.
arr[maj_index] is 4
4 occurs 5 times in the array therefore 4 is our majority element.
 Loop through each element and maintains a count of the majority element, and a majority
index, maj_index
 If the next element is the same then increment the count if the next element is not the same
then decrement the count.
 if the count reaches 0 then change the maj_index to the current element and set the count again
to 1.
 Now again traverse through the array and find the count of the majority element found.
 If the count is greater than half the size of the array, print the element
 Else print that there is no majority element
C++CJavaPython3C#JavascriptPHP
// C++ Program for finding out

// majority element in an array
/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0) {
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate

occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
int count = 0;
if (a[i] == cand)
count++;
if (count > size / 2)

return 1;
else
return 0;
}
/* Function to print Majority Element */

void printMajority(int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/

if (isMajority(a, size, cand))
cout << " " << cand << " ";
else
cout << "No Majority Element";
}
/* Driver code */
int main()
{
int a[] = { 1, 3, 3, 1, 2 };
int size = (sizeof(a)) / sizeof(a[0]);
// Function calling
printMajority(a, size);
return 0;
}
Output
No Majority Element
Time Complexity: O(n), As two traversal of the array, is needed, so the time complexity is
linear.
Auxiliary Space: O(1), As no extra space is required.
Majority Element Using Hashing:
In Hashtable(key-value pair), at value, maintain a count for each element(key), and whenever
the count is greater than half of the array length, return that key(majority element).
Illustration:
arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8
Create a hashtable for the array
3 -> 2
4 -> 5
2 -> 1
Now traverse the hashtable
 Count for 3 is 2, which is less than n/2 (4) therefore it can’t be the majority element.
 Count for 4 is 5, which is greater than n/2 (4) therefore 4 is the majority element.
 Create a hashmap to store a key-value pair, i.e. element-frequency pair.
 Traverse the array from start to end.
 For every element in the array, insert the element in the hashmap if the element does not exist
as a key, else fetch the value of the key ( array[i] ), and increase the value by 1
 If the count is greater than half then print the majority element and break.
 If no majority element is found print “No Majority element”
C++CJavaPython3C#Javascript
/* C++ program for finding out majority

element in an array */
void findMajority(int arr[], int size)

{
unordered_map<int, int> m;
for(int i = 0; i < size; i++)
m[arr[i]]++;
int count = 0;
for(auto i : m)
{
if(i.second > size / 2)
{
count =1;
cout << "Majority found :- " << i.first<<endl;
break;
}
}
if(count == 0)
cout << "No Majority element" << endl;
}
// Driver code
int main()
{
int arr[] = {2, 2, 2, 2, 5, 5, 2, 3, 3};
// Function calling
return 0;
}
// This code is contributed by codeMan_d
Output
Majority found :- 2
Time Complexity: O(n), One traversal of the array is needed, so the time complexity is linear.
Auxiliary Space: O(n), Since a hashmap requires linear space.
Majority Element Using Sorting:
The idea is to sort the array. Sorting makes similar elements in the array adjacent, so traverse
the array and update the count until the present element is similar to the previous one. If the
frequency is more than half the size of the array, print the majority element.
Illustration:
arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8
Array after sorting => arr[] = {2, 3, 3, 4, 4, 4, 4, 4}, count = 1
At i = 1:
 arr[i] != arr[i – 1] => arr[1] != arr[0]
 count is not greater than n/2, therefore reinitialise count with, count = 1
At i = 2:
 arr[i] == arr[i – 1] => arr[2] == arr[1] = 3
 count = count + 1 = 1 + 1 = 2
At i = 3
 arr[i] != arr[i – 1] => arr[3] != arr[2]
 count is not greater than n/2, therefore reinitialise count with, count = 1
At i = 4
 arr[i] == arr[i – 1] => arr[4] == arr[3] = 4
 count = count + 1 = 1 + 1 = 2
At i = 5
 arr[i] == arr[i – 1] => arr[5] == arr[4] = 4
 count = count + 1 = 2 + 1 = 3
At i = 6
 arr[i] == arr[i – 1] => arr[6] == arr[5] = 4
 count = count + 1 = 3 + 1 = 4
At i = 7
 arr[i] == arr[i – 1] => arr[7] == arr[6] = 4
 count = count + 1 = 4 + 1 = 5
 Therefore, the count of 4 is now greater than n/2.
 Sort the array and create a variable count and previous, prev = INT_MIN.
 Traverse the element from start to end.
 If the current element is equal to the previous element increase the count.
 Else set the count to 1.
 If the count is greater than half the size of the array, print the element as the majority element
and break.
 If no majority element is found, print “No majority element”
C++JavaPython3C#Javascript
// C++ program to find Majority

// element in an array
// Function to find Majority element

// in an array
// it returns -1 if there is no majority element
int majorityElement(int *arr, int n)

{
if (n == 1) return arr[0];
int cnt = 1;
// sort the array, o(nlogn)
sort(arr, arr + n);
for (int i = 1; i <= n; i++){
if (arr[i - 1] == arr[i]){
cnt++;
}
else{
if (cnt > n / 2){
return arr[i - 1];
}
cnt = 1;
}
}
// if no majority element, return -1
return -1;
}
// Driver code
int main()
{
int arr[] = {1, 1, 2, 1, 3, 5, 1};
// Function calling
cout<<majorityElement(arr, n);
return 0;
}
Output
Time Complexity: O(nlogn), Sorting requires O(n log n) time complexity.

Approach using Recursion:
The idea is to use the divide and conquer strategy to identify the majority element in an array
using a recursive approach.
Majority Element Using Recursive Approach:
In this recursive approach, we divide the array into halves until we reach base cases where the
array has only one element. Then, we combine the majority elements obtained from the left and
right halves to find the overall majority element of the entire array.
Illustration:
Consider an array arr[] = {3, 4, 3, 2, 4, 4, 4, 4} with n = 8.
Split the array into two halves: left half arr_left[] = {3, 4, 3, 2} and right half arr_right[] = {4,
4, 4, 4}.
Recursively find the majority elements of both halves.
Combine the majority elements obtained from both halves.
Check if the combined majority element appears more than n/2 times in the entire array.
Follow the steps below to solve the given problem using a recursive approach:
Define a recursive function findMajorityUtil that takes an array arr[], its lower index low, and
upper index high as input parameters.
If the array has only one element (low == high), return that element as the majority element.
Divide the array into two halves and recursively find the majority elements of both halves.
Combine the majority elements obtained from both halves.
Count the occurrences of the combined majority element in the entire array.
Return the combined majority element if it appears more than n/2 times; otherwise, return -1.
 Define a function “countOccurrences” which takes an array “arr”, its size “n”, and an
integer “num” as input parameters. This function counts the number of occurrences of the
given integer in the array and returns the count. And the initial count is 0.
 Then we’ll define a recursive function “findMajorityUtil” that takes an array, its
lower “low” and upper “high” indices as input parameters. This function has the following
steps:
 Check if the array has only one element (base case). If yes, return that element.
 Divide the array into two equal parts, left and right by finding the mid index.
 Recursively find the majority element in the left part and right part.
 If both the left and right parts have the same majority elements, then return that
element.
 Count the total number of occurrences of the left and right majority elements in the
entire array.
 Return the element that occurs more than n/2 times.
 Define a function “findMajority” which takes an array “arr” and its size “n” as input
parameters. This function calls the “findMajorityUtil” function with the array and its indices
and prints the majority element if it exists; otherwise, it will print “No Majority Element”.
 The “main” function will initialize an array “arr” and size “n”. It will call
the “findMajority” function with these parameters.
C++CJavaPython3C#Javascript
// C++ program for the above approach

// Function to count the occurrences

int countOccurrences(int arr[], int n, int num) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == num)
count++;
}
return count;
}
// Function to find the majority element

// using recursion
int findMajorityUtil(int arr[], int low, int high) {
// Base case: single element array

if (low == high)
return arr[low];
// Divide the array into left

// and right halves
int leftMajority = findMajorityUtil(arr, low, mid);
int rightMajority = findMajorityUtil(arr, mid+1, high);
// If left and right halves have the

// same majority element
if (leftMajority == rightMajority)
return leftMajority;
// Count the occurrences of the

// majority element in entire array
int leftCount = countOccurrences(arr, high-low+1, leftMajority);
int rightCount = countOccurrences(arr, high-low+1, rightMajority);
// Return the element that occurs

// more than n/2 times
if (leftCount > (high-low+1) / 2)
return leftMajority;
if (rightCount > (high-low+1) / 2)
return rightMajority;
// No majority element
return -1;
}
// Function to find the majority element

void findMajority(int arr[], int n) {
int majority = findMajorityUtil(arr, 0, n-1);
if (majority != -1)
cout << majority << endl;
else
}
// Driver Code
int main() {
int arr[] = {1, 3, 3, 3, 2};
return 0;
}
Output
Time Complexity: O(N*log N)

Space Complexity: O(log N)
Majority Element Using Bit Manipulation:
In this approach, we utilize bitwise operations to count the occurrences of each bit position for
all elements in the array. By analyzing the majority bits obtained, we can reconstruct the
majority element.
Illustration:
Consider an array arr[] = {3, 4, 3, 2, 4, 4, 4, 4} with n = 8.
Iterate through each element in the array and count the occurrences of each bit position.
Reconstruct the majority element from the majority bits obtained.
Check if the reconstructed majority element appears more than n/2 times in the array.
 Iterate through the array and count the occurrences of each bit position using bitwise
operations.
 Reconstruct the majority element from the majority bits obtained.
 Check if the reconstructed majority element appears more than n/2 times in the array.

C++CJavaPythonC#JavaScript
#include <iostream>
#include <vector>
int majorityElement(vector<int>& nums) {

int num_bits = 32;
int majority_element = 0;
for (int i = 0; i < num_bits; ++i) {

int count_ones = 0, count_zeros = 0;
for (int num : nums) {

if ((num >> i) & 1)
count_ones++;
else
count_zeros++;
}
if (count_ones > count_zeros)

majority_element |= (1 << i);
}
int count_majority = 0;
for (int num : nums) {
if (num == majority_element)
count_majority++;
}
return count_majority > nums.size() / 2 ? majority_element : -1;

}
int main() {
vector<int> nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
int result = majorityElement(nums);
if (result != -1)
cout << "Majority Element: " << result << endl;
else
return 0;
}
Output:
Majority Element: 4
Time Complexity: O(n * k), where n is the number of elements in the array and k is the number
of bits in an integer.
 Find the Number Occurring Odd Number of Times

Find the Number Occurring Odd Number of Times
Given an array of positive integers. All numbers occur an even number of times except one
number which occurs an odd number of times. Find the number in O(n) time & constant space.
Examples :
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3
Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5
Recommended Practice
A Simple Solution is to run two nested loops. The outer loop picks all elements one by one and
the inner loop counts the number of occurrences of the element picked by the outer loop.
Below is the implementation of the brute force approach :
C++JavaC#JavascriptPHPPython3
// C++ program to find the element

// occurring odd number of times
#include<bits/stdc++.h>
// Function to find the element

int getOddOccurrence(int arr[], int arr_size)
{
for (int i = 0; i < arr_size; i++) {
int count = 0;
for (int j = 0; j < arr_size; j++)

{
if (arr[i] == arr[j])
count++;
}
if (count % 2 != 0)
return arr[i];
}
return -1;
}
// driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 2,
4, 3, 5, 2, 4, 4, 2 };
// Function calling
cout << getOddOccurrence(arr, n);
return 0;
}
Output :
5
Time Complexity: O(n^2)

Find the Number Occurring Odd Number of Times using Hashing:
A Better Solution is to use Hashing. Use array elements as a key and their counts as values.
Create an empty hash table. One by one traverse the given array elements and store counts.
Below is the implementation of the above approch:
C++JavaC#JavascriptPython3

// function to find the element

int getOddOccurrence(int arr[],int size)
{
// Defining HashMap in C++

unordered_map<int, int> hash;
// Putting all elements into the HashMap

for(int i = 0; i < size; i++)
{
hash[arr[i]]++;
}
// Iterate through HashMap to check an element
// occurring odd number of times and return it
for(auto i : hash)
{
if(i.second % 2 != 0)
{
return i.first;
}
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 2, 4,
3, 5, 2, 4, 4, 2 };
// Function calling
cout << getOddOccurrence(arr, n);
return 0;
}
// This code is contributed by codeMan_d.

Output :
5

Auxiliary Space: O(n)
Find the Number Occurring Odd Number of Times using Bit Manipulation:
The Best Solution is to do bitwise XOR of all the elements. XOR of all elements gives us odd
occurring elements.
Here ^ is the XOR operators;
Note :
x^0 = x
x^y=y^x (Commutative property holds)
(x^y)^z = x^(y^z) (Distributive property holds)
x^x=0

C++CJavaC#JavascriptPHPPython3

// Function to find element occurring

// odd number of times
int getOddOccurrence(int ar[], int ar_size)
{
int res = 0;
for (int i = 0; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
/* Driver function to test above function */

int main()
{
int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = sizeof(ar)/sizeof(ar[0]);
// Function calling
cout << getOddOccurrence(ar, n);
return 0;
}
Output :
5

 Largest Sum Contiguous Subarray

Largest Sum Contiguous Subarray (Kadane’s Algorithm)



Given an array arr[] of size N. The task is to find the sum of the contiguous subarray within
a arr[] with the largest sum.
The idea of Kadane’s algorithm is to maintain a variable max_ending_here that stores the
maximum sum contiguous subarray ending at current index and a variable max_so_far stores
the maximum sum of contiguous subarray found so far, Everytime there is a positive-sum value
in max_ending_here compare it with max_so_far and update max_so_far if it is greater
than max_so_far.
So the main Intuition behind Kadane’s Algorithm is,
 The subarray with negative sum is discarded (by assigning max_ending_here = 0 in code).
 We carry subarray till it gives positive sum.
Pseudocode of Kadane’s algorithm:
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
Illustration of Kadane’s Algorithm:

Lets take the example: {-2, -3, 4, -1, -2, 1, 5, -3}
Note: in the image max_so_far is represented by Max_Sum and max_ending_here
by Curr_Sum
For i=0, a[0] = -2
 max_ending_here = max_ending_here + (-2)
 Set max_ending_here = 0 because max_ending_here < 0
 and set max_so_far = -2
For i=1, a[1] = -3
 Since max_ending_here = -3 and max_so_far = -2, max_so_far will remain -2
 Set max_ending_here = 0 because max_ending_here < 0
For i=2, a[2] = 4
 max_ending_here = max_ending_here + (4)
 max_ending_here = 4
 max_so_far is updated to 4 because max_ending_here greater than max_so_far which was -2
till now
For i=3, a[3] = -1
For i=4, a[4] = -2
For i=5, a[5] = 1
For i=6, a[6] = 5
 max_ending_here =
 max_so_far is updated to 7 because max_ending_here is greater than max_so_far
For i=7, a[7] = -3
Follow the below steps to Implement the idea:
 Initialize the variables max_so_far = INT_MIN and max_ending_here = 0
 Run a for loop from 0 to N-1 and for each index i:
 Add the arr[i] to max_ending_here.
 If max_so_far is less than max_ending_here then update max_so_far to
max_ending_here.
 If max_ending_here < 0 then update max_ending_here = 0
 Return max_so_far
Below is the Implementation of the above approach.
C++JavaPython3C#JavascriptPHP
// C++ program to print largest contiguous array sum

int maxSubArraySum(int a[], int size)

{
int max_so_far = INT_MIN, max_ending_here = 0;

max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Driver Code
int main()
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = sizeof(a) / sizeof(a[0]);
// Function Call
int max_sum = maxSubArraySum(a, n);
cout << "Maximum contiguous sum is " << max_sum;
return 0;
}
Output
Maximum contiguous sum is 7

Print the Largest Sum Contiguous Subarray:
To print the subarray with the maximum sum the idea is to maintain start index
of maximum_sum_ending_here at current index so that whenever maximum_sum_so_far is
updated with maximum_sum_ending_here then start index and end index of subarray can be
updated with start and current index.
 Initialize the variables s, start, and end with 0 and max_so_far = INT_MIN
and max_ending_here = 0
 Run a for loop from 0 to N-1 and for each index i:
 Add the arr[i] to max_ending_here.
 If max_so_far is less than max_ending_here then update max_so_far to
max_ending_here and update start to s and end to i .
 If max_ending_here < 0 then update max_ending_here = 0 and s with i+1.
 Print values from index start to end.
Below is the Implementation of above approach:

C++JavaPython3C#JavascriptPHP
#include <climits>
#include <iostream>
void maxSubArraySum(int a[], int size)

{
int max_so_far = INT_MIN, max_ending_here = 0,
start = 0, end = 0, s = 0;

max_ending_here += a[i];
if (max_so_far < max_ending_here) {

max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0) {
max_ending_here = 0;
s = i + 1;
}
}
cout << "Maximum contiguous sum is " << max_so_far
<< endl;
cout << "Starting index " << start << endl
<< "Ending index " << end << endl;
}
/*Driver program to test maxSubArraySum*/

int main()
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
maxSubArraySum(a, n);
return 0;
}
Output
Maximum contiguous sum is 7

Starting index 2
Ending index 6

Largest Sum Contiguous Subarray using Dynamic Programming:

For each index i, DP[i] stores the maximum possible Largest Sum Contiguous Subarray ending
at index i, and therefore we can calculate DP[i] using the mentioned state transition:
 DP[i] = max(DP[i-1] + arr[i] , arr[i] )
Below is the implementation:
C++JavaPython3C#Javascript

void maxSubArraySum(int a[], int size)

{
vector<int> dp(size, 0);
dp[0] = a[0];
int ans = dp[0];
dp[i] = max(a[i], a[i] + dp[i - 1]);
ans = max(ans, dp[i]);
}
cout << ans;
}
/*Driver program to test maxSubArraySum*/

int main()
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
maxSubArraySum(a, n);
return 0;
}
Output
7
Practice Problem:
Given an array of integers (possibly some elements negative), write a C program to find out the
*maximum product* possible by multiplying ‘n’ consecutive integers in the array where n ?
ARRAY_SIZE. Also, print the starting point of the maximum product subarray.
 Find the Missing Number

Find the Missing Number



Given an array arr[] of size N-1 with integers in the range of [1, N], the task is to find the
missing number from the first N integers.
Note: There are no duplicates in the list.
Examples:
Input: arr[] = {1, 2, 4, 6, 3, 7, 8}
Output: 5
Explanation: Here the size of the array is 8, so the range will be [1, 8]. The missing number
between 1 to 8 is 5
Input: arr[] = {1, 2, 3, 5}, N = 5
Output: 4
Explanation: Here the size of the array is 4, so the range will be [1, 5]. The missing number
between 1 to 5 is 4
Approach 1 (Using Hashing): The idea behind the following approach is

The numbers will be in the range (1, N), an array of size N can be maintained to keep record of
the elements present in the given array
 Create a temp array temp[] of size n + 1 with all initial values as 0.
 Traverse the input array arr[], and do following for each arr[i]
 if(temp[arr[i]] == 0) temp[arr[i]] = 1
 Traverse temp[] and output the array element having value as 0 (This is the missing element).
// C++ program to Find the missing element
void findMissing(int arr[], int N)

{
int i;
int temp[N + 1];
for(int i = 0; i <= N; i++){
temp[i] = 0;
}
for(i = 0; i < N; i++){
temp[arr[i] - 1] = 1;
}
int ans;
for (i = 0; i <= N ; i++) {
if (temp[i] == 0)
ans = i + 1;
}
cout << ans;
}
/* Driver code */
int main()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
findMissing(arr, n);
}
Output

Auxiliary Space: O(N)
Approach 2 (Using summation of first N natural numbers): The idea behind the approach is
to use the summation of the first N numbers.
Find the sum of the numbers in the range [1, N] using the formula N * (N+1)/2. Now find the
sum of all the elements in the array and subtract it from the sum of the first N natural numbers.
This will give the value of the missing element.
 Calculate the sum of the first N natural numbers as sumtotal= N*(N+1)/2.
 Find the sum of all the array elements.
 Print the missing number as SumTotal – sum of array
C++CJavaPythonC#JavaScriptPHP
// Function to get the missing number

int getMissingNo(int a[], int n)
{
// Given the range of elements
// are 1 more than the size of array
int N = n + 1;
int total = (N) * (N + 1) / 2;

for (int i = 0; i < n; i++)
total -= a[i];
return total;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
int miss = getMissingNo(arr, N);
cout << miss;
return 0;
}
Output

Modification for Overflow: The approach remains the same but there can be an overflow if N is
large.
In order to avoid integer overflow, pick one number from the range [1, N] and subtract a
number from the given array (don’t subtract the same number twice). This way there won’t be
any integer overflow.
Algorithm:
 Create a variable total = 1 which will store the total sum of first n elements.
 Update the value of total as total += i , now decrease value of total by current array
element.
 Print the missing number , which will be present in the total variable.
// Function to get the missing element

{
int i, total = 1;
for (i = 2; i < (n + 1); i++) {

total += i;
total -= a[i - 2];
}
return total;
}
// Driver Program
int main()
{
int arr[] = { 1, 2, 3, 5 };
// Function call
cout << getMissingNo(arr, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Output
4
Time Complexity: O(N). Only one traversal of the array is needed.
Auxiliary Space: O(1). No extra space is needed
Approach 3 (Using binary operations): This method uses the technique of XOR to solve the
problem.
XOR has certain properties
 Assume a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an = a and a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an-1 = b
 Then a ⊕ b = an
 Create two variables a = 0 and b = 0
 Run a loop from i = 1 to N:
 For every index, update a as a = a ^ i
 Now traverse the array from i = start to end.
 For every index, update b as b = b ^ arr[i].
 The missing number is a ^ b.
C++CJavaPythonC#JavaScriptPHP
// Java program to find missing Number

// using xor
class Main {
// Function to find missing number

static int getMissingNo(int a[], int n)
{
int x1 = a[0];
int x2 = 1;
// For xor of all the elements in array

for (int i = 1; i < n; i++)
x1 = x1 ^ a[i];
// For xor of all the elements from 1 to n+1

for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);

}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 5 };
int N = arr.length;
// Function call
System.out.println(miss);
}
}
Output

Approach 4 (Using Cyclic Sort): The idea behind it is as follows:

All the given array numbers are sorted and in the range of 1 to n-1. If the range is 1 to N then
the index of every array element will be the same as (value – 1).
 Use cyclic sort to sort the elements in linear time.
 Now traverse from i = 0 to the end of the array:
 If arr[i] is not the same as i+1 then the missing element is (i+1).
 If all elements are present then N is the missing element in the range [1, N].
// C++ program to find the missing Number
// Function to find the missing number

{
int i = 0;
while (i < n) {
int correct = a[i] - 1;
if (a[i] < n && a[i] != a[correct]) {
swap(a[i], a[correct]);
}
else {
i++;
}
}
for (int i = 0; i < n; i++) {

if (i != a[i] - 1) {
return i + 1;
}
}
return n;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 5 };
// Function call
cout << (miss);
return 0;
}
Output
4
Time Complexity: O(N), requires (N-1) comparisons
Auxiliary Complexity: O(1)
Approach 5 (Use elements as Index and mark the visited places as negative): Use the below
idea to get the approach
Traverse the array. While traversing, use the absolute value of every element as an index and
make the value at this index as negative to mark it visited. To find missing, traverse the array
again and look for a positive value.
Follow the steps to solve the problem:
 Traverse the given array
 If the absolute value of current element is greater than size of the array, then
continue.
 else multiply the (absolute value of (current element) – 1)th index with -1.
 Initialize a variable ans = size + 1.
 Traverse the array and follow the steps:
 if the value is positive assign ans = index + 1
 Print ans as the missing value.
// C++ program to Find the missing element
void findMissing(int arr[], int size)

{
int i;
for (i = 0; i < size; i++) {

if(abs(arr[i]) - 1 == size){
continue;
}
int ind = abs(arr[i]) - 1;
arr[ind] *= -1;
}
int ans = size + 1;

for (i = 0; i < size; i++) {
if (arr[i] > 0)
ans = i + 1;
}
cout << ans;
}
/* Driver code */
int main()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
findMissing(arr, n);
}
Output
4
 Search an element in a sorted and pivoted array

Search an element in a sorted and rotated Array
Given a sorted and rotated array arr[] of size N and a key, the task is to find the key in the array.
Note: Find the element in O(logN) time and assume that all the elements are distinct.
Example:
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 3
Output : Found at index 8
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}, key = 10
Output : Found at index 3
Approach 1 (Finding Pivot where rotation has happened): The primary idea to solve the
problem is as follows.
The idea is to find the pivot point, divide the array into two sub-arrays and perform a binary
search.
The main idea for finding a pivot is –
 For a sorted (in increasing order) and rotated array, the pivot element is the only element for
which the next element to it is smaller than it.
 Using binary search based on the above idea, pivot can be found.
 It can be observed that for a search space of indices in range [l, r] where the middle
index is mid,
 If rotation has happened in the left half, then obviously the element at l will
be greater than the one at mid.
 Otherwise the left half will be sorted but the element at mid will be greater
than the one at r.
 After the pivot is found divide the array into two sub-arrays.
 Now the individual sub-arrays are sorted so the element can be searched using Binary Search.
 Find out the pivot point using binary search. We will set the low pointer as the first array index
and high with the last array index.
 From the high and low we will calculate the mid value.
 If the value at mid-1 is greater than the one at mid, return that value as the pivot.
 Else if the value at the mid+1 is less than mid, return mid value as the pivot.
 Otherwise, if the value at low position is greater than mid position, consider the left
half. Otherwise, consider the right half.
 Divide the array into two sub-arrays based on the pivot that was found.
 Now call binary search for one of the two sub-arrays.
 If the element is greater than the 0th element then search in the left array
 Else search in the right array.
 If the element is found in the selected sub-array then return the index
 Else return -1.
Follow the below illustration for a better understanding
Illustration:
Consider arr[] = {3, 4, 5, 1, 2}, key = 1
Pivot finding:
low = 0, high = 4:
=> mid = 2
=> arr[mid] = 5, arr[mid + 1] = 1
=> arr[mid] > arr[mid +1],
=> Therefore the pivot = mid = 2
Array is divided into two parts {3, 4, 5}, {1, 2}
Now according to the conditions and the key, we need to find in the part {1, 2}
Key Finding:
We will apply Binary search on {1, 2}.
low = 3 , high = 4.
=> mid = 3
=> arr[mid] = 1 , key = 1, hence arr[mid] = key matches.
=> The required index = mid = 3
So the element is found at index 3.
 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
/* Java program to search an element
in a sorted and pivoted array*/
import java.io.*;
class Main {
/* Searches an element key in a

pivoted sorted array arrp[]
of size n */
static int pivotedBinarySearch(int arr[], int n,
int key)
{
int pivot = findPivot(arr, 0, n - 1);
// If we didn't find a pivot, then

// array is not rotated at all
if (pivot == -1)
return binarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first

// compare with pivot and then
// search in two subarrays around pivot
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
return binarySearch(arr, pivot + 1, n - 1, key);
}
/* Function to get pivot. For array

3, 4, 5, 6, 1, 2 it returns
3 (index of 6) */
static int findPivot(int arr[], int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
/* low + (high - low)/2; */

if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
/* Standard Binary Search function */

static int binarySearch(int arr[], int low, int high,
int key)
{
if (high < low)
return -1;
/* low + (high - low)/2; */

return mid;
if (key > arr[mid])
}
// main function
{
// Let us search 3 in below array
int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = arr1.length;
int key = 3;
System.out.println(
"Index of the element is : "
+ pivotedBinarySearch(arr1, n, key));
}
}
Output
Index of the element is : 8
Time Complexity: O(log N) Binary Search requires log n comparisons to find the element.
Auxiliary Complexity: O(1)
Thanks to Ajay Mishra for providing the above solution.
Approach 2 (Direct Binary Search on Array without finding Pivot):

The idea is to instead of two or more passes of binary search, the result can be found in one
pass of binary search.
The idea is to create a recursive function to implement the binary search where the search
region is [l, r]. For each recursive call:
 We calculate the mid value as mid = (l + h) / 2
 Then try to figure out if l to mid is sorted, or (mid+1) to h is sorted
 Based on that decide the next search region and keep on doing this till the element is found
or l overcomes h.
 Use a recursive function to implement binary search to find the key:
 Find middle-point mid = (l + h)/2
 If the key is present at the middle point, return mid.
 Else if the value at l is less than the one at mid then arr[l . . . mid] is sorted
 If the key to be searched lies in the range from arr[l] to arr[mid], recur
for arr[l . . . mid].
 Else recur for arr[mid+1 . . . h]
 Else arr[mid+1. . . h] is sorted:
 If the key to be searched lies in the range from arr[mid+1] to arr[h], recur
for arr[mid+1. . . h].
 Else recur for arr[l. . . mid]
Follow the below illustration for a better understanding:
Illustration:
Input arr[] = {3, 4, 5, 1, 2}, key = 1
Initially low = 0, high = 4.
low = 0, high = 4:
=> mid = 2
=> arr[mid] = 5, which is not the desired value.
=> arr[low] < arr[mid] So, the left half is sorted.
=> key < arr[low], So the next search region is 3 to 4.
low = 3, high = 4:
=> mid = 3
=> arr[mid] = 1 = key
=> So the element is found at index 3.
The element is found at index 3.
 C++
 C
 Java
 Python3
 C#
 Javascript
 PHP
/* Java program to search an element in
sorted and rotated array using
single pass of Binary Search*/
import java.io.*;
class Main {
// Returns index of key in arr[l..h]
// if key is present, otherwise returns -1
static int search(int arr[], int l, int h, int key)
{
if (l > h)
return -1;
int mid = (l + h) / 2;
if (arr[mid] == key)
return mid;
/* If arr[l...mid] first subarray is sorted */

if (arr[l] <= arr[mid]) {
/* As this subarray is sorted, we
can quickly check if key lies in
half or other half */
if (key >= arr[l] && key <= arr[mid])
return search(arr, l, mid - 1, key);
/*If key not lies in first half subarray,
Divide other half into two subarrays,
such that we can quickly check if key lies
in other half */
return search(arr, mid + 1, h, key);
}
/* If arr[l..mid] first subarray is not sorted,

then arr[mid... h] must be sorted subarray*/
if (key >= arr[mid] && key <= arr[h])
return search(arr, mid + 1, h, key);
return search(arr, l, mid - 1, key);

}
// main function
{
int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
int n = arr.length;
int key = 3;
int i = search(arr, 0, n - 1, key);
if (i != -1)
System.out.println("Index: " + i);
else
System.out.println("Key not found");
}
}
// This code is contributed by Aditya Kumar

(adityakumar129)
Output
Index: 8
Time Complexity: O(log N). Binary Search requires log n comparisons to find the element. So
time complexity is O(log n).
Auxiliary Space: O(1). As no extra space is required.
Thanks to Gaurav Ahirwar for suggesting the above solution.
How to handle duplicates?

At first look, it doesn’t look possible to search in O(Log N) time in all cases when duplicates are
allowed.
For example consider searching 0 in {2, 2, 2, 2, 2, 2, 2, 2, 0, 2} and {2, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2}.
Look into the following article to find a solution to this
issue: https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-rotated-array-with-
duplicates/
Similar Articles:
 Find the minimum element in a sorted and rotated array
 Given a sorted and rotated array, find if there is a pair with a given sum.
Please write comments if you find any bug in the above codes/algorithms, or find other ways to
solve the same problem.
Approach#3: Using linear search
This approach uses linear search to find the index of the key in a sorted and rotated array. The
idea is to iterate through the array and compare each element with the key until we find a match.
Algorithm
1. Initialize a loop index i to 0, and iterate over the array using a for loop.
2. For each element of the array, check if it is equal to the given key.
3. If the key is found, return the index of the element.
4. If the end of the array is reached without finding the key, return -1 to indicate that the key was
not found.
 C++
 Java
 Python3
 C#
 Javascript
/*package whatever //do not write package name here */
import java.io.*;
public class GFG {

public static int searchRotatedArray(int[] arr, int key) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 6, 7, 8, 9, 10, 1, 2, 3};
int key = 3;
int index = searchRotatedArray(arr, key);
if (index != -1) {
System.out.println("Found at index " + index);
} else {
System.out.println("Not found");
}
}
}
//This article is contributed by Abhay
Output
Found at index 8
Time complexity of this algorithm is O(n), where n is the length of the input array.
Space complexity is O(1), as the program only uses a constant amount of extra space to store the
loop index and the return value.
 Merge an array of size n into another array of size m+n

Merge an array of size n into another array of size m+n
There are two sorted arrays. First one is of size m+n containing only m elements. Another one is
of size n and contains n elements. Merge these two arrays into the first array of size m+n such
that the output is sorted.
Input: array with m+n elements (mPlusN[]).
NA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.
Input: array with n elements (N[]).
Output: N[] merged into mPlusN[] (Modified mPlusN[])
Algorithm:
Let first array be mPlusN[] and other array be N[]
1) Move m elements of mPlusN[] to end.
2) Start from nth element of mPlusN[] and 0th
element of N[] and merge them into mPlusN[].
Below is the implementation of the above algorithm :
 C++
 C
 Java
 Python3
 C#
 PHP
 Javascript
// Java program to Merge an array of

// size n into another array of size m + n
class MergeArrays {
/* Function to move m
elements at the end of array
* mPlusN[] */
void moveToEnd(int mPlusN[], int size)
{
int i, j = size - 1;
for (i = size - 1; i >= 0; i--) {
if (mPlusN[i] != -1) {
mPlusN[j] = mPlusN[i];
j--;
}
}
}
/* Merges array N[] of

size n into array mPlusN[]
of size m+n*/
void merge(int mPlusN[], int N[], int m, int n)
{
int i = n;
/* Current index of i/p part of mPlusN[]*/

int j = 0;
/* Current index of N[]*/
int k = 0;
/* Current index of output mPlusN[]*/

while (k < (m + n))
{
/* Take an element from mPlusN[] if
a) value of the picked element is smaller and we
have not reached end of it b) We have reached
end of N[] */
if ((i < (m + n) && mPlusN[i] <= N[j])
|| (j == n)) {
mPlusN[k] = mPlusN[i];
k++;
i++;
}
else // Otherwise take element from N[]
{
mPlusN[k] = N[j];
k++;
j++;
}
}
}
/* Utility that prints out an array on a line */

{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
// Driver Code
public static void main(String[] args)
{
MergeArrays mergearray = new MergeArrays();
/* Initialize arrays */
int mPlusN[] = { 2, 8, -1, -1, -1, 13, -1, 15, 20 };
int N[] = { 5, 7, 9, 25 };
int n = N.length;
int m = mPlusN.length - n;
/*Move the m elements at the end of mPlusN*/

mergearray.moveToEnd(mPlusN, m + n);
/*Merge N[] into mPlusN[] */

mergearray.merge(mPlusN, N, m, n);
/* Print the resultant mPlusN */

mergearray.printArray(mPlusN, m + n);
}
}
// This code has been contributed by Mayank Jaiswal

Output
2 5 7 8 9 13 15 20 25
Time Complexity: O(m+n)
 Median of two sorted arrays
Median of two Sorted Arrays of Different Sizes




Given two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays,
where N is the number of elements in the first array, and M is the number of elements in the
second array.
This is an extension of Median of two sorted arrays of equal size problem. Here we handle
arrays of unequal size also.
Examples:
Input: a[] = {-5, 3, 6, 12, 15}, b[] = {-12, -10, -6, -3, 4, 10}
Output: The median is 3.
Explanation: The merged array is: ar3[] = {-12, -10, -6, -5 , -3, 3, 4, 6, 10, 12, 15}.
So the median of the merged array is 3
Input: a[] = {2, 3, 5, 8}, b[] = {10, 12, 14, 16, 18, 20}
Output: The median is 11.
Explanation : The merged array is: ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
If the number of the elements are even. So there are two middle elements.
Take the average between the two: (10 + 12) / 2 = 11.
Naive Approach to find Median of two sorted Arrays of different sizes

The idea is to merge them into third array and there are two cases:
 Case 1: If the length of the third array is odd, then the median is at (length)/2th index in the
array obtained after merging both the arrays.
 Case 2: If the length of the third array is even, then the median will be the average of elements
at index ((length)/2 ) and ((length)/2 – 1) in the array obtained after merging both arrays.
Illustration:
arr1[] = { -5, 3, 6, 12, 15 } , arr2[] = { -12, -10, -6, -3, 4, 10 }
 After merging them in a third array : arr3[] = { -5, 3, 6, 12, 15, -12, -10, -6, -3, 4, 10}
 Sort arr3[ ] = { -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 }
 As the length of arr3 is odd, so the median is 3
 C++
 Java
 Python3
 C#
 Javascript
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
public class GFG {

public static int Solution(int[] arr)
{
int n = arr.length;
// If length of array is even

if (n % 2 == 0) {
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd

else {
int z = Math.round(n / 2);
return arr[z];
}
}
// Driver Code
{
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
int i = arr1.length;
int j = arr2.length;
int[] arr3 = new int[i + j];
// Merge two array into one array

System.arraycopy(arr1, 0, arr3, 0, i);
System.arraycopy(arr2, 0, arr3, i, j);
// Sort the merged array

Arrays.sort(arr3);
// calling the method

System.out.print("Median = " + Solution(arr3));
}
}
// This code is contributed by Manas Tole
Output
Median = 3
Time Complexity: O((N + M) * Log (N + M)), Time required to sort the array of size N + M
Auxiliary Space: O(N + M), Creating a new array of size N+M.
Median of two sorted arrays of different sizes by Merging Arrays efficiently:
The given arrays are sorted, so merge the sorted arrays in an efficient way and keep the count of
elements inserted in the output array or printed form. So when the elements in the output array
are half the original size of the given array print the element as a median element. There are two
cases:
 Case 1: M+N is odd, the median is at (M+N)/2th index in the array obtained after merging
both the arrays.
 Case 2: M+N is even, the median will be the average of elements at index ((M+N)/2 – 1) and
(M+N)/2 in the array obtained after merging both the arrays
Illustration:
Given two array ar1[ ]= { 900 } and ar2[ ] = { 5, 8, 10, 20 } , n => Size of ar1 = 1 and m
=> Size of ar2 = 4
 Loop will run from 0 till 2.
 First iteration : { 900 } { 5, 8, 10, 20 } , m1 = 5
 Second iteration : { 900 } { 5, 8, 10, 20 }, m1 = 8
 Third iteration : { 900 } { 5, 8, 10, 20 }, m1 = 10
 As size of ar1 + ar2 = odd , hence we return m1 = 10 as the median

 C++
 Java
 Python3
 C#
 Javascript
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
import java.io.*;
class GFG {
// Function to calculate median

static int getMedian(int ar1[], int ar2[], int n, int m)
{
// Current index of input array ar1[]

int i = 0;
// Current index of input array ar2[]

int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,

// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,

else {
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements

// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else {
for (count = 0; count <= (n + m) / 2; count++) {
m2 = m1;
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,

else {
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
{
int ar1[] = { 900 };
int ar2[] = { 5, 8, 10, 20 };
int n1 = ar1.length;
int n2 = ar2.length;
System.out.println(getMedian(ar1, ar2, n1, n2));

}
}
// This code is contributed by Yash Singhal

Output
10
Time Complexity: O(M + N). To merge both arrays O(M+N) time is needed.
Auxiliary Space: O(1). No extra space is required.
Median of two sorted arrays of different sizes using Binary Search:
The given two arrays are sorted, so we can utilize the ability of Binary Search to divide the
array and find the median.
Median means the point at which the whole array is divided into two parts. Hence since the two
arrays are not merged so to get the median we require merging which is costly.
Hence instead of merging, we will use a modified binary search algorithm to efficiently find the
median.
Below is the implementation:
 C++
 Java
 Python3
 C#
 Javascript
public class GFG {
// Method to find median

static double Median(int[] A, int[] B)
{
int n = A.length;
int m = B.length;
if (n > m)
return Median(B,
A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {

int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Integer
.MIN_VALUE; // checking overflow
// of indices
int leftB = (leftBsize > 0) ? B[leftBsize - 1]
: Integer.MIN_VALUE;
int rightA = (leftAsize < n)
? A[leftAsize]
: Integer.MAX_VALUE;
int rightB = (leftBsize < m)
? B[leftBsize]
: Integer.MAX_VALUE;
// if correct partition is done

if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0;
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
{
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
System.out.println("Median of the two arrays are");
System.out.println(Median(arr1, arr2));
}
}
// This code is contributed by Hritik

Output
Median of the two arrays are

3
Time Complexity: O(min(log M, log N)): Since binary search is being applied on the smaller of
the 2 arrays
Median of two sorted arrays of different sizes using Priority Queue:
In this Approach we have used Priority Queue (min Heap) to find out the median.
The Idea is simple, just push the elements into a single Priority Queue from both arrays. Now we
have to find median from priority queue by performing a simple traversal through it upto
median.
Illustration:
A[ ] = {-2, 3, 4, 5}, N = 4 & B[ ] = {-4, -1, 7, 8, 9}, M = 5
Step 1: Adding elements to priority queue(pq) from array A
 pq.push(-2)
 pq.push(3)
 pq.push(4)
 pq.push(5)
After adding array A elements to priority queue it will look as pq = {-2, 3, 4, 5}
Step 2: Adding elements to priority queue(pq) from array B
 pq.push(-4)
 pq.push(-1)
 pq.push(7)
 pq.push(8)
 pq.push(9)
After adding array B elements to priority queue it will look as pq = {-4, -2, -1, 3, 4, 5, 7, 8, 9}
Step 3: Now we have to find median from Priority Queue based on following conditions:
 if N+M is odd
 then traverse priority queue upto (n+m)/2 by popping element by element
 Then display median as pq.top()
 if N+M is even
 then traverse priority queue upto (n+m)/2 && ((n+m)/2)-1
 Then median = average of both top values of priority queue
In this case the median is 4
Below is the implementation of the above problem:
 C++
 Java
 Python3
 C#
 Javascript
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;
public class Main {
// Method to find median

public static double Median(Vector<Integer> A,
Vector<Integer> B)
{
int i;
int n = A.size();
int m = B.size();
// initializing Priority Queue (Min Heap)
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
// pushing array A values to priority Queue
for (i = 0; i < n; i++) {
pq.add(A.get(i));
}
// pushing array B values to priority Queue
for (i = 0; i < m; i++) {
pq.add(B.get(i));
}
int check = n + m;
double count = -1;
double mid1 = -1, mid2 = -1;
while (!pq.isEmpty()) {
count++;
// returning mid value if combined length(n+m)
// is odd
if (check % 2 != 0 && count == check / 2) {
double ans = pq.peek();
return ans;
}
// maintaining mid1 value if combined
// length(n+m) is even where we need to maintain
// both mid values in case of even combined
// length
if (check % 2 == 0
&& count == (check / 2) - 1) {
mid1 = pq.peek();
}
// now returning the mid2 value with previous
// maintained mid1 value by 2
if (check % 2 == 0 && count == check / 2) {
mid2 = pq.peek();
double ans = (mid1 + mid2) / 2;
return ans;
}
pq.poll();
}
return 0.00000;
}
// Driver code
{
Vector<Integer> arr1 = new Vector<Integer>();
arr1.add(-2);
arr1.add(3);
arr1.add(4);
arr1.add(5);
Vector<Integer> arr2 = new Vector<Integer>();

arr2.add(-4);
arr2.add(-1);
arr2.add(7);
arr2.add(8);
arr2.add(9);
System.out.println("Median of the two arrays are");

System.out.println(Median(arr1, arr2));
}
}
Output
Median of the two arrays are
4
Time Complexity: O((n + m) log(n + m)), Since the priority queue is implemented from two
arrays
Auxiliary Space: O(N+M): for storing two array values in the priority queue.
2. Matrix:
A matrix is a two-dimensional array of elements, arranged in rows and columns. It is represented
as a rectangular grid, with each element at the intersection of a row and column.
Important articles on Matrix:
 Search in a row wise and column wise sorted matrix
 Print a given matrix in spiral form
 A Boolean Matrix Question
 Print unique rows in a given boolean matrix
 Maximum size square sub-matrix with all 1s
 Print unique rows in a given boolean matrix
 Inplace M x N size matrix transpose | Updated
 Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
 Strassen’s Matrix Multiplication
 Create a matrix with alternating rectangles of O and X
 Print all elements in sorted order from row and column wise sorted matrix
 Given an n x n square matrix, find sum of all sub-squares of size k x k
 Count number of islands where every island is row-wise and column-wise separated
 Find a common element in all rows of a given row-wise sorted matrix
3. Linked List:
A linear data structure where elements are stored in nodes linked together by pointers. Each node
contains the data and a pointer to the next node in the list. Linked lists are efficient
for inserting and deleting elements, but they can be slower for accessing elements than arrays.
Types of Linked List:

a) Singly Linked List: Each node points to the next node in the list.
Important articles on Singly Linked Lis:
 Introduction to Linked List
 Linked List vs Array
 Linked List Insertion
 Linked List Deletion (Deleting a given key)
 Linked List Deletion (Deleting a key at given position)
 A Programmer’s approach of looking at Array vs. Linked List
 Find Length of a Linked List (Iterative and Recursive)
 How to write C functions that modify head pointer of a Linked List?
 Swap nodes in a linked list without swapping data
 Reverse a linked list
 Merge two sorted linked lists
 Merge Sort for Linked Lists
 Reverse a Linked List in groups of given size
 Detect and Remove Loop in a Linked List
 Add two numbers represented by linked lists | Set 1
 Rotate a Linked List
 Generic Linked List in C
b) Circular Linked List: The last node points back to the first node, forming a circular loop.
Important articles on Circular Linked List:
 Circular Linked List Introduction and Applications,
 Circular Singly Linked List Insertion
 Circular Linked List Traversal
 Split a Circular Linked List into two halves
 Sorted insert for circular linked list
c) Doubly Linked List: Each node points to both the next and previous nodes in the list.
Important articles on Doubly Linked List:
 Doubly Linked List Introduction and Insertion
 Delete a node in a Doubly Linked List
 Reverse a Doubly Linked List
 The Great Tree-List Recursion Problem.
 QuickSort on Doubly Linked List
 Merge Sort for Doubly Linked List
4. Stack:
Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last
Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the
element that is inserted first, comes out last.
Important articles on Stack:
 Introduction to Stack
 Infix to Postfix Conversion using Stack
 Evaluation of Postfix Expression
 Reverse a String using Stack
 Implement two stacks in an array
 Check for balanced parentheses in an expression
 Next Greater Element
 Reverse a stack using recursion
 Sort a stack using recursion
 The Stock Span Problem
 Design and Implement Special Stack Data Structure
 Implement Stack using Queues
 Design a stack with operations on middle element
 How to efficiently implement k stacks in a single array?
 Sort a stack using recursion
5. Queue:
A Queue Data Structure is a fundamental concept in computer science used for storing and
managing data in a specific order. It follows the principle of “First in, First out” (FIFO), where
the first element added to the queue is the first one to be removed
Important articles on Queue:

 Queue Introduction and Array Implementation
 Linked List Implementation of Queue
 Applications of Queue Data Structure
 Priority Queue Introduction
 Deque (Introduction and Applications)
 Implementation of Deque using circular array
 Implement Queue using Stacks
 Find the first circular tour that visits all petrol pumps
 Maximum of all subarrays of size k
 An Interesting Method to Generate Binary Numbers from 1 to n
 How to efficiently implement k Queues in a single array?
6. Binary Tree:
Binary Tree is a hierarchical data structure where each node has at most two child nodes, referred
to as the left child and the right child. Binary trees are mostly used to represent hierarchical data,
such as file systems or family trees.
Important articles on Binary Tree:

 Binary Tree Introduction
 Binary Tree Properties
 Types of Binary Tree
 Handshaking Lemma and Interesting Tree Properties
 Enumeration of Binary Tree
 Applications of tree data structure
 Tree Traversals
 BFS vs DFS for Binary Tree
 Level Order Tree Traversal
 Diameter of a Binary Tree
 Inorder Tree Traversal without Recursion
 Inorder Tree Traversal without recursion and without stack!
 Threaded Binary Tree
 Maximum Depth or Height of a Tree
 If you are given two traversal sequences, can you construct the binary tree?
 Clone a Binary Tree with Random Pointers
 Construct Tree from given Inorder and Preorder traversals
 Maximum width of a binary tree
 Print nodes at k distance from root
 Print Ancestors of a given node in Binary Tree
 Check if a binary tree is subtree of another binary tree
 Connect nodes at same level
7. Binary Search Tree:

A Binary Search Tree is a data structure used for storing data in a sorted manner. Each node in
a Binary Search Tree has at most two children, a left child and a right child, with the left child
containing values less than the parent node and the right child containing values greater than the
parent node. This hierarchical structure allows for efficient searching, insertion, and deletion
operations on the data stored in the tree.
Important articles on Binary Search Tree:

 Search and Insert in BST
 Deletion from BST
 Minimum value in a Binary Search Tree
 Inorder predecessor and successor for a given key in BST
 Check if a binary tree is BST or not
 Lowest Common Ancestor in a Binary Search Tree.
 Inorder Successor in Binary Search Tree
 Find k-th smallest element in BST (Order Statistics in BST)
 Merge two BSTs with limited extra space
 Two nodes of a BST are swapped, correct the BST
 Floor and Ceil from a BST
 In-place conversion of Sorted DLL to Balanced BST
 Find a pair with given sum in a Balanced BST
 Total number of possible Binary Search Trees with n keys
 Merge Two Balanced Binary Search Trees
 Binary Tree to Binary Search Tree Conversion
8. Heap:
A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the
value of its children is less than or equal to its own value. Heaps are usually used to
implement priority queues, where the smallest (or largest) element is always at the root of the
tree.
Important articles on Heap:

 Binary Heap
 Why is Binary Heap Preferred over BST for Priority Queue?
 Heap Sort
 K’th Largest Element in an array
 Sort an almost sorted array
 Binomial Heap
 Fibonacci Heap
 Tournament Tree (Winner Tree) and Binary Heap
9. Hashing:
Hashing is a technique that generates a fixed-size output (hash value) from an input of variable
size using mathematical formulas called hash functions. Hashing is used to determine an index or
location for storing an item in a data structure, allowing for efficient retrieval and insertion.
Important articles on Hashing:

 Hashing Introduction
 Separate Chaining for Collision Handling
 Open Addressing for Collision Handling
 Print a Binary Tree in Vertical Order
 Find whether an array is subset of another array
 Union and Intersection of two Linked Lists
 Find a pair with given sum
 Check if a given array contains duplicate elements within k distance from each other
 Find Itinerary from a given list of tickets
 Find number of Employees Under every Employee
10. Graph:
Graph is a collection of nodes connected by edges. Graphs are mostly used to represent networks,
such as social networks or transportation networks.
Important articles on Graph:

 Graph and its representations
 Breadth First Traversal for a Graph
 Depth First Traversal for a Graph
 Applications of Depth First Search
 Applications of Breadth First Traversal
 Detect Cycle in a Directed Graph
 Detect Cycle in Graph using DSU
 Detect cycle in an Undirected Graph using DFS
 Longest Path in a Directed Acyclic Graph
 Topological Sorting
 Check whether a given graph is Bipartite or not
 Snake and Ladder Problem
 Minimize Cash Flow among a given set of friends who have borrowed money from each
other
 Boggle (Find all possible words in a board of characters)
 Assign directions to edges so that the directed graph remains acyclic

Data Structures - Lecture - 2

Uploaded by

Copyright:

Available Formats

Data Structures - Lecture - 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structures - Lecture - 2

Uploaded by

Copyright:

Available Formats

Lecture – 2

1.2 Data Structure

1.3 Why are Data Structures Important?

1.6 Applications of Data Structures

Learn Basics of Data Structure:

1.7 Introduction to Linear Data Structures

1.7.1 Linear data structure

Here, we have briefly explained every linear data type below:

Escalator is one of the best real-life examples of the queue.

1.7.2 Non-linear data structure?

Types of the graph:

The above-explained data structures are fundamental data structures.

Difference between linear data structure and non-linear data structure

Linear data structure Non-linear data structure

The linear relationship is present between Data elements have a hierarchical

We can traverse it in a single run as it is We can't traverse it in a single run as it is a

It is a single-level data structure. It is a multi-level data structure.

The utilization of memory is not efficient. Memory utilization is efficient.

Time complexity increases if we need to Time complexity doesn't change much if we

All Social networks, telephone networks,

Example: Graph, map, tree, heap data

1.8 Introduction to Hierarchical Data Structure

Binary Tree Properties:

Basic Operation On Binary Tree:

Applications of Binary Tree:

Binary Tree Traversals:

b. Binary Search Tree

Binary Search Tree Declaration

Since it is a Binary Tree, its declaration is similar to the Binary Tree.

Primary BST Operations:

Auxiliary BST Operations:

Here is the algorithm to implement a binary heap:

Why the Need for Hashing:

A good hash function should have the following properties:

// initialize a variable to store the hash value

// loop over each character in the input string

// return the hash value modulo some large prime

// Print the hash value

A good hash function should have following properties:

Adjacency Matrix Representation of the above graph

Time Complexities in case of Adjacency Matrix :

Time Complexities in case of Adjacency List :

The leaf nodes are in blue.

Insert time : O(M) where M is the length of the string.

Construction of segment tree : O(N)

 Represent complex relationships: Graphs can be used to represent complex

 Fast search and retrieval of strings

 Can have a high memory overhead for large datasets

 Efficient range queries and updates

 Can require significant memory overhead

 Fast string search and pattern matching

 Can have a high memory overhead

1.10 Abstract Data Types -Most Popular Data Structures:

Below are some most popular Data Structure:

Search, Insert, and Delete in an Unsorted Array | Array Operations

// C++ program to implement linear

// Function to implement search operation

// If the key is not found

// Using a last element as search element