Data Structures and Algorithms (DSA) - Concepts & Interview Questions

Table of Contents

Introduction to DSA

No.	Questions
1	What is Data Structure?
2	How is Data Organized in Memory?
3	Stack vs Heap Memory
4	Types of Data Structures
5	Time and Space Complexity

Array Representations

No.	Questions
1	What is an Array?
2	What are Dynamic Arrays?
3	What are Static Arrays?
4	What is a 2D Array?
5	What defines the Dimensionality of an array?
6	Advantages and Disadvantages of Arrays

Array as ADT (Abstract Data Type)

No.	Questions
1	What does it mean by Array ADT?
2	How to Add / Append?
3	How to Insert?
4	How to Delete?
5	How to Search?
6	What is Linear Search?
7	How to improve Linear Search (Move to Head / Move to Front)?
8	What is Binary Search?
9	Difference between Linear and Binary Search?
10	How to Get, Set, Find Min - Max?
11	How to Reverse and Shift an Array?
12	Left Shift / Rotation?
13	Right Shift / Rotation?
14	Insert into Sorted Array?
15	Check if an Array is Sorted?
16	Arranging Negative Numbers on Left Side?
17	Merge Arrays?
18	Set Operations (Union, Intersection, Difference)?
19	Find Missing Element (Single Missing, Multiple Missing)?
20	Find Duplicate Elements?
21	Finding a Pair with Sum K?
22	Reverse an Array?
23	Find Two Elements with Difference Equal to S in a Sorted Array?
24	Finding Minimum and Maximum in a Single Scan?
25	Find Array Elements that are Neither Minimum nor Maximum?
26	Find 2nd Maximum or Minimum Element?
27	Find Elements in Range (0-100) with Frequency > 50

Strings

No.	Questions
1	What is character set?
2	What is the ASCII of strings?
3	What is string?
4	Difference b/w character set and strings?
5	How to find Length of string?
6	How to change case of strings?
7	How to count words, vowels and consonants in a string?
8	How to validate a string?
9	How to reverse a string?
10	How to compare strings and check palindrome?
11	How to find duplicates in strings?
12	How to apply bitwise operations?
13	How to check if strings are anagram?
14	How to find permutation of strings?

Recursion

No.	Questions
1.	What is Recursion?
2.	How Recursion Works?
3.	What are the Advantages & Disadvantages of Recursion?
4.	How to Trace Recursive Functions?
5.	What are the Phases of Recursion?
6.	What is the Difference Between Recursion and Loop?
7.	How Recursion Uses Stack?
8.	What are the Types of Recursion?
9.	What is the Time Complexity of Recursion (Tree vs Recurrence Relation)?
10.	What are the Steps to Solve Recursive Problems?
11.	How to find the Sum of First N Natural Numbers?
12.	How to find the Factorial of a Number?
13.	How to find the Power of a Number (m^n)?
14.	How to find the Taylor Series?
15.	How to find the Fibonacci Series (Excessive Recursion and Memoization)?
16.	How to find ⁿCɾ Combination or Selection Formula?
17.	How to Solve the Tower of Hanoi Problem?
18.	How to find the Number of Ways in an n X m Matrix?

Linked List

No.	Questions
1.	What is a Linked List?
2.	How Does a Linked List Work?
3.	What is a Self-Referential Structure?
4.	Understanding Node Structure
5.	What are the Common Conditions in a Linked List?
6.	How to Create a Linked List
7.	How to Display a Linked List
8.	How to Reverse Display a Linked List
9.	What is the Time Complexity of Linked List Operations?
10.	How to Count Nodes in a Linked List
11.	How to Find the Sum of Elements in a Linked List
12.	How to Find the Maximum Element in a Linked List
13.	How to Apply Linear Search in a Linked List
14.	What is Move to Head in a Linked List?
15.	What is Move to Transposition?
16.	How to Insert a Node in a Linked List
17.	How to Delete a Node in a Linked List
18.	How to Check if a List is sorted or not
19.	How to Remove Duplicates from Linked List
20.	How to Reverse a Linked List
21.	How to Concatenate Linked Lists
22.	How to Merge Linked Lists
23	How to Find the Middle of a Linked List
24.	How to Detect and Remove a Loop in a Linked List

Circular Linked List

No.	Questions
1.	What is a Circular Linked List?
2.	What are the conditions for a Circular Linked List?
3.	What are the benefits of a Circular Linked List over a Singly Linked List?
4.	How to create a Circular Linked List?
5.	How to display a Circular Linked List?
6.	How to insert a node in a Circular Linked List?
7.	How to delete a node from a Circular Linked List?

Doubly Linked List

No.	Questions
1.	What is a Doubly Linked List?
2.	What are the benefits of a Doubly Linked List over a Singly or Circular Linked List?
3.	How to create a Doubly Linked List?
4.	How to display a Doubly Linked List?
5.	How to insert a node in a Doubly Linked List?
6.	How to delete a node from a Doubly Linked List?
7.	How to reverse a Doubly Linked List?

Circular Doubly Linked List

No.	Questions
1.	What is a Circular Doubly Linked List?
2.	What are the benefits of a Circular Doubly Linked List over Singly, Circular, and Doubly Linked Lists?
3.	What are the conditions for a Circular Doubly Linked List?
4.	How to create a Circular Doubly Linked List?
5.	How to display a Circular Doubly Linked List?

No.	Questions
1.	Give a Brief Comparison of Linked List Types
2.	Comparison of Linked List with Array
3.	How to find the intersection point of two Linked Lists?

Stack

No.	Questions
1.	What is Stack?
2.	What is ADT with Stack?
3.	What are the benefits of Stack over Array and Linked List?
4.	How to implement Stack using Array?
5.	How to implement Stack using Linked List?
6.	How to solve Parenthesis Matching problem using Stack?
7.	How to check balance with conditions of matching brackets?
8.	How to perform Infix to Postfix Conversion using Stack?

Queue

No.	Questions
1.	What is Queue?
2.	What is ADT in Queue?
3.	What are the benefits of Queue over Array, Linked List, and Stack?
4.	How to implement Queue using Array?
5.	What are the drawbacks of Queue?
6.	What is Circular Queue?
7.	How to implement Queue using Linked List?

DEQueue (Double Ended Queue)

No.	Questions
1.	What is DEQueue?
2.	What are the Restrictions in DEQueue?

Priority Queues

No.	Questions
1.	What is Priority Queue?
2.	What does it mean by Limited Set of Priorities?
3.	What does it mean by Element Priority? Explain methods.

No.	Questions
1.	How to Implement Queue using 2 Stacks

Trees

No.	Question
1.	What is a Tree?
2.	What are the terminologies in a tree?
2.1.	What is the Root Node?
2.2.	What are Edges in a Tree?
2.3.	What is a Parent and Child Node?
2.4.	What are Siblings in a Tree?
2.5.	What is a Subtree?
2.6.	What are Descendants in a Tree?
2.7.	What are Ancestors in a Tree?
2.8.	What is the Degree of a Node?
2.9.	What is the Degree of a Tree?
2.10.	What is a Leaf Node (External Node)?
2.11.	What is an Internal Node (Non-Leaf Node)?
2.12.	What is Level in a Tree?
2.13.	What is the Height of a Tree?
2.14.	What is a Forest in Tree Data Structures?
2.15.	What is the Maximum Number of Nodes in a Tree?
3.	What is a Binary Tree?
4.	How to find Height or Nodes of a Binary Tree if one is given?
5.	What is a Strict Binary Tree?
6.	How to find Height or Nodes of a Strict Binary Tree if one is given?
7.	What are n-ary trees?
8.	What are strict n-ary trees?
9.	How to implement a Binary Tree using an array?
10.	How to implement a Binary Tree using a linked list?
11.	What are the Types of Binary Trees?
11.1.	What is a Full Binary Tree?
11.2.	What is a Complete Binary Tree?
12.	What are the Types/Different Methods of Tree Traversals?
12.1.	What is Preorder Traversal? Explain and provide code for both recursive and iterativees.
12.2.	What is Inorder Traversal? Explain and provide code for both recursive and iterativees.
12.3.	What is Postorder Traversal? Explain and provide code for both recursive and iterativees.
12.4.	What is Level Order Traversal? Explain and provide code for both recursive and iterativees.
13.	How to implement/create a Binary Tree?
14.	How to generate a Tree from Traversal?
15.	How to Count Total Nodes, Nodes with Data, Full Nodes, Nodes with One or Two Children, Leaf Nodes, and Nodes with Exactly One Child in a Tree?

Binary Search Tree (BST)

No.	Question
1.	What is Binary Search Tree (BST)?
2.	What are the Key Properties of a Binary Search Tree (BST)?
3.	How to Search in a BST? Explain and provide code for both recursive and iterative approaches.
4.	How to Insert in a BST? Explain and provide code for both recursive and iterative approaches.
5.	How to Delete a Node in a BST? Explain and provide code for both recursive and iterative approaches. Also, explain what a Predecessor and Successor are.
6.	How to Construct a BST from a Given Preorder Traversal?
7.	What are the Drawbacks of BST and How Can They Be Solved?

AVL Trees

No.	Question
1.	What is AVL Tree?
2.	How to Balance AVL Trees?
3.	What are the Types of Rotations Used for Balancing AVL Trees?
3.1	LL (Left-Left) Rotation
3.2	RR (Right-Right) Rotation
3.3	LR (Left-Right) Rotation
3.4	RL (Right-Left) Rotation
4.	How to Perform Deletion in AVL Tree?
5.	How to Find Height or Nodes of an AVL Tree?
6.	Comparison of AVL Trees and BSTs: Benefits Over BSTs
7.	What are the Applications of AVL Trees: When Are They Preferred?

Binary Heap

No.	Question
1.	What is Binary Heap? What are its Characteristics?
2.	Which is the Preferred Way to Implement Binary Heap?
3.	How to Implement Binary Heap Using an Array?
4.	How to Perform Operations on Binary Heap?
5.	Explain the Concept of Heapify Process
6.	What is Binary Heap as a Priority Queue?

Sorting Techniques

No.	Question
1.	What are Sorting Techniques?
2.	What are the Criteria for Analyzing a Sorting Algorithm?
3.	What are the Different Types of Sorting Algorithms? (Comparison-Based and Index-Based)
4.	What is Bubble Sort? Explain with an Example.
5.	What is Insertion Sort? Explain with an Example.
6.	What is the Difference between Bubble Sort and Insertion Sort
7.	What is Selection Sort? Explain with an Example.
8.	What is Quick Sort? Explain with an Example.
9.	What is the Difference between Selection Sort and Quick Sort
10.	What is Merge Sort? Explain and Provide Code for Both Recursive and Iterativees.
11.	What is Counting Sort? Explain with an Example.
12.	What is Bucket/Bin Sort? Explain with an Example.
13.	What is Radix Sort? Explain with an Example.
14.	What is Shell Sort? Explain with an Example.

Hashing Techniques

No.	Question
1.	What is Hashing?
2.	Why is Hashing Useful for Searching?
3.	How Does Hashing Work?
4.	What are the Different Types of Mappings in Hashing?
5.	What is a Hash Collision?
6.	What are the Methods for Resolving Hash Collisions?
7.	What is Chaining in Hashing? (With Analysis)
8.	What is Linear Probing? (With Analysis)
9.	What is Quadratic Probing? (With Analysis)
10.	What is Double Hashing?
11.	Comparison: Linear Probing vs. Quadratic Probing vs. Double Hashing
12.	What are Hash Functions?
13.	What are the Different Types of Hash Functions?

STL (Standard Template Library)

No.	Topic
1.	What is STL?
2.	Why Use STL?
3.	When to Use Which STL Container?
4.	Main Components of STL
5.	Pairs
6.	Vectors
7.	Lists
8.	Deques
9.	Stack (LIFO)
10.	Queue (FIFO)
11.	Priority Queue
12.	Set
13.	Multiset
14.	Unordered Set
15.	Map
16.	Multimap
17.	Unordered Map
18.	Algorithms

Introduction to DSA

What is Data Structure? 📂

A Data Structure is a way of organizing and storing data in memory during program execution.
It allows efficient storage, retrieval, and manipulation of data.
Data structures use algorithms to structure data efficiently in memory.

⬆ Back to Top

How is Data Organized in Memory?

The way data is stored in main memory for efficient access is called a Data Structure. Memory is divided into three main sections:

Code Section 🖥️
- Contains the program's executable instructions.
- Execution starts from this section.
Stack Section 📌
- Stores function calls and local variables.
- Uses Last In, First Out (LIFO) order.
- Memory is statically allocated and automatically managed.
Heap Section 📂
- Stores dynamically allocated memory (e.g., malloc() in C or new in C++/Java).
- Accessed via pointers.
- Memory needs to be manually managed (deallocation required).

⬆ Back to Top

Stack vs Heap Memory

Feature 🔥	Stack Memory 📌	Heap Memory 📂
Allocation	Static	Dynamic
Access Speed	Faster	Slower
Size	Limited	Large
Lifetime	Auto-managed	Manually managed (deallocation required)
Usage	Function calls, local variables	Dynamic objects, large data structures

The stack is efficient but limited in size.
The heap is flexible but requires proper memory management.

⬆ Back to Top

🤷‍♂️ Types of Data Structures

Physical Data Structures

Define how data is stored in memory.
- Array: Fixed size, used when the max size is known.
- Linked List: Dynamic, stored in heap, suitable when size is unknown.

Logical Data Structures

Define data operations like searching & sorting.
- Stack: Last In, First Out (LIFO)
- Queue: First In, First Out (FIFO)
- Tree & Graph: Non-linear structures
- Hash Table: Key-value pairs for quick lookup

⬆ Back to Top

Time and Space Complexity

⏳ Time Complexity

Measures algorithm efficiency as input size increases.
Ignoring constants: O(n + 1) → O(n).
Common complexities:
- O(1): Constant time (random access in an array).
- O(log n): Logarithmic time (Binary Search).
- O(n): Linear time (Loop through an array).
- O(n log n): Quasi-linear (Merge Sort, Quick Sort).
- O(n²): Quadratic time (Bubble Sort, Insertion Sort).

🗄️ Space Complexity

Determines memory usage based on input size.
Includes auxiliary space (extra space required apart from input data).

⬆ Back to Top

⏱️ Quick Guide to Measuring Time Complexity

1. Loop-Based Patterns

Pattern	Code Example	Time Complexity
Single Loop	`for (int i = 0; i < n; i++)`	O(n)
Nested Loops	`for (int i = 0; i < n; i++)` `for (int j = 0; j < n; j++)`	O(n²)
Triple Nested Loops	`for (int i = 0; i < n; i++)` `for (int j = 0; j < n; j++)` `for (int k = 0; k < n; k++)`	O(n³)
Loop with Increment (`i *= 2`)	`for (int i = 1; i < n; i *= 2)`	O(log n)
Loop with Decrement (`i /= 2`)	`for (int i = n; i > 0; i /= 2)`	O(log n)

2. Recursive Patterns

Pattern	Recurrence Relation	Time Complexity
Linear Recursion	`T(n) = T(n-1) + O(1)`	O(n)
Binary Recursion	`T(n) = 2T(n/2) + O(1)`	O(n)
Divide & Conquer (Merge Sort, Quick Sort Worst Case)	`T(n) = 2T(n/2) + O(n)`	O(n log n)
Exponential Recursion (Fibonacci, Brute Force DFS)	`T(n) = T(n-1) + T(n-2)`	O(2ⁿ)

3. Divide and Conquer Patterns

Algorithm	Recurrence	Complexity
Binary Search	`T(n) = T(n/2) + O(1)`	O(log n)
Merge Sort	`T(n) = 2T(n/2) + O(n)`	O(n log n)
Quick Sort (Best & Avg)	`T(n) = T(n/2) + O(n)`	O(n log n)
Quick Sort (Worst Case - sorted array)	`T(n) = T(n-1) + O(n)`	O(n²)

4. Dynamic Programming Patterns

Pattern	Example	Time Complexity
Memoization (Top-Down Recursion with Cache)	Fibonacci DP	O(n)
Bottom-Up Iterative DP	Knapsack, LIS	O(n²) or O(n³)
Matrix Chain Multiplication	`T(n) = O(n³)`	O(n³)

5. Graph Algorithms

Algorithm	Complexity
BFS / DFS (Adjacency List)	O(V + E)
Dijkstra (Min Heap)	O((V + E) log V)
Bellman-Ford	O(VE)
Floyd Warshall (All-Pairs Shortest Path)	O(V³)
Prim’s / Kruskal’s MST	O(E log V)

6. Sorting Algorithms

Algorithm	Best Case	Worst Case
Bubble Sort / Insertion Sort	O(n)	O(n²)
Merge Sort	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n²)
Heap Sort	O(n log n)	O(n log n)

7. Logarithmic and Amortized Complexities

Pattern	Example	Complexity
Binary Search	Search in sorted array	O(log n)
Heap Operations (Insert/Delete)	Priority Queue, Dijkstra	O(log n)
Balanced BST (Insertion, Deletion, Search)	AVL, Red-Black Tree	O(log n)
Union-Find (Path Compression & Rank)	DSU operations	O(α(n)) (inverse Ackermann)

8. Special Cases

Case	Example
Iterating All Subsets	O(2ⁿ)
Iterating All Permutations	O(n!)
Brute Force Checking All Pairs	O(n²)

💾 Quick Guide to Calculating Space Complexity

1. What is Space Complexity?

Space Complexity is the total memory required by a program to execute. It includes:

Fixed Part – Independent of input size (e.g., code, static/global variables, constants).
Variable Part – Depends on input size (e.g., dynamic memory allocation, function call stack, recursion depth).

2. Components of Space Complexity

a) Fixed Memory (O(1))

Code Space: Memory occupied by compiled instructions.
Constant Space: Fixed-size variables, constants.
Global & Static Variables: Memory allocated at program startup, remains till termination.

b) Variable Memory (Depends on Input)

Stack Space: Used for function calls (parameters, return addresses, local variables).
Heap Space: Memory dynamically allocated using new in Java/C++, malloc() in C.
Data Structures: Arrays, lists, trees, hash tables, etc.

3. Steps to Calculate Space Complexity

Step 1: Analyze Fixed Space

int a = 10, b = 20; // Fixed space O(1)

Step 2: Analyze Variable Space

int[] arr = new int[n]; // Takes O(n) space

Step 3: Analyze Function Calls & Stack Usage

void recursive(int n) {
    if (n == 0) return;
    recursive(n - 1);
} // O(n) stack space

Step 4: Consider Auxiliary Space

int[] newArray = new int[n]; // O(n) auxiliary space

4. Space Complexity Analysis for Common Data Structures

Data Structure	Space Complexity
Array (1D)	O(n)
2D Array	O(n²)
Linked List	O(n)
HashMap	O(n)
Tree (Balanced)	O(n)
Graph (Adjacency List)	O(V + E)
Stack (n elements)	O(n)
Queue (n elements)	O(n)

5. Space Complexity of Common Algorithms

Iterative Algorithm (O(1))

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
} // O(1) space

Recursive Algorithm (O(n))

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
} // O(n) stack space

Sorting Algorithms

Algorithm	Auxiliary Space
Bubble Sort	O(1)
Merge Sort	O(n)
Quick Sort (in-place)	O(log n)
Heap Sort	O(1)

6. Best Practices for Optimizing Space Complexity

Use In-Place Algorithms
Use Iteration Instead of Recursion
Choose Space-Efficient Data Structures
Free Memory When Not Needed

⬆ Back to Top

Array Representations

What is an Array?

Array is like a container that is use to store some kind of data or collection of elements.
It is a linear data structure. And have contiguous memory locations.
It allows easy access to elements using an index.
Example:
```
int arr[5] = {1, 2, 3, 4, 5};
```

⬆ Back to Top

What are Dynamic Arrays?

A dynamic array can change its size during runtime.
It is implemented using pointers and memory allocation functions like new in C++.
Can grow or shrink during runtime using new and delete.
```
int *arr = new int[10];
```

#include<iostream>
using namespace std;

int main(){
    int *arr = new int[5];
    for(int i = 0; i < 5; i++){
        cout << "Enter " << i + 1 << " element: ";
        cin >> arr[i];
    }
    delete[] arr;
}

⬆ Back to Top

What are Static Arrays?

A static array has a fixed size determined at compile time.
Fixed-size memory allocation.
Cannot grow or shrink dynamically.
```
int arr[10];
```

⬆ Back to Top

#include<iostream>
using namespace std;

int main(){
    int *a = new int[5];

    for(int i = 0; i < 5; i++){
        cout << "Enter " << i + 1 << " element: ";
        cin >> a[i];
    }

    char i;
    cout << "Do you want to increase the size of array? (Y/N): ";
    cin >> i;

    if(i == 'Y'){
        int num;
        cout << "\nEnter number of elements you want to add: ";
        cin >> num;

        int *b = new int[5 + num];

        for(int i = 0; i < 5; i++){
            b[i] = a[i];
        }

        for(int i = 5; i < 5 + num; i++){
            cout << "Enter " << i + 1 << " element: ";
            cin >> b[i];
        }

        delete[] a;
        a = b;
        b = nullptr;

        for(int i = 0; i < 5 + num; i++){
            cout << a[i] << " ";
        }
    }else{
        for(int i = 0; i < 5; i++){
            cout << a[i] << " ";
        }
    }

    delete[] a;
}

Advantages and Disadvantages of Arrays

Advantages	Disadvantages
Fast access to elements using an index.	Fixed size (static arrays) cannot be resized.
Efficient memory usage for storing similar data.	Insertion and deletion are costly due to shifting.
Easier to traverse using loops.	-

⬆ Back to Top

What is a 2D Array?

A 2D array represents data in a tabular format with rows and columns.
Commonly used to implement matrices.
Accessed using two indices (one for row and one for column).

int matrix[3][3] = {
      {1, 2, 3},
      {4, 5, 6},
      {7, 8, 9}
  };

⬆ Back to Top

What defines the Dimensionality of an Array?

The number of indices needed to access an element defines the dimensionality of an array.
Example:
- 1D Array: arr[5]
- 2D Array: arr[3][3]
- 3D Array: arr[3][3][3]

⬆ Back to Top

Methods/Ways of Declaring 2D Arrays

1. Normal Declaration

Memory will be created like a single dimension array , but compiler will allow us to access that array as a 2D arrays with rows and columns.

int A[3][4] = {
    {1,2,3,4},
    {2,4,6,8},
    {3,5,7,9}
};

2. Array of Pointers

The pointer will be created inside heap memory and through that we can access , initialise and declare all the elements inside the array. This is array of arrays.

int *A[3];
A[0] = new int[4];
A[1] = new int[4];
A[2] = new int[4];

int row, col;
cout << "Number of rows, col: ";
cin >> row >> col;
int *A[row];
for(int i = 0; i < row; i++){
    A[i] = new int[col];
}

for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
        cout << "Enter A[" << i << "][" << j << "] element: ";
        cin >> A[i][j];
    }
}

for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
        cout << A[i][j] << " ";
    }
    cout << endl;
}

for(int i = 0; i < row; i++){
    delete[] A[i];
}

delete[] A;

3. Double Pointer Method

Almost everything is inside the heap pointer.
The pointer acts like a variable; there is no new operator for it, so it is created inside the stack.

int **A;
A = new int*[3];
for(int i = 0; i < 3; i++){
    A[i] = new int[4];
}

int **A;
    A = new int*[3]; // Allocating memory for 3 rows
    for(int i = 0; i < 3; i++){
        A[i] = new int[4]; // Allocating memory for 4 columns in each row
    }

    // Example usage: Assigning values
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 4; j++){
            A[i][j] = (i + 1) * (j + 1); // Sample values
        }
    }

    // Displaying the 2D array
    cout << "2D Array Elements:\n";
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 4; j++){
            cout << A[i][j] << " ";
        }
        cout << endl;
    }

    // Freeing allocated memory
    for(int i = 0; i < 3; i++){
        delete[] A[i]; // Deleting columns
    }
    delete[] A; // Deleting row pointers

⬆ Back to Top

Array as ADT (Abstract Data Type)

What is Array ADT?

An Array ADT (Abstract Data Type) consists of:

Data Representation (handled by the compiler)
Operations on Data (defined by the program)

Key Components of Array ADT:

Data:
- Array space → Memory allocated for the array.
- Size → Total allocated memory.
- Length → Number of elements currently stored.
Operations:
- Display() → Show all elements.
- Add(x) / Append(x) → Add an element at the end.
- Insert(index, x) → Insert an element at a specific position.
- Delete(index) → Remove an element.
- Search(x) → Find an element.
- Get(index) → Retrieve an element at a specific position.
- Set(index, x) → Update an element.
- Max / Min → Find the maximum or minimum element.
- Reverse → Reverse the array.
- Shift / Rotate → Move elements left or right.
size = 10, but only length = 5 elements are used in an array.
This means 5 slots are empty but allocated in memory.

⬆ Back to Top

How to Add / Append?

Adding or appending means inserting an element at the end of an array.

The new element is stored at the next available index.
The time complexity is O(1) (constant time) since we are adding at the end.

arr[length] = x;  // Insert element at the next index
length++;         // Increase the length of the array

⬆ Back to Top

How to Insert?

Insertion means adding an element at a specific index in the array.

Time Complexity:

Best case (O(1)) → When inserting at the end.
Worst case (O(n)) → When inserting at the beginning (as elements need to be shifted).

#include <iostream>
using namespace std;

class Arr {
    private:
        int *A;
        int length;
        int size;

    public:
        Arr(int size) {
            this->size = size;
            A = new int[size];
            length = 0;
        }

        void insert(int num) {
            if (length < size) {
                A[length] = num;
                length++;
            } else {
                cout << "Array is full!" << endl;
            }
        }

        void add(int index, int num) {
            if (index < 0 || index > length) {
                cout << "Invalid index!" << endl;
                return;
            }
            if (length == size) {
                cout << "Array is full!" << endl;
                return;
            }
            for (int i = length; i > index; i--) {
                A[i] = A[i - 1];
            }
            A[index] = num;
            length++;
        }

        void display() {
            for (int i = 0; i < length; i++) {
                cout << A[i] << " ";
            }
            cout << endl;
        }

        ~Arr() {
            delete[] A;
            cout << "Array destroyed" << endl;
        }
};

int main() {
    Arr ar(5);
    ar.insert(1);
    ar.insert(2);
    ar.insert(3);
    ar.insert(5);
    ar.add(3, 4);
    ar.display();
}

⬆ Back to Top

How to Delete?

Deletion means removing an element from a specific index in the array.

Time Complexity:

O(n) → Because elements must be shifted after deletion.

void del(int index) {
    if (index >= 0 && index < length) {
        for (int i = index; i < length - 1; i++) {
            A[i] = A[i + 1];
        }
        length--;
    }
}

⬆ Back to Top

How to Search?

Searching involves finding an element in an array. The two main searching techniques are:

Linear Search → Works on both sorted and unsorted arrays.
Binary Search → Works only on sorted arrays for faster searching.

⬆ Back to Top

What is Linear Search?

Linear search is a simple searching algorithm where we traverse the array element by element until we find the key.
If we find the element in the array, we return its index; otherwise, we return -1 to indicate it is not present.
The value we are searching for is called the key.

Time Complexity

Best case time complexity: O(1) (when the key is found at the first position).
Worst case time complexity: O(n) (when the key is at the last position or not present at all).

#include <iostream>
using namespace std;

int search(int arr[], int size, int key) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == key) {
            return i; // Return index if found
        }
    }
    return -1; // Return -1 if not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 30;

    int result = search(arr, size, key);
    if (result != -1)
        cout << "Element found at index: " << result << endl;
    else
        cout << "Element not found" << endl;

    return 0;
}

⬆ Back to Top

How to Improve Linear Search (Move to Head / Move to Front)?

Optimization Techniques:

1. Transposition:

Move the recently searched element one step forward for faster future access.

2. Move to Front (Move to Head):

Move the frequently searched element to the beginning of the array.

1. Transposition:

In this technique, when we find the element, we swap it with the previous element. This ensures that frequently accessed elements move closer to the start over time.

#include <iostream>
using namespace std;

class Arr {
    public:
        int arr[10] = {1, 3, 5, 7, 9, 10, 8, 6, 4, 2};

        int search(int key) {
            for (int i = 0; i < 10; i++) {
                if (arr[i] == key) {
                    if (i != 0) {
                        swap(&arr[i], &arr[i - 1]);
                        return i - 1;
                    }
                    return i;
                }
            }
            return -1;
        }

        void swap(int *arr1, int *arr2) {
            int temp = *arr2;
            *arr2 = *arr1;
            *arr1 = temp;
        }
};

int main() {
    Arr arr1;
    cout << "Element found at index: " << arr1.search(4) << endl;
}

2. Move to Front (Move to Head)

In this method, whenever an element is found, we swap it with the first element. This ensures that the most frequently searched elements stay at the beginning.

#include <iostream>
using namespace std;

class Arr {
    public:
        int arr[10] = {1, 3, 5, 7, 9, 10, 8, 6, 4, 2};

        int search(int key) {
            for (int i = 0; i < 10; i++) {
                if (arr[i] == key) {
                    if (i != 0) {
                        swap(&arr[i], &arr[0]);
                        return 0;
                    }
                    return i;
                }
            }
            return -1;
        }

        void swap(int *arr1, int *arr2) {
            int temp = *arr2;
            *arr2 = *arr1;
            *arr1 = temp;
        }
};

int main() {
    Arr arr1;
    cout << "Element found at index: " << arr1.search(2) << endl;
}

⬆ Back to Top

What is Binary Search?

Works only on sorted arrays.
Always searches for the middle element and splits the array into two halves.
Time Complexity: O(log n)

Process:

If key == middle element → ✅ Found.
If key < middle element → 🔍 Search in left half.
If key > middle element → 🔍 Search in right half.

// Iterative
#include <iostream>
using namespace std;

class Arr {
    public:
        int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        int search(int key) {
            int l = 0, h = 9;
            int mid;
            while (l <= h) {
                mid = (l + h) / 2;
                if (key == arr[mid])
                    return mid;
                else if (key < arr[mid])
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            return -1;
        }
};

int main() {
    Arr arr1;
    cout << "Element found at index: " << arr1.search(11) << endl;
}

// Recursive
#include <iostream>
using namespace std;

class Arr {
    public:
        int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        int search(int key, int l, int h) {
            if (l <= h) {
                int mid = (l + h) / 2;
                if (key == arr[mid])
                    return mid;
                else if (key < arr[mid])
                    return search(key, l, mid - 1);
                else
                    return search(key, mid + 1, h);
            }
            return -1;
        }
};

int main() {
    Arr arr1;
    cout << "Element found at index: " << arr1.search(10, 0, 9) << endl;
}

Analysis of Binary Search

Time Complexity: `O(log n)`

The complexity is determined by the number of comparisons from tracing the binary tree.

For Successful Search:

Best case: O(1)
Worst case: O(log n)

For Unsuccessful Search:

Always O(log n), whether using recursion or iteration.

Difference Between Linear and Binary Search:

Search Type	Best Case	Worst Case	Works on Sorted Array?
Linear Search	`O(1)`	`O(n)`	Yes (But Complexity is High)
Binary Search	`O(1)`	`O(log n)`	Yes

⬆ Back to Top

How to Get, Set, Find Min - Max?

1. Get(index)

Retrieves the element at the specified index.

int get(int index) {
    if (index >= 0 && index < 10) // Assuming array size is 10
        return arr[index];
    else
        return -1; // Error value for invalid index
}

2. Set(index, value)

Modifies the element at the specified index.

void set(int index, int value) {
    if (index >= 0 && index < 10) // Assuming array size is 10
        arr[index] = value;
}

3. Min()

Finds the minimum value in the array.

Time Complexity: O(n)

int getMin(){
    int min;
    for(int i = 0; i < 9; i++)
        if(arr[i] > arr[i + 1])
            min = arr[i];
    return min;
}

4. Max()

Finds the maximum value in the array.

Time Complexity: O(n)

int getMax(){
    int max = arr[0];
    for(int i = 1; i < 9; i++)
        if(arr[i] > max)
            max = arr[i];
    return max;
}

5. Sum() + Average()

Calculates the sum and average of array elements.

Time Complexity: O(n)

// Iterative
int getAverage(){
    int sum = 0;
    for(int i = 0; i < 10; i++)
        sum += arr[i];
    return (sum / 10);
}

// Recursive
int getAverage(int arr[], int num){
    if(num < 0){
        return 0;
    } else {
        return getAverage(arr, num - 1) + arr[num];
    }
}

⬆ Back to Top

How to Reverse and Shift an Array?

There are two common methods to reverse an array:

1️. Auxiliary Array Method

Create a temporary array.
Copy elements in reverse order.
Copy back to the original array.
Time Complexity: O(2n)

class Arr {
  public:
    int arr1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    void reverse() {
        int arr2[10];

        for(int i = 9, j = 0; i >= 0; i--, j++)
            arr2[j] = arr1[i];

        for(int i = 0; i < 10; i++)
            arr1[i] = arr2[i];

        for(int i = 0; i < 10; i++)
            cout << arr1[i] << " ";
    }
};

int main() {
    Arr arr;
    arr.reverse();
}

2. In-Place Swap Method

Swap elements from the start and end of the array.

Time Complexity: O(n)

#include <iostream>
using namespace std;

class Arr {
  public:
    int arr1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    void reverse() {
        for(int i = 0, j = 9; i < j; i++, j--) {
            int temp = arr1[j];
            arr1[j] = arr1[i];
            arr1[i] = temp;
        }

        for(int i = 0; i < 10; i++)
            cout << arr1[i] << " ";
    }
};

int main() {
    Arr arr;
    arr.reverse();
}

⬆ Back to Top

Left Shift / Rotation?

Move elements one position left.

The first element moves to the last position.
Used in image sliders and circular queues.
Time Complexity: O(n)

#include <iostream>
using namespace std;

class Arr {
  public:
    int A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    void rotate() {
        int temp = A[0];
        for (int i = 0; i < 9; i++) {
            A[i] = A[i + 1];
        }
        A[9] = temp;

        for (int i = 0; i < 10; i++)
            cout << A[i] << " ";
    }
};

int main() {
    Arr A;
    A.rotate();
}

⬆ Back to Top

Right Shift / Rotation?

Move elements one position right.

The last element moves to the first position.
Time Complexity: O(n)

#include <iostream>
using namespace std;

class Arr {
  public:
    int A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    void rotate() {
        int temp = A[9];
        for (int i = 9; i > 0; i--) {
            A[i] = A[i - 1];
        }
        A[0] = temp;

        for (int i = 0; i < 10; i++)
            cout << A[i] << " ";
    }
};

int main() {
    Arr A;
    A.rotate();
}

⬆ Back to Top

Insert into Sorted Array?

This function inserts a given value into a sorted array while maintaining its sorted order.

Time Complexity: O(n)

void insertIntoSorted(int value) {
    int i = length - 1;

    while (i >= 0 && A[i] > value) {
        A[i + 1] = A[i];
        i--;
    }

    A[i + 1] = value;
    length++;
}

⬆ Back to Top

Check if an Array is Sorted?

This function checks whether a given array is sorted in ascending order.

Time Complexity: O(n)

bool isSorted() {
    for (int i = 0; i < 9; i++) {
        if (A[i] > A[i + 1]) {
            return false;
        }
    }
    return true;
}

⬆ Back to Top

Arranging Negative Numbers on Left Side?

This function rearranges the array so that all negative numbers are placed on the left side, while the non-negative numbers remain on the right.

Time Complexity: O(n)

void adjust() {
    int i = 0, j = 9;
    while (i < j) {
        while (A[i] < 0) { i++; }
        while (A[j] >= 0) { j--; }
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

⬆ Back to Top

Merge Arrays?

Merging Two Sorted Arrays

Combines two sorted arrays into one sorted array.
Uses a two-pointer technique to efficiently merge the arrays.
Time Complexity: O(n + m), where n and m are the lengths of the arrays.

#include <iostream>
using namespace std;

class Array {
public:
    int A[5] = {1, 4, 7, 9, 10};
    int B[5] = {2, 3, 5, 6, 8};
    int C[10]; // Merged array
    int length = 10;

    void merge() {
        int i = 0, j = 0, k = 0;

        while (i < 5 && j < 5) {
            if (A[i] <= B[j]) {
                C[k++] = A[i++];
            } else {
                C[k++] = B[j++];
            }
        }

        while (i < 5) {
            C[k++] = A[i++];
        }

        while (j < 5) {
            C[k++] = B[j++];
        }
    }

    void print() {
        for (int i = 0; i < length; i++)
            cout << C[i] << " ";
        cout << endl;
    }
};

int main() {
    Array arr;
    arr.merge();
    arr.print();
}

⬆ Back to Top

Set Operations (Union, Intersection, Difference)?

1. Union of Two Arrays

Unsorted Arrays

Copy all elements of the first array (A) into the result array (C).
Iterate through the second array (B).
If an element from B is not already present in C, add it.
Time Complexity: O(m * n) (for checking duplicates)

#include<iostream>
using namespace std;

class Array{
    public:
      int A[5] = {2, 4, 1, 5, 10};
      int B[5] = {3, 4, 1, 2, 9};
      int C[10];
      int length = 0;

      void UNION() {
          for(int i = 0; i < 5; i++)
              C[length++] = A[i];
          for(int i = 0; i < 5; i++){
              bool found = false;
              for(int j = 0; j < length; j++){
                  if(B[i] == C[j]){
                      found = true;
                      break;
                  }
              }
              if(!found)
                  C[length++] = B[i];
          }
      }

      void print(){
          for(int i = 0; i < length; i++)
              cout << C[i] << " ";
      }
};

int main()
{
    Array A;
    A.UNION();
    A.print();
}

Sorted Arrays

Use two pointers i and j to traverse both arrays.
Compare elements and add the smaller one to C.
If they are equal, add one and move both pointers forward.
Add remaining elements of either array.
Time Complexity: O(m + n) (since both arrays are traversed once)

#include<iostream>
using namespace std;
class Array{
  public:
    int A[5] = {1, 4, 7, 8, 10};
    int B[5] = {2, 4, 5, 7, 8};
    int C[10];
    int k = 0;

      void UNION() {
         int i = 0, j = 0;

         while(i < 5 && j < 5){
             if(A[i] < B[j]){
                 C[k++] = A[i++];
             }else if(A[i] > B[j]){
                 C[k++] = B[j++];
             }else{
                 C[k++] = A[i];
                 i++; j++;
             }
         }

         while(i < 5)
             C[k++] = A[i++];
         while(j < 5)
             C[k++] = B[j++];
      }

      void print(){
          for(int i = 0; i < k; i++)
              cout << C[i] << " ";
      }
};

int main()
{
    Array A;
    A.UNION();
    A.print();
}

2. Intersection of Two Arrays

Unsorted Arrays

Iterate through A and B, checking for common elements.
Store them in C if found.
Time Complexity: O(m * n) (brute force comparison)

void INTERSECTION(){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            if(A[i] == B[j]){
                C[k++] = A[i];
            }
        }
    }
}

Sorted Arrays

Use two pointers i and j.
If A[i] == B[j], store in C.
Otherwise, increment the smaller pointer.
Time Complexity: O(m + n)

void INTERSECTION(){
    int i = 0, j = 0;
    while(i < 5 && j < 5){
        if(A[i] < B[j]){
            i++;
        }else if(A[i] > B[j]){
            j++;
        }else{
            C[k++] = A[i++];
            j++;
        }
    }
}

3. Difference of Two Arrays

Unsorted Arrays

Iterate through A, checking if each element exists in B.
If not, add to C.

Time Complexity: O(m * n) (brute force search)

void DIFFERENCE(){
    for(int i = 0; i < 5; i++){
        bool isFound = false;
        for(int j = 0; j < 5; j++){
            if(A[i] == B[j]){
                isFound = true;
                break;
            }
        }
        if(!isFound){
            C[k++] = A[i];
        }
    }
}

Sorted Arrays

Use two pointers i and j.
If A[i] is smaller, add it to C.
If equal, skip both.
Append remaining elements of A.
Time Complexity: O(m + n)

void DIFFERENCE(){
    int i = 0, j = 0;

    while(i < 5 && j < 5){
        if(A[i] < B[j]){
            C[k++] = A[i++];
        }else if(A[i] > B[j]){
            j++;
        }else{
            i++;
            j++;
        }
    }

    while(i < 5)
        C[k++] = A[i++];
}

⬆ Back to Top

Find Missing Element (Single Missing, Multiple Missing)?

1. Single Missing Element from Natural Numbers (Sorted Array)

From 1 to n (First n Natural Numbers):

void Array::missingElement(){
    int sum = 10 * (10 + 1) / 2;
    int s;
    for(int i = 0; i < 10; i++)
        s += A[i];

    cout << "Missing element is: " << (sum - s);
};

From k to n:

void Array::missingElement(){
    int diff = A[0] - 0;

    for(int i = 0; i < 10; i++){
        if(A[i] - i != diff){
            cout << "Missing element is: " << (diff + i) << endl;
            break;
        }
    }
};
// Add index + difference

2. Multiple Missing Elements from Unsorted Array

This procedure uses a hash table / bit set, which operates in constant time.
When searching for missing elements, a hash table is a preferred choice if feasible.
When using this technique, the required space should be equal to the maximum value of the array. If space is constrained, this approach may not be suitable.

void Array::missingElements(){
    int B[14]; // Maximum element of array
    for(int i = 0; i < 14; i++)
        B[A[i]] = 1;
    for(int i = 0; i < 14; i++)
        if(B[i] == 0)
           cout << "Missing element: " << i << endl;
}

⬆ Back to Top

Find Duplicate Elements?

1. Finding Duplicates in a Sorted Array

If an element appears more than once, it should be printed only once.

void duplicateElements(){
    int lastDuplicate = 0;
    for(int i = 0; i < 10 - 1; i++){
        if(A[i] == A[i + 1] && lastDuplicate != A[i]){
            cout << "Duplicate element: " << A[i] << endl;
            lastDuplicate = A[i];
        }
    }
}

2. Counting Duplicates in a Sorted Array

Counts how many times each element appears in a sorted array.

void countDuplicates(){
    for(int i = 0; i < 10 - 1; i++){
        if(A[i] == A[i + 1]){
            int j = i + 1;
            while(A[j] == A[i]) j++;
            cout << A[i] << " appears " << j - i << " times." << endl;
            i = j - 1;
        }
    }
}

3. Counting Duplicates Using a Hash Table (Sorted Array)

void countDuplicates(){
    for(int i = 0; i < 10 - 1; i++){
        if(A[i] == A[i + 1]){
            int j = i + 1;
            while(A[j] == A[i]) j++;
            cout << A[i] << " " << j - i << endl;
            i = j - 1;
        }
    }
}

4. Finding Duplicates in an Unsorted Array

Uses brute force method, setting duplicate values to -1.

void findDuplicateUnsort(){
    for(int i = 0; i < 10 - 1; i++){
        int count = 1;
        if(A[i] != -1){
            for(int j = i + 1; j < 10; j++){
                if(A[i] == A[j]){
                    count++;
                    A[j] = -1;
                }
            }
            if(count > 1){
                cout << "Duplicate element " << A[i] << " appears " << count << " times." << endl;
            }
        }
    }
}

5. Finding Duplicates Using a Hash Table (Unsorted Array)

void findDuplicateUnsort(){
    int B[10] = {0};
    for(int i = 0; i < 10; i++)
        B[A[i]]++;
    for(int i = 0; i < 10; i++)
        if(B[i] > 1)
            cout << "Duplicate element " << i << " appears " << B[i] << " times." << endl;
}

⬆ Back to Top

Finding a Pair with Sum K?

1. Finding a Pair of Elements with Sum K (Sorted Array)

This approach uses the two-pointer technique to find a pair whose sum equals k.

If the sum is equal to k, the pair is printed.
If the sum is less than k, increment i (move right).
If the sum is greater than k, decrement j (move left).
Time Complexity: O(n)

void Array::findPair(int k){
    int i = 0, j = 10 - 1;
    while (i < j) {
        if(A[i] + A[j] == k){
            cout << "Pair found: " << A[i] << " and " << A[j] << endl;
            i++; j--;
        } else if(A[i] + A[j] < k){
            i++;
        } else {
            j--;
        }
    }
}

2. Finding a Pair of Elements with Sum K (Unsorted Array)

This approach checks all possible pairs in a nested loop to find the sum k.

It iterates through the array, comparing each element with every other element.
If a pair with sum k is found, it is printed.
Time Complexity: O(n²)

void Array::findPair(int k){
    for(int i = 0; i < 10 - 1; i++){
        for(int j = i + 1; j < 10; j++){
            if(A[i] + A[j] == k){
                cout << "Pair found: " << A[i] << " and " << A[j] << endl;
            }
        }
    }
}

3. Finding a Pair of Elements with Sum K (Using Hash Table)

This approach uses an auxiliary array (hash table) to store values and find the sum efficiently.

How It Works:

It iterates through the array, checking if k - A[i] exists in the hash table.
If found, it prints the pair.
Otherwise, it marks A[i] as visited in the hash table.
Time Complexity: O(n)

void Array::findPair(int k){
    int B[10] = {0};

    for(int i = 0; i < 10; i++){
        if(B[k - A[i]] != 0)
            cout << "Pair found: " << A[i] << " and " << k - A[i] << endl;
        B[A[i]]++;
    }
}

⬆ Back to Top

Reverse an Array?

Reversing an array can be done in different segments:

1. Reverse `[1, k]`

This function reverses the elements from index 1 to k (0-based indexing).

void reverseOneToK(int k){
    for(int i = 0, j = k - 1; i < k / 2; i++, j--){
        int c = A[i];
        A[i] = A[j];
        A[j] = c;
    }
}

2. Reverse `[k + 1, n]`

This function reverses elements from index k + 1 to n, which means reversing the latter part of the array.

void reverseFromKPlusOne(int k) {
  for (int i = k + 1, j = size - 1; i < j; i++, j--) {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
  }
}

3. Reverse `[1, n]`

This function reverses the entire array.

void reverseOneToN(){
    for(int i = 0, j = 10 - 1; i < j; i++, j--){
        int c = A[i];
        A[i] = A[j];
        A[j] = c;
    }
}

⬆ Back to Top

Find Two Elements with Difference Equal to S in a Sorted Array?

Array in increasing order, we want to find two elements having difference equal to (s)

Works for sorted arrays.
Uses two pointers (i and j).
If difference equals s, prints the pair.
If difference is less than s, moves j forward.
If difference is greater than s, moves i forward.

Time Complexity: `O(n)`

void findDifference(int s) {
    int i = 0, j = 1;
    while (j < 10) {
        if ((A[j] - A[i]) == s) {
            cout << "Difference found with: " << A[j] << " - " << A[i] << endl;
            i++;
            j++;
        } else if ((A[j] - A[i]) < s) {
            j++;
        } else {
            i++;
        }
    }
}

⬆ Back to Top

Finding Minimum and Maximum in a Single Scan?

void minAndMax(){
    int min = A[0], max = A[0];

    for(int i = 1; i < 10; i++){
        if(A[i] < min)
            min = A[i];
        else if(A[i] > max)
            max = A[i];
    }

    cout << "Minimum: " << min << ", Maximum: " << max << endl;
}

Best Case: When array is in descending order (1 comparison per iteration).
Worst Case: When min and max are at opposite ends.

⬆ Back to Top

Find Array Elements that are Neither Minimum nor Maximum?

1. Simple Conditional Check

void findNum() {
   if(A[0] > A[1] && A[0] < A[2])
       cout << "Number: " << A[0];
   else if(A[1] > A[0] && A[1] < A[2])
       cout << "Number: " << A[1];
   else
       cout << "Number: " << A[2];
}

2. Generalized Approach for Larger Arrays

void findMiddleElements(int A[], int n) {
    int minVal = INT_MAX, maxVal = INT_MIN;

    // Finding minimum and maximum values
    for(int i = 0; i < n; i++) {
        if(A[i] < minVal) minVal = A[i];
        if(A[i] > maxVal) maxVal = A[i];
    }

    cout << "Elements neither minimum nor maximum: ";
    for(int i = 0; i < n; i++) {
        if(A[i] != minVal && A[i] != maxVal)
            cout << A[i] << " ";
    }
    cout << endl;
}

⬆ Back to Top

Find 2nd Maximum or Minimum Element?

// Maximum
void secondMaximum(){
    int first = INT_MIN, second = INT_MIN;
    for(int i = 0; i < 10; i++){
        if(A[i] > first){
            second = first;
            first = A[i];
        } else if(A[i] > second && A[i] != first){
            second = A[i];
        }
    }
    cout << "Second maximum value: " << second << endl;
}```

```cpp
// Minimum
void secondMinimum(){
    int first = INT_MAX, second = INT_MAX;
    for(int i = 0; i < 10; i++){
        if(A[i] < first){
            second = first;
            first = A[i];
        } else if(A[i] < second && A[i] != first){
            second = A[i];
        }
    }
    cout << "Second minimum value: " << second << endl;
}

⬆ Back to Top

Find Elements in Range (0-100) with Frequency > 50

Given an array of elements within the range 0 to 100, find the frequency of elements greater than 50 and display the count of each occurrence.

Approach

We initialize an array temp[50] to store the frequency of numbers greater than 50 (i.e., numbers between 51 to 100).
We read n elements from user input.
If the number is greater than 50, we increment its respective index in temp[].
Finally, we display the numbers and their corresponding frequency.

#include <iostream>
using namespace std;

class Array {
public:
    int temp[50] = {0}; // Frequency array for numbers 51-100

    void elementsCounting() {
        for (int i = 0; i < 10; i++) { // Modify 10 based on input size
            int element;
            cin >> element;

            if (element > 50 && element <= 100)
                temp[element - 51]++; // Map 51-100 to 0-49 index
        }
    }

    void display() {
        for (int i = 0; i < 50; i++) {
            if (temp[i] != 0)
                cout << (i + 51) << " appears " << temp[i] << " times" << endl;
        }
    }
};

int main() {
    Array A;
    A.elementsCounting();
    A.display();
}

⬆ Back to Top

Strings

Character Set

A character set is the set of characters that are supported by a programming language.
Computers do not directly understand characters, so numeric codes are assigned to characters.
These numeric codes are standardized globally, known as ASCII and Unicode.
Standardized by American National Standards Institute (ANSI) and ISO.

⬆ Back to Top

ASCII

Total ASCII codes: 128 (0-127)
A-Z ASCII codes: 65-90
a-z ASCII codes: 97-122
0-9 ASCII codes: 48-57
Special characters: Enter = 10, Space = 13, Esc = 27
Each symbol/character takes 7 bits or 1 byte

⬆ Back to Top

Unicode

Supports all languages worldwide.
Uses 16 bits or 2 bytes.
Represented in hexadecimal format.

Character array

char A[5];
char A[5] = {65, 66, 67, 68, 69};
char A[5] = {'A', 'B', 'C', 'D', 'E'}

⬆ Back to Top

Difference Between Character Set and Strings

A character set is a collection of characters assigned with unique numeric codes.
A string is a sequence of characters that ends with a null character (\0).

#include <iostream>
using namespace std;

int main() {
    char charSet[] = {65, 66, 67, 68, 69}; // Character Set (ASCII values for A-E)
    char str[] = "ABCDE"; // String with \0 at the end

    cout << "Character Set: ";
    for (char c : charSet) {
        cout << c << " ";
    }
    cout << "\nString: " << str << endl;
    return 0;
}

⬆ Back to Top

Strings

A string is a sequence of characters terminated by a special character \0 (null character).

The \0 character acts as a string delimiter.

char A[6] = "Hello"; // Automatically adds '\0' at the end

Without \0, a character array remains just an array of characters, not a string.

⬆ Back to Top

How to find Length of string?

We cannot calculate the size of a string using array - 1 because the string may have fewer elements than the total allocated size.
In C and C++, when you initialize a character array with a string literal like "ABDUL AHAD", the compiler automatically appends a null terminator ('\0') at the end of the string.
- So, when you declare char A[] = "ABDUL AHAD";, the memory layout looks like this:
  - | 'A' | 'B' | 'D' | 'U' | 'L' | 'A' | ' ' | 'H' | 'A' | 'D' | '\0' |

char A[] = "ABDUL AHAD";
cout << A << endl;
char B[5] = {'A', 'B', 'C', 'D', '\0'};
cout << B << endl;
char C[] = {'A', 'B', 'C', 'D', '\0'};
cout << C << endl;
int length = 0;
for(int i = 0; A[i] != '\0'; i++)
    length++;
cout << "Length of A: " << length;

Another approach using a function:

int length(char str[]) {
    int i = 0;
    while (str[i] != '\0') {
        i++;
    }
    return i;
}

⬆ Back to Top

How to change case of strings?

Changing the case of a string means converting uppercase letters to lowercase and lowercase letters to uppercase.

In ASCII, uppercase letters ('A' to 'Z') range from 65 to 90.
Lowercase letters ('a' to 'z') range from 97 to 122.
The difference between uppercase and lowercase letters is 32 ('A' + 32 = 'a' and 'a' - 32 = 'A').

Convert Uppercase to Lowercase

#include <iostream>
using namespace std;

int main() {
    char A[] = "ABDUL AHAD";

    // Convert to lowercase
    for (int i = 0; A[i] != '\0'; i++) {
        A[i] = char(A[i] + 32);
    }

    cout << A << endl; // Output: abdul ahad

    // Convert the first letter back to uppercase
    A[0] = char(A[0] - 32);

    cout << A; // Output: Abdul ahad
}

Convert Lowercase to Uppercase and Vice Versa

This program swaps the case of each character.

#include <iostream>
using namespace std;

int main() {
    char A[] = "ABDUL AHAD";

    // Toggle case (uppercase → lowercase, lowercase → uppercase)
    for (int i = 0; A[i] != '\0'; i++) {
        if (A[i] >= 97 && A[i] <= 122) // If lowercase
            A[i] -= 32;
        else if (A[i] >= 65 && A[i] <= 90) // If uppercase
            A[i] += 32;
    }

    char B[] = "cHiLli";

    for (int i = 0; B[i] != '\0'; i++) {
        if (B[i] >= 'a' && B[i] <= 'z') // If lowercase
            B[i] -= 32;
        else if (B[i] >= 'A' && B[i] <= 'Z') // If uppercase
            B[i] += 32;
    }

    cout << A << " " << B;
    // Output: abdul ahad ChIlLI
}

⬆ Back to Top

How to count words, vowels and consonants in a string?

This program calculates:

Word Count: A word is identified when a space is followed by a non-space character.
Vowel Count: Characters a, e, i, o, u (both uppercase and lowercase).
Consonant Count: Any letter that is not a vowel.

#include <iostream>
using namespace std;

int main() {
    char A[] = "We are all Palestinian";
    int wordCount = 0, vowelCount = 0, consonantCount = 0;

    for (int i = 0; A[i] != '\0'; i++) {
        // Counting words (checking spaces between words)
        if (A[i] == ' ' && A[i - 1] != ' ')
            wordCount++;

        // Counting vowels
        if (A[i] == 'a' || A[i] == 'e' || A[i] == 'i' || A[i] == 'o' || A[i] == 'u' ||
            A[i] == 'A' || A[i] == 'E' || A[i] == 'I' || A[i] == 'O' || A[i] == 'U') {
            vowelCount++;
        }
        // Counting consonants (any alphabet that is not a vowel)
        else if ((A[i] >= 65 && A[i] <= 90) || (A[i] >= 97 && A[i] <= 122)) {
            consonantCount++;
        }
    }

    cout << "Total words: " << wordCount + 1 << " ,Vowels: " << vowelCount << " ,Consonants: " << consonantCount;
}

⬆ Back to Top

How to validate a string?

This program checks whether a given string is valid by ensuring it contains only:

Digits (0-9)
Uppercase letters (A-Z)
Lowercase letters (a-z)

If the string contains any special characters (e.g., @, *, #, !), it is considered invalid.

#include <iostream>
using namespace std;

int validate(char A[]) {
    for (int i = 0; A[i] != '\0'; i++) {
        // Checking if the character is NOT a digit, uppercase letter, or lowercase letter
        if (!(A[i] >= 48 && A[i] <= 57) && !(A[i] >= 65 && A[i] <= 90) && !(A[i] >= 97 && A[i] <= 122))
            return 0; // Invalid string
    }
    return 1; // Valid string
}

int main() {
    char A[] = "ABDULAHAD786*ali";  // String to validate
    if (validate(A))
        cout << "Valid string!";
    else
        cout << "Not a valid string!";
}

⬆ Back to Top

How to Reverse a String?

Reversing a string means rearranging its characters in the opposite order. We can achieve this using:

Extra Array Method: Storing the reversed string in a separate array.
Swapping Method: Swapping characters in the same array.

Method 1: Using an Extra Array

First, find the length of the string.
Then, store characters in reverse order in a new array.

#include <iostream>
using namespace std;

int main() {
    char A[] = "CHILLI";
    int i;

    // Finding string length
    for(i = 0; A[i] != '\0'; i++) {};

    char B[i];  // Creating new array to store reversed string
    i = i - 1;  // Adjusting index to last character

    // Storing characters in reverse order
    for(int j = 0; i >= 0; i--, j++)
        B[j] = A[i];

    cout << "Reversed string: " << B;
}

Method 2: Swapping in the Same Array

Using two pointers: One at the start, another at the end.
Swap characters until pointers meet in the middle.

#include <iostream>
using namespace std;

int main() {
    char A[] = "CHILLI";
    int i, j;

    // Finding string length
    for(j = 0; A[j] != '\0'; j++) {};
    j--;  // Move to last character

    // Swapping characters
    for(i = 0; i < j; i++, j--) {
        char c = A[i];
        A[i] = A[j];
        A[j] = c;
    }

    cout << "Reversed string: " << A;
}

⬆ Back to Top

How to compare strings and check palindrome?

1. Comparing Strings

String comparison determines which string is lexicographically larger, smaller, or equal.

Iterate through both strings character by character.
Stop at the first mismatched character.
Compare their ASCII values:
- If A[i] > B[j], A is larger.
- If A[i] < B[j], A is smaller.
- If all characters match, the strings are equal.

#include <iostream>
using namespace std;

int main() {
    char A[] = "APPLE";
    char B[] = "BANANA";
    int i, j;

    // Compare characters one by one
    for(i = 0, j = 0; A[i] != '\0' && B[j] != '\0'; i++, j++)
        if(A[i] != B[j])
            break;

    if(A[i] > B[j])
        cout << "A is larger";
    else if(A[i] < B[j])
        cout << "A is smaller";
    else
        cout << "Both strings are equal!";
}

2. Checking if a String is a Palindrome

A palindrome is a string that reads the same forward and backward.

"MADAM", "RACECAR" are palindromes.
"HELLO", "WORLD" are not palindromes.

Reverse the string and store it in another array.
Compare the original and reversed strings character by character.
If all characters match, it's a palindrome.

#include <iostream>
using namespace std;

int main() {
    char A[] = "MADAM";
    int i;

    // Step 1: Find string length
    for(i = 0; A[i] != '\0'; i++) {}

    char B[i + 1];  // Extra space for null terminator
    B[i] = '\0';  // End reversed string with null character

    // Step 2: Store reversed string
    for(int j = 0; i > 0; i--, j++) {
        B[j] = A[i - 1];
    }

    // Step 3: Compare original and reversed strings
    for(i = 0; A[i] != '\0'; i++) {
        if(A[i] != B[i]) {
            cout << "Not a palindrome\n";
            return 0;
        }
    }

    cout << "Palindrome\n";
}

3. Alternative: Two-Pointer Palindrome Check

A more efficient approach is to use two pointers, one at the start and one at the end, and compare characters.

#include <iostream>
using namespace std;

int main() {
    char A[] = "MADAM";
    int i, j;

    // Find string length
    for(j = 0; A[j] != '\0'; j++) {};
    j--;  // Adjust for index

    // Compare first and last characters
    for(i = 0; i < j; i++, j--) {
        if(A[i] != A[j]) {
            cout << "Not a palindrome\n";
            return 0;
        }
    }

    cout << "Palindrome\n";
}

⬆ Back to Top

How to find duplicates in strings?

Finding duplicate characters in a string helps in text processing, compression, and data validation.

Methods to Find Duplicates

Using Nested Loops (Brute Force) → O(n²) Time Complexity
Using Hash Tables (Efficient for lowercase letters) → O(n) Time Complexity

1. Brute Force Approach (Nested Loops)

Compare each character with all previous characters.

#include <iostream>
using namespace std;

int main() {
    char A[] = "Finding";

    for(int i = 0; A[i] != '\0'; i++) {
        for(int j = 0; j < i; j++) {
            if(A[i] == A[j]) {
                cout << "Duplicate element: " << A[i] << endl;
                break; // Stop checking once a duplicate is found
            }
        }
    }
}

2. Efficient Approach Using Hash Tables

Create an array of size 26 (for lowercase letters).
Traverse the string and count occurrences of each character.
Print characters that appear more than once.

#include <iostream>
using namespace std;

int main() {
    char A[] = "finding"; // Lowercase string
    int B[26] = {0};  // Hash table initialized with 0

    // Count character occurrences
    for(int i = 0; A[i] != '\0'; i++) {
        B[A[i] - 'a']++;
    }

    // Display duplicates
    for(int i = 0; i < 26; i++) {
        if(B[i] > 1) {
            cout << char(i + 'a') << " appears " << B[i] << " times." << endl;
        }
    }
}

3. Optimized Approach: Using Bit Manipulation

Faster than other methods.
Lower memory usage (only a single integer).
Works only for lowercase letters (a-z).

#include <iostream>
using namespace std;

int main() {
    char A[] = "finding";
    int checker = 0, x = 0;

    for(int i = 0; A[i] != '\0'; i++) {
        x = 1 << (A[i] - 'a');  // Create a bitmask

        if((checker & x) > 0) // Check if character already exists
            cout << "Duplicate element: " << A[i] << endl;
        else
            checker = checker | x;  // Mark character as seen
    }
}

⬆ Back to Top

How to apply bitwise operations?

Why Use Bitwise Operations?

Bitwise operations allow efficient manipulation of binary data. They are widely used in:

Strings: Checking for duplicate characters, toggling cases, etc.
Integers: Performing arithmetic and logical operations efficiently.

Types of Bitwise Operations

1️. Left Shift (`<<`)

Shifts bits to the left by a specified number of positions.
Fills the empty right positions with 0s.
Effectively multiplies the number by 2^n.

int x = 5;      // 0000 0101
int y = x << 1; // 0000 1010  (5 * 2 = 10)

2. Bitwise AND (`&`) - Masking

Used to check whether a specific bit is set (ON) or not.
If a bit is 1 in both operands, the result is 1; otherwise, 0.

int x = 5;      // 0000 0101
int y = 1;      // 0000 0001
int result = x & y; // 0000 0001 (1)

Use Case: Checking if a character has already appeared in a string.

3️. Bitwise OR (`|`) - Merging

Used to set (turn ON) a bit at a specific position.
If a bit is 1 in either operand, the result is 1.

int x = 5;      // 0000 0101
int y = 2;      // 0000 0010
int result = x | y; // 0000 0111 (7)

Use Case: Marking a character as "seen" in a string.

4. Finding Duplicate Characters in a String

This method uses bitwise operations to detect duplicate characters efficiently.

Use a long integer (H) as a bit container.
Left shift (<<) to mark characters as seen.
Use AND (&) to check if a character was already marked.
Use OR (|) to mark new characters as seen.

#include <iostream>
using namespace std;

int main() {
    char A[] = "Finding";
    long int H = 0, x = 0;

    for(int i = 0; A[i] != '\0'; i++) {
        x = 1;
        x = x << (A[i] - 'a');  // Left shift based on character position

        if((x & H) > 0)  // Check if character is already seen
            cout << A[i] << " is a duplicate element!" << endl;
        else
            H = x | H;  // Mark character as seen
    }
}

⬆ Back to Top

How to check if strings are anagram?

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase. In this approach, we check whether all the elements from string 1 are present in string 2.

First, check if the sizes of both strings are equal. If not, they are not anagrams.
Use an array of size 26 (for lowercase letters) to count occurrences of each character in the first string.
Traverse the second string and decrement the character count in the array.
If any value in the array becomes negative, the strings are not anagrams.
If all values are zero at the end, the strings are anagrams.

#include <iostream>
using namespace std;

int main() {
    char A[] = "finding";
    char B[] = "dingfin";

    int i, C[26] = {0};
    bool isAnagram = true;

    // Count character occurrences in A
    for(i = 0; A[i] != '\0'; i++)
        C[A[i] - 'a'] += 1;

    // Compare with B
    for(i = 0; B[i] != '\0'; i++) {
        C[B[i] - 'a'] -= 1;
        if(C[B[i] - 'a'] < 0) {
            isAnagram = false;
            cout << "Not Anagram" << endl;
            break;
        }
    }

    if(isAnagram && B[i] == '\0')
        cout << "Anagram" << endl;
}

Complexity Analysis

Method	Time Complexity	Space Complexity
Nested Loops	O(n²)	O(1)
Hash Table	O(n)	O(1)

Recommended Approach: Using hash tables provides better performance compared to the nested loop method.

⬆ Back to Top

How to Find Permutation of Strings?

Arrangement of a string.
For ABC:
- Possible permutations: ABC, ACB, BAC, BCA, CAB, CBA
- Since there are 3 characters, the number of arrangements is 3!.
- For n characters, the arrangement is n!.
State Space Tree: Imagine a tree where each branch represents a possible state of a problem, and the leaves show the results.
Backtracking: Going back and trying another path in the tree to explore different possibilities.
Brute Force: Trying every possible combination to find a solution.
Recursion: Using a procedure within itself to explore different paths, often used for backtracking.
Dynamic Programming: It's like a smarter brute force. It also tries different combinations but aims to find the best solution efficiently.
Use recursion to achieve backtracking.
With backtracking, we perform brute force.
Traverse in each call and pick characters that are not yet selected.
At the leaf node, prepare a string and display it.

Method 1: Using Recursion with a Helper Array

#include <iostream>
using namespace std;

void perm(char s[], int k){
    static char res[10];
    static int A[10] = {0};
    if(s[k] == '\0'){
        res[k] = '\0';
        cout << res << " ";
    }else{
        for(int i = 0; s[i] != '\0'; i++){
            if(A[i] == 0){
                res[i] = s[k];
                A[i] = 1;
                perm(s, k + 1);
                A[i] = 0;
            }
        }
    }
}

int main()
{
   char p[] = "ABC";
   perm(p, 0);
}

Method 2: Using Swapping

#include <iostream>
using namespace std;

void swap(char &x, char &y){
    char z = x;
    x = y;
    y = z;
}

void perm(char p[], int l, int h){
    if(l == h){
        cout << p << " ";
    }else{
        for(int i = l; i <= h; i++) {
            swap(p[l], p[i]);
            perm(p, l + 1, h);
            swap(p[l], p[i]);
        }
    }
}

int main()
{
   char p[] = "ABC";
   perm(p, 0, 2);
}

⬆ Back to Top

Recursion

What is Recursion?

Recursion is a programming concept where a function calls itself to solve a smaller version of the same problem.

Recursion breaks a problem into smaller sub-problems of the same type.
It follows the LIFO (Last In, First Out) principle.
Every recursive function must have a base case to prevent infinite recursion.
Recursion can be traced using a tree diagram.
It has two phases:
- Calling phase (function calls itself)
- Returning phase (function returns values)

void fun(int num) {
  if (num > 0) {
      cout << num << " "; // Prints in descending order
      fun(num - 1); // Recursive call
      cout << num << " "; // Prints in ascending order after returning from recursion
  }
}

⬆ Back to Top

How Recursion Works?

Recursion follows these steps:

Calls itself with a smaller input.
Stops when it reaches the base case.
Returns values in reverse order (returning phase).

Example:

void countDown(int n) {
    if (n == 0) return; // Base case
    cout << n << " ";
    countDown(n - 1); // Recursive call
}

⬆ Back to Top

What are the Advantages & Disadvantages of Recursion?

Advantages:

Easier to read and write for problems like tree traversal, DFS, etc.
Reduces complex problems into simpler sub-problems.

Disadvantages:

Can be slow due to repeated function calls.
Uses extra memory (stack space).
Risk of stack overflow if recursion depth is too high.

⬆ Back to Top

How to Trace Recursive Functions?

Recursion can be traced using a tree diagram.

Identify the base case and recursive case.
Expand each recursive call in a tree-like structure.
Evaluate the base case first to stop recursion.
Work your way back up to compute results.

Head Recursion (Recursive Call First)

void fun1(int n) {
    if (n > 0) {
        cout << n << " ";  // Print before recursive call
        fun1(n - 1);
    }
}
int main() {
    fun1(3);
}

Tracing:

        fun1(3)
        /  \
 Print 3    fun1(2)
           /   \
    Print 2     fun1(1)
                /   \
         Print 1     fun1(0) → Base Case (stops recursion)

Tail Recursion (Recursive Call First, Printing After Returning)

void fun2(int n) {
    if (n > 0) {
        fun2(n - 1);  // Recursive call first
        cout << n << " ";  // Print after recursion
    }
}
int main() {
    fun2(3);
}

Tracing:

              fun2(3)
              /
        fun2(2)
        /
   fun2(1)
   /
fun2(0) → Base Case (stops recursion)
   ├── Prints 1
   ├── Prints 2
   ├── Prints 3

⬆ Back to Top

What are the Phases of Recursion?

Recursion has two phases:

Calling Phase: Function calls itself.
Returning Phase: Function returns values after reaching the base case.

int fun(int num) {
    if (num > 0) {
        cout << num << " "; // Calling Phase
        fun(num - 1);
        cout << num << " "; // Returning Phase
    }
}

Two scenarios of recursion:

Switch on the light (bulb) and go to the next room.

void fun(int num) {
    if (num > 0) {
        cout << num << " "; // Prints in descending order
        fun(num - 1); // (*2) Returning time
        cout << num << " "; // Prints in ascending order after returning from recursion
    }
}

Go to the next room and then switch on the light (bulb).

int fun2(int num){
    if(num > 0){
        fun1(num - 1);
        cout << num << " ";
    }
}

int main(){
    fun1(3);
    cout << endl;
    fun2(3);
}

Generalization

The things that occur before are executed during calling time. We can call it ascending.
The things that occur after are executed during returning time. The things that are present with the function also do work during returning time. We can call it descending.

int fun(int num){
    if(num > 0){
    cout << num;
    cout << fun(num - 1) * 2;
    cout << num;
    }
}

⬆ Back to Top

What is the Difference Between Recursion and Loop?

Both recursion and loops are used for repeating operations, but they have key differences:

Loops execute in a straightforward manner, usually iterating in one direction (ascending order).
Recursion executes in both ascending and descending order, making function calls until a base case is met.

Feature	Recursion	Loop
Memory Usage	High (due to stack frames)	Low (single iteration variable)
Execution Speed	Slower (due to function calls)	Faster
Readability	Easier for complex problems	Easier for simple problems

Recursion:

void recursiveFunction(int n) {
    if (n > 0) {
        cout << n << " ";
        recursiveFunction(n - 1);
    }
}

int main() {
    recursiveFunction(5); // 5 4 3 2 1
}

recursiveFunction(5)
├── recursiveFunction(4)
│   ├── recursiveFunction(3)
│   │   ├── recursiveFunction(2)
│   │   │   ├── recursiveFunction(1)
│   │   │   │   ├── recursiveFunction(0) → Base Case (stops recursion)

Loop:

int main() {
    for (int i = 5; i > 0; i--) {
        cout << i << " "; // 5 4 3 2 1
    }
}

i = 5 → Print 5 → i--
i = 4 → Print 4 → i--
i = 3 → Print 3 → i--
i = 2 → Print 2 → i--
i = 1 → Print 1 → i--
i = 0 → Loop stops

⬆ Back to Top

How Recursion Uses Stack?

Each recursive function call creates an activation record in the stack. When the base case is reached, the function calls return in reverse order.

Consider the following recursive function:

void fun(int n) {
    if (n > 0) {
        cout << "Call: " << n << endl;
        fun(n - 1);
        cout << "Return: " << n << endl;
    }
}
int main() {
    fun(3);
}

Function call flow:

fun(3)   → Push onto stack
  fun(2)   → Push onto stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
    (return 1) → Pop from stack
  (return 2) → Pop from stack
(return 3) → Pop from stack

Stack Memory:

| fun(0) |  → Base Case (pops first)
| fun(1) |
| fun(2) |
| fun(3) |  → First pushed, last popped (LIFO)

⬆ Back to Top

What are the Types of Recursion?

If a recursive function has operations before and after the recursive call, it is called linear recursion.

Tail Recursion

A recursive function where the recursive call is the last statement in the function.
Everything is performed at calling time.
No operation is left for returning time.
If additional operations are needed after returning, it is not tail recursion.
Easily convertible to a loop.
Time Complexity: O(n)
Space Complexity:
- Recursion: O(n) (due to n activation records)
- Loop: O(1) (single activation record)
Conclusion: Loops are more efficient for tail recursion.

Loop:

void fun(int n){
    while(n > 0){
        cout << n;
        n--;
    }
}

Recursion:

void fun(int n){
    if(n > 0){
        cout << n << " ";
        fun(n - 1);
    }
}
int main(){
    fun(3);
}

Recursive Call Tree:

fun(3)
|
fun(2)
|
fun(1)
|
fun(0) → Base Case (stops recursion)

Function call flow:

fun(3)   → Push onto stack
  fun(2)   → Push onto stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
    (return) → Pop from stack
  (return) → Pop from stack
(return) → Pop from stack

Stack Memory:

| fun(0) |  → Base Case (pops first)
| fun(1) |
| fun(2) |
| fun(3) |  → First pushed, last popped (LIFO)

Head Recursion

In head recursion, the recursive call is the first statement in the function. No operations are performed before the recursive call.
- All operations occur only at returning time.
- Difficult to convert into a loop without extra logic.

Loop:

void fun(int n){
  int i = 1;
  while(i <= n){
    cout << n;
    n--;
  }
}

Recursion:

void fun(int n){
    if(n > 0){
        fun(n - 1);
        cout << n << " ";
    }
}
int main(){
    fun(3);
}

Recursive Call Tree:

         fun(3)
        /
     fun(2)
    /
 fun(1)
 /
fun(0) → Base Case (stops recursion)

Function call flow:

fun(3)   → Push onto stack
  fun(2)   → Push onto stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
    (return 1) → Pop from stack → Print 1
  (return 2) → Pop from stack → Print 2
(return 3) → Pop from stack → Print 3

Stack Memory:

| fun(0) |  → Base Case (pops first)
| fun(1) |
| fun(2) |
| fun(3) |  → First pushed, last popped (LIFO)

Tree Recursion

If a function calls itself more than once, it is called tree recursion.
The time complexity of tree recursion is calculated as:

[ (2⁰ + 2¹ + 2² + ... + 2ⁿ) = (2ⁿ⁺¹) - 1 \approx O(2ⁿ) ]
The space complexity depends on the height of the recursive tree, which is O(n).

void fun(int n)
{
   if (n > 0)
   {
     printf("%d ", n);
     fun(n - 1);
     fun(n - 1);
   }
}

Recursive Call Tree:

                fun(3)
               /      \
          fun(2)      fun(2)
         /     \      /     \
    fun(1)  fun(1) fun(1)  fun(1)
    /    \   /   \  /    \  /   \
fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) → Base Case (Stops recursion)

Function call flow:

fun(3)   → Push onto stack
  fun(2)   → Push onto stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
      fun(0)   → Base Case (Stops recursion)
    (return) → Pop from stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
      fun(0)   → Base Case (Stops recursion)
    (return) → Pop from stack
  (return) → Pop from stack
  fun(2)   → Push onto stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
      fun(0)   → Base Case (Stops recursion)
    (return) → Pop from stack
    fun(1)   → Push onto stack
      fun(0)   → Base Case (Stops recursion)
      fun(0)   → Base Case (Stops recursion)
    (return) → Pop from stack
  (return) → Pop from stack
(return) → Pop from stack

Stack Memory:

| fun(0) |  → Base Case (pops first)
| fun(1) |
| fun(2) |
| fun(3) |  → First pushed, last popped (LIFO)

For tree recursion, multiple function calls are pushed onto the stack before returning.

Indirect recursion

Indirect recursion occurs when more than one function calls one another in a circular manner.
Instead of a single function calling itself directly, function A calls B, B calls C, and C calls A (or any similar cycle).

void fun2(int n);
void fun1(int n){
    if(n > 0){
        cout << n << endl;
        fun2(n - 1);  // Calling fun2
    }
}
void fun2(int n){
    if(n > 1){
        cout << n << endl;
        fun1(n / 2);  // Calling fun1
    }
}
int main(){
    fun1(20);
}

Recursive Call Tree:

fun1(20)
    |
fun2(19)
    |
fun1(9)
    |
fun2(8)
    |
fun1(4)
    |
fun2(3)
    |
fun1(1)
    |
fun2(0) → Base Case (Stops recursion)

Function call flow:

fun1(20)  → Push onto stack
  fun2(19)  → Push onto stack
    fun1(9)  → Push onto stack
      fun2(8)  → Push onto stack
        fun1(4)  → Push onto stack
          fun2(3)  → Push onto stack
            fun1(1)  → Push onto stack
              fun2(0)  → Base Case (Stops recursion)
            (return) → Pop from stack
          (return) → Pop from stack
        (return) → Pop from stack
      (return) → Pop from stack
    (return) → Pop from stack
  (return) → Pop from stack
(return) → Pop from stack

Stack Memory:

| fun2(0) |  → Base Case (pops first)
| fun1(1) |
| fun2(3) |
| fun1(4) |
| fun2(8) |
| fun1(9) |
| fun2(19) |
| fun1(20) |  → First pushed, last popped (LIFO)

For indirect recursion, functions call each other alternately before returning.

Nested Recursion

Nested recursion occurs when a recursive function passes a parameter as a recursive call.
First, it processes the parameter recursively, and then the result is used in the main recursion.

int fun(int n){
  if(n > 100){
    return n - 10;  // Base condition
  } else {
    return fun(fun(n + 11));  // Nested recursion
  }
}
int main() {
    cout << fun(95) << endl;  // Example call
}

Recursive Call Tree:

                          fun(95)
                              |
               ---------------------------------
               |                               |
           fun(fun(106))                   fun(96)
               |                               |
       ------------------                ------------------
       |                |                |                |
   fun(106)         fun(fun(107))     fun(97)         fun(fun(108))
       |                |                |                |
      96       ---------------          97       ---------------
              |             |                    |             |
          fun(107)     fun(fun(108))        fun(98)     fun(fun(109))
              |             |                    |             |
             97      ---------------           98      ---------------
                      |             |                    |             |
                  fun(108)     fun(fun(109))        fun(99)     fun(fun(110))
                      |             |                    |             |
                     98      ---------------           99      ---------------
                              |             |                    |             |
                          fun(109)     fun(fun(110))        fun(100)     fun(fun(111))
                              |             |                    |             |
                             99      ---------------          100      ---------------
                                      |             |                    |             |
                                  fun(110)     fun(fun(111))        fun(101)     fun(101)
                                      |             |                    |             |
                                     100      ---------------          101          101
                                              |             |
                                          fun(111)     fun(101)
                                              |             |
                                             101           91

Function call flow:

fun(95) → Calls fun(fun(106))
  fun(106) → Returns 96
  fun(96) → Calls fun(fun(107))
    fun(107) → Returns 97
    fun(97) → Calls fun(fun(108))
      fun(108) → Returns 98
      fun(98) → Calls fun(fun(109))
        fun(109) → Returns 99
        fun(99) → Calls fun(fun(110))
          fun(110) → Returns 100
          fun(100) → Calls fun(fun(111))
            fun(111) → Returns 101
            fun(101) → Returns 91
          Returns 91
        Returns 91
      Returns 91
    Returns 91
  Returns 91
Returns 91

Stack Memory:

| fun(101) → 91 |  → Base Case Reached
| fun(100) → 91 |
| fun(99) → 91  |
| fun(98) → 91  |
| fun(97) → 91  |
| fun(96) → 91  |
| fun(95) → 91  |  → First pushed, last popped (LIFO)

⬆ Back to Top

What is the Time Complexity of Recursion (Tree vs Recurrence Relation)?

We can analyze recursion time complexity using two methods:

Tree Diagram Approach
- Convert the recursion into a tree-like structure.
- Count the number of function calls at each level.
- Determine the complexity.
Recurrence Relation Approach
- Express the recursive function as a mathematical recurrence relation.
- Solve it using the substitution method or the Master Theorem.

Tree Diagram

A tree diagram helps visualize recursion depth and function calls.

int fib(int n) {
    if (n <= 1) return n; // Base Case
    return fib(n-1) + fib(n-2); // Recursive Case
}

Recursive Call Tree:

              fib(4)
             /      \
        fib(3)      fib(2)
       /      \     /      \
  fib(2)   fib(1) fib(1)  fib(0)
  /     \
fib(1) fib(0)

The recursion tree has O(2ⁿ) calls.
Each level doubles the number of calls, leading to O(2ⁿ) complexity..

Recurrence Relation:

The recurrence relation expresses how the function breaks down.

Fibonacci Recursion:

The recurrence relation for Fibonacci is: T(n) = T(n-1) + T(n-2) + O(1)
Expanding it: T(n) ≈ 2T(n-1)
This leads to O(2ⁿ) complexity.

Factorial Recursion

int fact(int n) {
    if (n == 0) return 1; // Base Case
    return n * fact(n - 1); // Recursive Case
}

The recurrence relation for Factorial is: T(n) = T(n-1) + O(1)
Expanding it: T(n) = T(n-2) + 2O(1)
This leads to O(n) complexity.

Method	How it Works	Best for
Tree Diagram	Expands recursion into a tree and counts calls	Intuitive visualization
Recurrence Relation	Converts recursion into a mathematical equation	Formal complexity analysis

⬆ Back to Top

What are the Steps to Solve Recursive Problems?

To effectively solve problems using recursion, follow these five key steps:

1️. Find the Simplest Possible Input

Identify the base case, which is the smallest input that can be solved directly.
The base case is the only case where we provide an explicit answer; all other solutions will build upon it.

2️. Play Around with Examples

Try small inputs to see how the problem behaves.
Check edge cases and special cases to ensure correctness.

3️. Relate Hard Cases to Simplest Cases

Break down the problem into smaller subproblems.
Example:
- If we know how to find the sum from 0 to 3, can we use that to find the sum from 0 to 4?

4️. Generalize the Pattern

Identify a recurrence relation.
Example:
- If we need to compute a value for n = k, we can find it by first computing n = k - 1 and then combining results.

5️. Write Code by Combining Recursive Pattern with Base Case

Implement the recursive pattern identified.
Ensure the base case stops recursion.

int sum(int n) {
    if (n == 0) return 0; // Base Case
    return n + sum(n - 1); // Recursive Case
}

int main() {
    cout << "Sum of first 5 numbers: " << sum(5) << endl;
}

Recursive Calls:

sum(5) = 5 + sum(4)
sum(4) = 4 + sum(3)
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1 + sum(0)
sum(0) = 0  → Base Case

Returns in Reverse Order:

sum(1) = 1 + 0 = 1
sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6
sum(4) = 4 + 6 = 10
sum(5) = 5 + 10 = 15

⬆ Back to Top

How to find the Sum of First N Natural Numbers?

1. Formula

The formula for finding the sum of first N natural numbers is: [ S = \frac{n(n + 1)}{2} ]

int sumFormula(int n){
    return (n * (n + 1)) / 2;
}

Time and space complexity is: O(n)

2. Loop

Iterate from 1 to n and sum up values.

int sumLoop(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        sum += i;
    }
    return sum;
}

Time complexity is O(n) and space complexity is O(1).

3. Recursion

The sum of the first n numbers is: S(n)=n+S(n−1)

int sumRecursive(int n){
    if(n == 0){
        return 0;  // Base case
    } else {
        return n + sumRecursive(n - 1);
    }
}

Recursive Call Tree:

            sumRecursive(4)
                 │
          ┌─────┴─────┐
          │           │
   sumRecursive(3)    +4
        │
   ┌────┴────┐
   │         │
sumRecursive(2)   +3
     │
 ┌───┴───┐
 │       │
sumRecursive(1)   +2
    │
┌───┴───┐
│       │
sumRecursive(0)  +1 (Base Case)

Function call flow:

sumRecursive(4) → Calls sumRecursive(3)
  sumRecursive(3) → Calls sumRecursive(2)
    sumRecursive(2) → Calls sumRecursive(1)
      sumRecursive(1) → Calls sumRecursive(0) → Base Case returns 0
      (returns 1 + 0 = 1)
    (returns 2 + 1 = 3)
  (returns 3 + 3 = 6)
(returns 4 + 6 = 10)

Stack Memory: Before Returning (LIFO - Last In, First Out):

| sumRecursive(0) |  → Base Case (pops first)
| sumRecursive(1) |
| sumRecursive(2) |
| sumRecursive(3) |
| sumRecursive(4) |  → First pushed, last popped (LIFO)

After Returning:

| sumRecursive(1) | → sumRecursive(0) popped
| sumRecursive(2) | → sumRecursive(1) popped
| sumRecursive(3) | → sumRecursive(2) popped
| sumRecursive(4) | → sumRecursive(3) popped

Time complexity is O(n) and space complexity is O(n) -> because of recursive calls.

⬆ Back to Top

How to find the Factorial of a Number?

Loop

int fac(int n){
  int fc = 1;
  if(n > 0)
    for(int i = 0; i <= n; i++)
      fc *= i;
  else
    return 1;
  return fc;
}

Recursion

int fac(int n){
  if(n > 0)
    return (n - 1) * n;
  else
    return 1;
}

Recursive Call Tree:

          fac(5)
         /
    fac(4)
       /
   fac(3)
      /
  fac(2)
     /
 fac(1)
    /
fac(0) → Base Case (stops recursion)

Function call flow:

fac(5)   → Push onto stack
  fac(4)   → Push onto stack
    fac(3)   → Push onto stack
      fac(2)   → Push onto stack
        fac(1)   → Push onto stack
          fac(0)   → Base Case (stops recursion)
        (return 1) → Pop from stack
      (return 2 * 1 = 2) → Pop from stack
    (return 3 * 2 = 6) → Pop from stack
  (return 4 * 6 = 24) → Pop from stack
(return 5 * 24 = 120) → Pop from stack

Stack Memory:

| fac(0) |  → Base Case (pops first)
| fac(1) |
| fac(2) |
| fac(3) |
| fac(4) |
| fac(5) |  → First pushed, last popped (LIFO)

⬆ Back to Top

How to find the Power of a Number (m^n)?

Loop

int fun(int n, int m) {
    if (m > 0) {
        int result = 1;
        for (int i = 0; i < m; i++) {
            result *= n;
        }
        return result;
    } else {
        return 1;
    }
}

When we have to return multiple values from recursive function then we use static keywords.

Recursion

It will create total n + 1 activation records.
Other way:
- If power is even:
  - (m * m)ⁿ∕ ²
- If power is odd:
  - m * (m * m)ⁿ⁻¹∕ ²

Simple Recursive

int fun(int n, int m){
  if(m > 0){
      return fun(n, m - 1) * n;
  }else{
      return 1;
  }
};

Optimized Recursive (Exponentiation by Squaring)

int fun(int n, int m){
  if(m == 0){
    return 1;
  }
  if(m % 2 == 0){
    return fun(n * n, m / 2);
  }else{
    return n * fun(n * n, (m - 1) / 2);
  }
}

Recursive Call Tree (For fun 2^3):

          fun(2, 3)
         /        \
  2 * fun(4, 1)   → m is odd, so multiply n
      /
  fun(16, 0)  → Base Case (stops recursion)

Function call flow:

fun(2, 3)   → Push onto stack
  fun(4, 1)   → Push onto stack
    fun(16, 0)   → Base Case (Stops recursion)
  (return 16) → Pop from stack
(return 32) → Pop from stack

Stack Memory:

| fun(16, 0) |  → Base Case (pops first)
| fun(4, 1)  |
| fun(2, 3)  |  → First pushed, last popped (LIFO)

⬆ Back to Top

How to find the Taylor Series?

Using recursion:

Time complexity or number of multiplication is O(n²). We can calculate is by calculating its number of multiplications.

double fun(double num, double power) {
    static double p = 1;
    static double f = 1;
    double r;

    if(power == 0){
        return 1;
    }
        p *= num;
        f *= power;
        r = fun(num, power - 1);

    return r + p / f;
}
int main() {
    cout <<fun(2, 3);
}

Using loop:

double fun(double x, double power) {
    double s = 1;
    double power = 1;
    double fac = 1;

    for(int i = 1; i <= power; i++){
        power *= x;
        fac *= i;
        s += num / den;
    }
    return s;
}
int main() {
    cout <<fun(2, 3);
}

Using Horners:

In this method we take commons at much at possible to reduce number of multiplications.
Recursion:

double fun(double num, double power) {
static double s = 1;

if(power == 0){
    return s;
}

s = 1 + num / power * s;
fun(num, power - 1);
}
int main() {
cout <<fun(2, 3);
}

Loop

double fun(double num, double power) {
    double s = 1;
    for(; power > 0; power--){
        s = 1 + num / power * s;
    }
    return s;
}
int main() {
    cout <<fun(2, 3);
}

How to find the Fibonacci Series (Excessive Recursion and Memoization)?

Fibonacci series is a sequence where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, ...

There are multiple ways to compute Fibonacci numbers, including:

Excessive Recursion (Inefficient)
Recursion with Memoization (Efficient)
Using a Loop (Iterative)

1. Excessive Recursion

When a function repeatedly calls itself with the same parameters, it leads to excessive recursion.
This results in redundant calculations and high time complexity O(2ⁿ).

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(5) << endl;  // Output: 5
}

O(2ⁿ) (Exponential, inefficient for large n)

2. Recursion with Memoization (Optimized)

Memoization stores previously computed values to avoid redundant calculations.
This reduces the time complexity from O(2ⁿ) to O(n).

// Recursive Memoization Approach
int memo[100];  // Array to store computed values

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // If already computed, return it
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    fill_n(memo, 100, -1); // Initialize memoization array with -1
    cout << fib(5) << endl;  // Output: 5
}

O(n) (Efficient, avoids redundant calculations)

3. Iterative (Using a Loop)

The most efficient way to compute Fibonacci is using an iterative loop.
This avoids recursion overhead.

int fib(int n) {
    if (n <= 1) return n;

    int first = 0, second = 1, next;
    for (int i = 2; i <= n; i++) {
        next = first + second;
        first = second;
        second = next;
    }
    return next;
}
int main() {
    cout << fib(5) << endl;  // Output: 5
}

O(n) (Most efficient, no recursion overhead)

How to find ⁿCɾ Combination or Selection Formula?

This is a method to determine how many ways we can select a subset from a given set of objects.
The combination formula is used to compute the number of ways we can select a subset: [ C(n, r) = \frac{n!}{r! \cdot (n - r)!} ]
Using recursion, this problem can be solved using Pascal's Triangle.

Combination Formula

Mathematical Representation: [ C(n, r) = C(n-1, r-1) + C(n-1, r) ]
Base Case:
- If r == 0 or n == r, then C(n, r) = 1.

Recursive

The recursive method follows Pascal’s Triangle.
It makes recursive calls from bottom to top, reducing the problem size.

int C(int n, int r) {
    if (r == 0 || n == r) {
        return 1;
    }
    return C(n - 1, r - 1) + C(n - 1, r);
}
int main() {
    cout << C(5, 3) << endl;  // Output: 10
}

Loop

int fac(int n){
    if(n == 0){
        return 1;
    }
    return fac(n - 1) * n;
}
int C(int n, int r) {
    int n_fac, r_fac, b_fac;

    n_fac = fac(n);
    r_fac = fac(r);
    b_fac = fac(n - r);

    return n_fac / (r_fac * b_fac);
};
int main() {
    cout << C(5, 3);
}

⬆ Back to Top

How to Solve the Tower of Hanoi Problem?

The Tower of Hanoi is a classic recursion-based problem involving three rods (towers) and n disks.
Rules of the game:
1. Only one disk can be moved at a time.
2. A disk can only be placed on top of another larger disk.
3. The goal is to move all disks from Tower 1 to Tower 3, using Tower 2 as a helper.
Understanding the Problem
- Given:
- n disks initially stacked in ascending size order on Tower 1.
- Tower 2 (Helper).
- Tower 3 (Destination).
Objective: Move all n disks from Tower 1 → Tower 3 following the rules.
The problem follows a divide-and-conquer approach:
1. Move n-1 disks from Tower 1 → Tower 2 (using Tower 3).
2. Move the largest disk from Tower 1 → Tower 3.
3. Move n-1 disks from Tower 2 → Tower 3 (using Tower 1).

int TOH(int n, int A, int B, int C) {

    if(n > 0){
        TOH(n - 1, A, C, B);
        cout << "( " << A << ", " << C << " )" << endl;
        TOH(n - 1, B, A, C);
    }
};
int main() {
    cout << TOH(4, 1, 2, 3);
}

⬆ Back to Top

How to find the Number of Ways in an n X m Matrix?

Problem Statement:

Given an n × m matrix, find the number of ways to move from the top-left corner to the bottom-right corner.
You can only move right or down.

Approach:

If n == 1 or m == 1, there is only one way to reach the destination (either all right moves or all down moves).
This forms our base case.
The total number of ways to reach (n, m) is the sum of:
- Ways to reach (n-1, m) (moving down).
- Ways to reach (n, m-1) (moving right).

int countWays(int n, int m) {
    if (n == 1 || m == 1) {
        return 1; // Base case: Only one way to move
    }
    return countWays(n - 1, m) + countWays(n, m - 1);
}
int main() {
    cout << countWays(3, 3) << endl;  // Output: 6
}

O(2ⁿ⁺ᵐ) (Exponential due to overlapping subproblems).

⬆ Back to Top

Linked List

What is a Linked List?

A linked list is a collection of nodes where each node consists of:

Some data
A link (pointer) to the next node in the sequence

The first node is known as the head of the linked list.

OR

A linked list is a dynamic, linear data structure with a dynamic size. Let’s break these properties down:

Dynamic Data Structure
- Unlike arrays, which have a fixed size, linked lists use dynamic memory allocation (new and delete in C++).
- Nodes are created and deleted as needed, making memory management efficient.
Linear Data Structure
- Elements (nodes) in a linked list are arranged sequentially.
- Each node points to the next node, making traversal straightforward but requiring sequential access.
Dynamic Size
- The size of a linked list can grow or shrink at runtime without the need for reallocation or resizing.

⬆ Back to Top

How Does a Linked List Work?

Each node in the linked list contains two components:

Data: Stores the actual value.
Pointer: Points to the next node in the sequence.

The last node in the list points to NULL, indicating the end of the list.

⬆ Back to Top

What is a Self-Referential Structure?

A self-referential structure in C++ is a structure (or class) that contains a pointer (or reference) to another instance of the same structure. This concept is fundamental for creating linked data structures such as linked lists, trees, and graphs.

struct Node {
    int data;
    Node* next; // Pointer to another Node
};

⬆ Back to Top

Understanding Node Structure

Each node in a linked list typically occupies 4 bytes:

2 bytes for data (assuming int is 2 bytes)
2 bytes for the pointer to the next node

struct Node {
    int data;   // Data of the node
    Node* next; // Pointer to next node
};

⬆ Back to Top

What are the Common Conditions in a Linked List?

Pointer Assignments:

q = p; → Whatever is stored in p, assign it to q.
q = p->next; → Store p's next node in q.
p = p->next; → Move p to the next node.

Conditional Checks:

if (p == 0) → Check if p is 0 (empty).
if (p == NULL) → Equivalent to checking if p is NULL.
if (!p) → Another way to check if p is NULL.
if (p != NULL) → Check if p is not NULL.
if (p != 0) → Another way to check if p is not empty.
if (p) → Equivalent to if (p != NULL).
if (p->next == NULL) → Check if p is the last node.
if (p->next != NULL) → Check if p has a next node.

⬆ Back to Top

How to Create a Linked List?

class Node {
    public:
        int data;
        Node *next;
};

Node *head = NULL;

void create(int A[], int n) {
    Node *temp, *tail;
    head = new Node;
    head->data = A[0];
    head->next = 0;
    tail = head;
    for(int i = 1; i < n; i++) {
        temp = new Node;
        temp->data = A[i];
        temp->next = 0;
        tail->next = temp;  // Link the tail node to the new node
        tail = temp; // Update tail to point to the new node
    }
}

int main() {
    int A[] = {0, 5, 10, 15, 20};
    create(A, 5);
    // display(head);
    // reverseDisplay(head);
}

⬆ Back to Top

How to Display a Linked List?

void display(Node *p) {
    if (p != NULL) {
        cout << p->data << " ";
        display(p->next);
    }
}

⬆ Back to Top

How to Reverse Display a Linked List?

void reverseDisplay(Node *p) {
    if (p != NULL) {
        reverseDisplay(p->next);
        cout << p->data << " ";
    }
}

⬆ Back to Top

What is the Time Complexity of Linked List Operations?

Time complexity is O(n). Since recursion uses the stack, its total activation records are n+1. Both space and time complexity are O(n).

⬆ Back to Top

How to Count Nodes in a Linked List?

In this case, time complexity is O(n) and space complexity is O(1).

void count(Node *p){
    int counter = 0;
    while(p != NULL){
        counter++;
        p = p->next;
    }
    cout << "Total nodes: " << counter;
}

OR

int count(Node *p){
    if(p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

int count(Node *p){
    int x = 0;
    if(p){
        x = count(p->next);
        return x + 1;
    } else {
        return x;
    }
}

In this case, both time and space complexity is O(n).

⬆ Back to Top

How to Find the Sum of Elements in a Linked List?

int sum(Node *p){
    int sums = 0;
    while(p != NULL){
        sums += p->data;
        p = p->next;
    }
    cout << "Sum: " << sums;

    if(p == 0){
        return 0;
    } else {
        return sum(p->next) + p->data;
    }
}

⬆ Back to Top

How to Find the Maximum Element in a Linked List?

int maxElement(Node *p){
    int max = 0;
    if(p == 0){
        return 0;
    } else {
        max = maxElement(p->next);
        if(max < p->data){
            return p->data;
        } else {
            return max;
        }
    }
}

OR

int maxElement(Node *p){
    int max = 0;
    while(p != NULL){
        if(max < p->data)
            max = p->data;
        p = p->next;
    }
    cout << "Maximum: " << max;
}

OR

int maxElement(Node *p){
    int max = 0;
    if(p == 0)
        return 0;
    max = maxElement(p->next);
    return max < p->data ? p->data : max;
}

⬆ Back to Top

How to Apply Linear Search in a Linked List?

Iterative

Node* linearSearch(Node *p, int num){
  while(p != NULL){
      if(p->data == num)
          return p;
      p = p->next;
  }
  return nullptr;
}

Recursive

Node* linearSearch(Node *p, int num){
  if(p == nullptr)
      return nullptr;
  if(p->data == num)
      return p;
  return linearSearch(p->next, num);
}

⬆ Back to Top

What is Move to Head in a Linked List?

Move-to-head optimizes linear search by moving frequently searched elements to the front, reducing search time for repeated queries.

int search(Node *temp, int key){
    Node *prev = nullptr;
    while(temp != NULL){
        if(temp->data == key){
            if(prev){
                prev->next = temp->next;
                temp->next = head;
                head = temp;
            }
            return 1;
        }
        prev = temp;
        temp = temp->next;
    }
}

⬆ Back to Top

What is Move to Transposition?

Move-to-transposition swaps the searched node with its previous node to improve search efficiency over time.

Node* search(Node *p, int key) {
    Node *prev = nullptr, *prevPrev = nullptr;
    while (p != nullptr) {
        if (p->data == key) {
            if (prev != nullptr) {
                if (prevPrev != nullptr) {
                    prevPrev->next = p;
                } else {
                    head = p;
                }
                prev->next = p->next;
                p->next = prev;
            }
            return p;
        }
        prevPrev = prev;
        prev = p;
        p = p->next;
    }
    return nullptr;
}

⬆ Back to Top

How to Insert a Node in a Linked List?

Insert at Start (Before First Node)

void insertAtStart(Node *&head, int num){
    Node *p = new Node;
    p->data = num;
    p->next = head;
    head = p;
}

Insert at Given Position

void insertAtPosition(Node *&head, int num, int position){
    Node *temp = new Node;
    temp->data = num;
    if(position == 0){
        temp->next = head;
        head = temp;
        return;
    }
    Node *p = head;
    for(int i = 0; i < position - 1 && p; i++){
        p = p->next;
    }
    if(p){
        temp->next = p->next;
        p->next = temp;
    }
}

Insert at Last

void insertAtLast(Node *&head, Node *&tail, int num){
    Node *temp = new Node;
    temp->data = num;
    temp->next = nullptr;
    if(head == nullptr){
        head = tail = temp;
    } else {
        tail->next = temp;
        tail = temp;
    }
}

Insert in Sorted Order (Using Three Pointers)

void insertSort(Node *&head, int n) {
    Node *temp = new Node;
    temp->data = n;
    temp->next = nullptr;
    if (head == nullptr || head->data >= n) {
        temp->next = head;
        head = temp;
        return;
    }
    Node *p = head, *q = nullptr;
    while (p != nullptr && p->data < n) {
        q = p;
        p = p->next;
    }
    temp->next = p;
    q->next = temp;
}

Insert in Sorted Order (Using Two Pointers)

void insertSort(Node *&head, int n) {
    Node *temp = new Node;
    temp->data = n;
    temp->next = nullptr;
    if (head == nullptr || head->data >= n) {
        temp->next = head;
        head = temp;
        return;
    }
    Node *p = head;
    while (p->next != nullptr && p->next->data < n) {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
}

⬆ Back to Top

How to Delete a Node in a Linked List?

Delete node except first

A node in a linked list can be deleted by updating the previous node’s next pointer to skip the node being deleted. The below method efficiently deletes a node at a given position.

void deleteNodeAtPosition(int position){
  Node *p = head;
  Node *q = nullptr;
  int x;

  for(int i = 0; i < position - 1; i++){
      q = p;
      p = p->next;
  }

  q->next = p->next;
  x = p->data;
  delete p;
}

Delete node from anywhere

This method handles deletion from anywhere in the list, including the first node. It ensures that memory is properly freed while maintaining list integrity.

void deleteNode(int position){
  Node *temp = head;
  int x;

  if(position == 1){
      x = head->data;
      temp = head;
      head = head->next;
      delete temp;
  }else{
      Node *p = head;
      Node *q = nullptr;
      for(int i = 0; i < position - 1 && p; i++){
          q = p;
          p = p->next;
      }
      if(p){
          q->next = p->next;
          x = p->data;
          delete p;
      }
  }
}

⬆ Back to Top

How to Check if a List is Sorted or Not?

Checking if a linked list is sorted involves traversing the list and comparing adjacent node values to ensure they are in non-decreasing order.

void isSorted() {
    Node *temp = head;
    if (temp == nullptr) {
        cout << "List is empty\n";
        return;
    }

    while (temp->next != nullptr) {
        if (temp->data > temp->next->data) {
            cout << "Not Sorted\n";
            return;
        }
        temp = temp->next;
    }
    cout << "Sorted\n";
}

Alternative Approach

This method uses a variable to keep track of the last visited node’s value to ensure proper ordering.

void isSorted() {
    Node *temp = head;
    int x = -32768;

    if (temp == nullptr) {
        cout << "List is empty\n";
        return;
    }

    while (temp != nullptr) {
        if(temp->data < x){
            cout << "Not Sorted";
            return;
        }
        x = temp->data;
        temp = temp->next;
    }
    cout << "Sorted\n";
}

⬆ Back to Top

How to Remove Duplicates from a Linked List?

Duplicate removal involves comparing consecutive nodes and deleting redundant ones while maintaining list integrity.

void removeDuplicates(){
    Node *p = head;
    Node *q = head->next;

    while(q != nullptr){
        if(p->data == q->data){
            p->next = q->next;
            delete q;
            q = p->next;
        }else{
            p = q;
            q = q->next;
        }
    }
}

⬆ Back to Top

How to Reverse a Linked List?

Reversing elements

This method stores the linked list elements in an array and rewrites them in reverse order.

void reverseElements(int n){
    int Arr[n];
    Node *temp = head;
    int i = 0;
    while(temp != nullptr){
        Arr[i++] = temp->data;
        temp = temp->next;
    }
    temp = head;
    i--;
    while(temp != nullptr){
        temp->data = Arr[i--];
        temp = temp->next;
    }
}

Reversing links

Instead of reversing data, this method modifies the node pointers to reverse the linked list efficiently.

void reverseLinks(){
    Node *p = head;
    Node *q = nullptr;
    Node *r = nullptr;
    while(p != nullptr){
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    head = q;
}

Recursive Reverse for Linked List

This method reverses the linked list using recursion, updating the head when the last node is reached.

void recursiveReverse(Node *q, Node *p){
    if(p != nullptr){
        recursiveReverse(p, p->next);
        p->next = q;
    }else{
        head = q;
    }
}

⬆ Back to Top

How to Concatenate Linked Lists?

Concatenation involves linking the last node of the first linked list to the head of the second linked list. The second list is then set to nullptr to avoid redundancy.

void concatenate() {
    if (head1 == nullptr) {
        head1 = head2;
    } else {
        Node *p = head1;
        while(p->next != nullptr) {
            p = p->next;
        }
        p->next = head2;
    }
    head2 = nullptr;
}

⬆ Back to Top

How to Merge Linked Lists?

Merging two linked lists combines them into a single sorted linked list without using an extra array. This approach efficiently merges two sorted lists into one.

Using Three Linked Lists

void merge() {
    if(head1->data < head2->data) {
        head3 = tail3 = head1;
        head1 = head1->next;
        tail3->next = NULL;
    } else {
        head3 = tail3 = head2;
        head2 = head2->next;
        tail3->next = NULL;
    }

    while(head1 != NULL && head2 != NULL) {
        if(head1->data < head2->data) {
            tail3->next = head1;
            tail3 = head1;
            head1 = head1->next;
        } else {
            tail3->next = head2;
            tail3 = head2;
            head2 = head2->next;
        }
    }

    if(head1 != NULL) tail3->next = head1;
    else tail3->next = head2;
}

Using Two Linked Lists

void merge() {
    Node *mergedHead = nullptr;
    Node *mergedTail = nullptr;

    if (head1->data < head2->data) {
        mergedHead = mergedTail = head1;
        head1 = head1->next;
    } else {
        mergedHead = mergedTail = head2;
        head2 = head2->next;
    }
    mergedTail->next = NULL;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data < head2->data) {
            mergedTail->next = head1;
            mergedTail = head1;
            head1 = head1->next;
        } else {
            mergedTail->next = head2;
            mergedTail = head2;
            head2 = head2->next;
        }
    }

    if (head1 != NULL) mergedTail->next = head1;
    else mergedTail->next = head2;

    head1 = mergedHead;
}

Complete Merging Linked List (Code):

class Node{
    public:
        int data;
        Node *next;
};

Node *head1 = NULL; Node *tail1 = NULL;
Node *head2 = NULL; Node *tail2 = NULL;

void createList1(int A[], int n){
    head1 = new Node;
    head1->data = A[0];
    head1->next = NULL;
    tail1 = head1;

    for(int i = 1; i < n; i++){
        Node *temp = new Node;
        temp->data = A[i];
        temp->next = NULL;
        tail1->next = temp;
        tail1 = temp;
    }
}

void createList2(int B[], int n){
    head2 = new Node;
    head2->data = B[0];
    head2->next = NULL;
    tail2 = head2;

    for(int i = 1; i < n; i++){
        Node *temp = new Node;
        temp->data = B[i];
        temp->next = NULL;
        tail2->next = temp;
        tail2 = temp;
    }
}

void merge(){
    Node *head3 = NULL; Node *tail3 = NULL;
    if(head1->data < head2->data){
        head3 = tail3 = head1;
        head1 = head1->next;
        tail3->next = NULL;
    }else{
        head3 = tail3 = head2;
        head2 = head2->next;
        tail3->next = NULL;
    }

    while(head1 != NULL && head2 != NULL){
        if(head1->data < head2->data){
            tail3->next = head1;
            tail3 = head1;
            head1 = head1->next;
            tail3->next = NULL;
        }else{
            tail3->next = head2;
            tail3 = head2;
            head2 = head2->next;
            tail3->next = NULL;
        }
    }

    if(head1 != NULL){
        tail3->next = head1;
    }else{
        tail3->next = head2;
    }

    head1 = head3;
}

void displayList(Node *temp){
    while(temp != NULL){
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main()
{
    int A[] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};

    createList1(A, 5);
    createList2(B, 5);

    displayList(head1);
    displayList(head2);

    merge();
    displayList(head1);
}

⬆ Back to Top

### How to Find the Middle of a Linked List?

Finding the middle of a linked list is useful in various algorithms like binary search on a linked list. We use the slow and fast pointer approach where the fast pointer moves twice as fast as the slow pointer.

Node* findMiddle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

⬆ Back to Top

How to Detect and Remove a Loop in a Linked List?

A loop in a linked list occurs when the last node points back to a previous node instead of nullptr. We can detect a loop using Floyd’s Cycle Detection Algorithm (slow and fast pointer method).

Detecting a Loop

bool isLoop(Node *temp) {
    Node *p, *q;
    p = q = temp;
    do {
        p = p->next;
        q = q->next;
        q = q ? q->next : NULL;
    } while(p && q && p != q);
    return p == q;
}

Removing a Loop

Once a loop is detected, we find the node where the loop starts and break it.

void removeLoop(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (slow == fast) {
        slow = head;
        while (slow->next != fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        fast->next = NULL;
    }
}

⬆ Back to Top

Circular Linked List

What is a Circular Linked List?

A circular linked list is a linked list in which the last node points back to another node, forming a circular structure.

There is no first or last node; instead, we call one node the head.
Allows circular traversal of nodes.
Only forward direction traversal is possible.
A circular linked list can never be NULL.
Unlike singly linked lists that end at NULL, circular lists end at HEAD.

⬆ Back to Top

What are the conditions for a Circular Linked List?

At least one node must be present.
The last node should always point back to the head.
Traversal should end when the head is reached again.

⬆ Back to Top

What are the benefits of a Circular Linked List over a Singly Linked List?

A Circular Linked List (CLL) is a variation of a Singly Linked List (SLL) where the last node points back to the first node, forming a loop instead of terminating with NULL. This structure eliminates the need for NULL pointers and allows for continuous traversal.

Advantages of Circular Linked List Over Singly Linked List

A Circular Linked List provides multiple benefits over a Singly Linked List, especially in scenarios requiring continuous operations.

1. Efficient Traversal

In a Singly Linked List, traversal requires checking for NULL, leading to extra conditions.
In a Circular Linked List, there are no NULL pointers, making traversal seamless.

2. Faster Insertions at Head

Inserting at the head of a Singly Linked List requires updating the last node’s pointer, which may need full traversal (O(n) complexity).
In a Circular Linked List, the last node is already connected to the first node, enabling constant time insertion (O(1)) at the head.

3. Continuous Navigation

Since there is no NULL endpoint, a Circular Linked List supports cyclic operations efficiently.
Ideal for applications that require looping through data, such as music playlists, scheduling algorithms, and multiplayer gaming turns.

4. Memory Optimization

No NULL pointers are required, saving memory.
Suitable for memory-constrained environments where optimizing pointer storage is necessary.

5. Ideal for Queue Implementations

Circular Queues can be implemented using a Circular Linked List without needing complex reallocation.
Buffer Management Systems use Circular Linked Lists to cycle through available memory efficiently.

Comparison Table: Circular Linked List vs. Singly Linked List

Feature	Singly Linked List	Circular Linked List
End Node	Points to `NULL`	Points to Head
Traversal	Stops at `NULL`	Loops infinitely
Insertion at Head	Requires full traversal to update last node (`O(n)`)	O(1) (Last node already points to head)
Deletion	Extra handling for last node	Easier as no `NULL` check needed
Usage in Scheduling	Less efficient	Ideal for round-robin scheduling
Buffer/Memory Optimization	Not memory-efficient	Eliminates `NULL` pointers, saving space

Real-World Applications of Circular Linked Lists

Circular Linked Lists are widely used in various practical applications:

Round-Robin CPU Scheduling – Efficiently cycles through processes.
Multiplayer Games – Used to manage turn-based player actions.
Music & Video Playlists – Enables seamless looping.
Networking (Token Ring Topology) – Ensures continuous data transmission.
Memory Buffers – Used in real-time applications for buffering data.

⬆ Back to Top

How to create a Circular Linked List?

void createCircularList(int A[], int n) {
    head = new Node;
    head->data = A[0];
    head->next = head;
    tail = head;

    for(int i = 1; i < n; i++) {
        Node *temp = new Node;
        temp->data = A[i];
        temp->next = tail->next;
        tail->next = temp;
        tail = temp;
    }
}

OR

struct Node {
    int data;
    Node* next;
};

// Function to insert at the end of a Circular Linked List
void insert(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;

    if (head == nullptr) {
        head = newNode;
        head->next = head; // Point to itself (single-node circular list)
        return;
    }

    Node* temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->next = head; // Make it circular
}

// Function to delete a node in Circular Linked List
void deleteNode(Node*& head, int key) {
    if (head == nullptr) return;

    Node *current = head, *prev = nullptr;

    // Case 1: If head node is to be deleted
    if (head->data == key) {
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = head->next;
        head = head->next;
        delete current;
        return;
    }

    // Case 2: Searching for the node
    do {
        prev = current;
        current = current->next;
    } while (current != head && current->data != key);

    if (current->data == key) {
        prev->next = current->next;
        delete current;
    }
}

// Function to display the Circular Linked List
void display(Node* head) {
    if (head == nullptr) return;

    Node* temp = head;
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);

    cout << "(Back to Head)" << endl;
}

int main() {
    Node* head = nullptr;

    insert(head, 10);
    insert(head, 20);
    insert(head, 30);

    cout << "Circular Linked List: ";
    display(head);

    deleteNode(head, 20);
    cout << "After Deletion: ";
    display(head);
}

⬆ Back to Top

How to display a Circular Linked List?

void displayCircularList(Node *temp) {
    do {
        cout << temp->data << " ";
        temp = temp->next;
    } while(temp != head);
    // static int flag = 0;
    // if(temp != head || flag == 0){
    //     flag = 1;
    //     cout << temp->data << " ";
    //     displayCircularList(temp->next);
    // }
    // flag = 0;
}

⬆ Back to Top

How to insert a node in a Circular Linked List?

Inserting at Head

New node is inserted before the current head.
Head is updated to the new node.

void insertAtStart(int n) {
    Node *temp = new Node;
    temp->data = n;
    temp->next = head;

    Node *p = head;
    do {
        p = p->next;
    } while(p->next != head);

    p->next = temp;
    head = temp; // Moving head
}

Inserting at Any Position Except Head

The new node is inserted at the given position.

void insertAtPosition(int n, int position) {
    Node *temp = new Node;
    Node *p = head;

    for(int i = 1; i < position - 1; i++)
        p = p->next;

    temp->data = n;
    temp->next = p->next;
    p->next = temp;
}

Inserting at Any Position (Handling Empty List)

If the list is empty, create a new node as head.
Otherwise, insert at the given position.

void insertInCircularLinkedList(int data, int position) {
    Node *p = head;
    Node *temp = new Node;
    temp->data = data;

    if(position == 0) {
        if(head == NULL) {
            head = temp;
            head->next = head;
            tail = head;
        } else {
            temp->next = head;
            while(p->next != head) p = p->next;
            p->next = temp;
            head = temp;
        }
    } else {
        for(int i = 0; i < position - 1; i++) p = p->next;
        temp->next = p->next;
        p->next = temp;
    }
}

⬆ Back to Top

How to delete a node from a Circular Linked List?

Deleting from Head

void deleteAtHead(){
    Node *p = head;
    while(p->next != head){
        p = p->next;
    }
    p->next = head->next;
    delete head;
    head = p->next;
}

Deleting from any Position

void deleteAtPosition(int position){
    Node *p = head;
    Node *q;
    for(int i = 0; i < position - 2; i++) p = p->next;

    q = p->next;
    p->next = q->next;

    cout << "Deleted node: " << q->data << endl;
    delete q;
}

Deleting Anywhere in Circular Linked List

void deleteAtPosition(int position){
    Node *p = head;
    Node *q = NULL;

    if(position == 1){
        while(p->next != head) p = p->next;
        if(p == head){ // Only one node in list
            delete head;
            head = NULL;
        }else{
            p->next = head->next;
            delete head;
            head = p->next;
        }
    }else{
        for(int i = 0; i < position - 1; i++){
            q = p;
            p = p->next;
        }
        q->next = p->next;
    }
}

⬆ Back to Top

Doubly Linked List

What is a Doubly Linked List?

This is similar to website navigation (back and forward arrows), allowing traversal in both directions.
Also, like a mobile contacts list, you can move up and down easily.
The benefit of using a doubly linked list is that it allows efficient traversal in either direction.
It is structured like a singly linked list (with head and tail), but the difference is that each node connects both forward and backward.

⬆ Back to Top

What are the benefits of a Doubly Linked List over a Singly or Circular Linked List?

Doubly linked lists allow traversal in both directions, unlike singly linked lists, which only allow forward movement.
They make deletion and insertion at both ends more efficient compared to singly linked lists.
Useful for implementing LRU caches and undo/redo functionalities in applications.

⬆ Back to Top

How to create a Doubly Linked List?

class Node{
    public:
        Node *prev;
        int data;
        Node *next;
};

Node *head = NULL;
Node *last = NULL;

void createDoubleLinkedList(int A[], int n){
    head = new Node;
    head->prev = NULL;
    head->data = A[0];
    head->next = NULL;
    last = head;

    for(int i = 1; i < n; i++){
        Node *temp = new Node;
        temp->prev = last;
        temp->data = A[i];
        temp->next = last->next;
        last->next = temp;
        last = temp;
    }
}

⬆ Back to Top

How to display a Doubly Linked List?

void display(){
    Node *p = head;
    while(p){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

⬆ Back to Top

How to insert a node in a Doubly Linked List?

Before Head

void insertBeforeFirstNode(int data){
    Node *temp = new Node;
    temp->prev = NULL;
    temp->data = data;
    temp->next = head;
    head->prev = temp;
    head = temp;
}

At Position

void insertAtPosition(int data, int position){
    Node *p = head;
    for(int i = 0; i < position - 1; i++){
        p = p->next;
    }
    Node *temp = new Node;
    temp->next = p->next;
    temp->data = data;
    temp->prev = p;
    if(p->next)
        p->next->prev = temp;
    p->next = temp;
}

⬆ Back to Top

How to delete a node from a Doubly Linked List?

Delete from Head

void deleteAtHead(){
    Node *p = head;
    head = head->next;
    if(head) head->prev = NULL;
    cout << "Deleted Head: " << p->data << endl;
    delete p;
}

Delete at Any Position

void deleteAtPosition(int position){
    Node *p = head;
    for(int i = 0; i < position - 1; i++){
        p = p->next;
    }
    p->prev->next = p->next;
    if(p->next)
        p->next->prev = p->prev;
    cout << "Deleted Element: " << p->data << endl;
    delete p;
}

⬆ Back to Top

How to reverse a Doubly Linked List?

Iterative

void Reverse2(Node *p){
    Node *q = NULL, *r = NULL;
    Node *first = p;
    while(p != NULL){
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    first = q;
}

Recursive

void reverse(Node *q, Node *p){
    if(p){
        reverse(p, p->next);
        p->next = q;
    } else {
        head = q;
    }
}

Optimized Iterative

void reverse(){
    Node* p = head;
    Node* temp;
    while (p != nullptr){
        temp = p->next;
        p->next = p->prev;
        p->prev = temp;
        p = p->prev;

        if (p->next == nullptr){
            p->next = p->prev;
            p->prev = nullptr;
            head = p;
            break;
        }
    }
}

⬆ Back to Top

Circular Doubly Linked List

What is a Circular Doubly Linked List?

A Circular Doubly Linked List is a linked list where nodes are connected in both forward and backward directions, forming a circular structure.
It allows bidirectional traversal and maintains a circular connection, meaning the last node connects back to the first node.

⬆ Back to Top

What are the benefits of a Circular Doubly Linked List over Singly, Circular, and Doubly Linked

Lists?

Efficient navigation: Can traverse in both directions.
No NULL pointers: Unlike singly and doubly linked lists, no NULL pointers are required for the first and last nodes.
Circular nature: Useful in applications that require continuous looping over data (e.g., scheduling, buffering, etc.).

⬆ Back to Top

What are the conditions for a Circular Doubly Linked List?

If there is only one node, both prev and next pointers must point to itself.
The last node's next pointer should point to the head.
The head node's prev pointer should point to the last node.

⬆ Back to Top

How to create a Circular Doubly Linked List?

void create(int A[], int n) {
    head = new Node;
    head->data = A[0];
    head->prev = head;
    head->next = head;
    tail = head;

    for (int i = 1; i < n; i++) {
        Node *temp = new Node;
        temp->data = A[i];
        temp->prev = tail;
        temp->next = head;

        tail->next = temp;
        head->prev = temp;
        tail = temp;
    }
}

⬆ Back to Top

How to display a Circular Doubly Linked List?

void display(Node *head) {
    Node *p = head;
    if (!head) return;

    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != head);
    cout << endl;
}

⬆ Back to Top

Give a Brief Comparison of Linked List Types?

Space Complexity:

Linear & Circular Linked List: Uses n space for pointers (1 pointer per node).
Doubly Linear & Doubly Circular Linked List: Uses 2n space (2 pointers per node).

Insertion:

Inserting at head is O(1) in all linked lists except circular linked list.
Doubly linked list head insertion takes O(n) time.
Inserting at any other position takes between O(1) and O(n).

Deletion:

Circular Linked List head deletion takes O(n), others take O(1).
Deleting a node given a pointer to it requires O(n) time in some cases.

Best Choice:

Doubly Circular Linked List is optimal as it allows movement in both directions but uses more space.

⬆ Back to Top

Comparison of Linked List with Array?

Feature	Array	Linked List
Memory Allocation	Stack/Heap	Heap Only
Size	Fixed	Dynamic
Space Utilization	May have unused space	Uses exact required space + pointer overhead
Access	Random `O(1)`	Sequential `O(n)`
Insert/Delete	Right-side `O(1)`, Left-side `O(n)`	Head `O(1)`, Tail `O(n)`
Binary Search	`O(log n)`	Inefficient `O(n log n)`
Sorting	Efficient	Merge & Insertion Sort work best

When to Use?
- Use Arrays when fixed size is known and fast access is required.
- Use Linked Lists when dynamic size and frequent insertions/deletions are needed.

⬆ Back to Top

How to find the intersection point of two Linked Lists?

To find the intersection point of two linked lists, we use two stacks to store the nodes and compare them.

class Node{
public:
    int data;
    Node* next;
};

Node* head = new Node;
Node* second = new Node;

void create(int A[], int n){
    Node* temp;
    Node* tail;

    head->data = A[0];
    head->next = nullptr;
    tail = head;

    for (int i=1; i<n; i++){
        temp = new Node;
        temp->data = A[i];
        temp->next = nullptr;
        tail->next = temp;
        tail = temp;
    }
}

void createSecond(int A[], int n, Node* p){
    Node* temp;
    Node* tail;

    second->data = A[0];
    second->next = nullptr;
    tail = second;

    for (int i=1; i<n; i++){
        temp = new Node;
        temp->data = A[i];
        temp->next = nullptr;
        tail->next = temp;
        tail = temp;
    }
    tail->next = p;
}

void Intersection(Node* p, Node* q){
    stack<Node*> stk1, stk2;
    while (p) { stk1.push(p); p = p->next; }
    while (q) { stk2.push(q); q = q->next; }

    Node* r;
    while (!stk1.empty() && !stk2.empty() && stk1.top() == stk2.top()){
        r = stk1.top();
        stk1.pop();
        stk2.pop();
    }
    cout << "Intersecting Node: " << r->data << endl;
}

int main() {
    int A[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
    create(A, sizeof(A)/sizeof(A[0]));

    Node* temp = head;
    int i = 5;
    while (i > 0){ temp = temp->next; i--; }

    int B[] = {2, 4, 6, 8, 10};
    createSecond(B, sizeof(B)/sizeof(B[0]), temp);

    Intersection(head, second);
}

Create Two Linked Lists - One normal and one that intersects at a certain node.
Use Stacks - Push all nodes of both lists onto two separate stacks.
Find Common Node - Compare stack tops and find the last common node.
Output the Intersection Node.

Time Complexity: `O(N + M)`, where `N` and `M` are the lengths of the linked lists.

⬆ Back to Top

Stack

What is Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element inserted into the stack is the first one to be removed. Real-world examples of a stack include:

Parking lot where cars are parked in a single lane.
Stack of plates where the last plate placed is the first to be removed.
Recursion calls in programming utilize stacks for execution order.

⬆ Back to Top

What is ADT with Stack?

Abstract Data Type (ADT) defines the data representation and operations of a stack without specifying the internal implementation. A stack ADT consists of:

Data: Elements stored with a pointer to the top.
Operations:
- isEmpty(): Checks if the stack is empty.
- isFull(): Checks if the stack is full.
- push(x): Inserts an element at the top.
- pop(): Removes and returns the top element.
- peek(pos): Retrieves an element at a specific position.
- stackTop(): Returns the topmost element without removing it.

⬆ Back to Top

What are the benefits of Stack over Array and Linked List?

Efficient insertion and deletion: Stacks provide O(1) time complexity for push and pop operations, whereas arrays may require shifting elements.
Memory management: Stacks are used for function calls, managing recursion, and backtracking efficiently.
No extra pointers: Unlike linked lists, stacks don’t require additional memory for pointers when implemented using arrays.

⬆ Back to Top

How to implement Stack using Array?

Stacks can be implemented using an array by maintaining a top pointer to track the last inserted element. This implementation ensures constant-time push and pop operations.

#include<iostream>
using namespace std;

class Stack {
    public:
        int *A;
        int size;
        int top;
};

Stack s;

void isFull() {
    if (s.top == s.size - 1)
        cout << "Stack is full" << endl;
    else
        cout << "Stack is not full" << endl;
}

void isEmpty() {
    if (s.top == -1)
        cout << "Stack is empty" << endl;
    else
        cout << "Stack is not empty" << endl;
}

void push(int n) {
    if (s.top + 1 == s.size) {
        cout << "Stack Overflow" << endl;
        return;
    }
    s.top++;
    s.A[s.top] = n;
}

void pop() {
    if (s.top == -1) {
        cout << "Stack Underflow" << endl;
        return;
    }
    int x = s.A[s.top];
    cout << "Popped element: " << x << endl;
    s.top--;
}

int main() {
    cout << "Enter size of stack: ";
    cin >> s.size;
    s.top = -1;
    s.A = new int[s.size];

    push(1);
    push(2);
    push(3);
    pop();
    isFull();
    isEmpty();
    delete[] s.A;
}

⬆ Back to Top

How to implement Stack using Linked List?

A stack can also be implemented using a linked list, where each node contains a value and a pointer to the next node. The top pointer tracks the latest added node, allowing constant-time insertion and deletion.

#include<iostream>
using namespace std;

class Node {
    public:
        int data;
        Node *next;
};

Node *top = NULL;

bool isEmpty() {
    return top == NULL;
}

void push(int n) {
    Node *temp = new Node;
    temp->data = n;
    temp->next = top;
    top = temp;
}

void pop() {
    if (isEmpty()) {
        cout << "Stack is empty" << endl;
        return;
    }
    Node *temp = top;
    top = top->next;
    cout << "Deleted node: " << temp->data << endl;
    delete temp;
}

void display() {
    Node *temp = top;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    push(5);
    push(4);
    push(3);
    pop();
    display();
}

⬆ Back to Top

How to solve Parenthesis Matching problem using Stack?

Concept: The problem requires checking whether every opening bracket in an expression has a corresponding closing bracket, ensuring that the expression is balanced.

Use a stack to store opening brackets and match them with closing brackets.
If a bracket has only one operand, it is not properly parenthesized.
The procedure does not check for logical correctness beyond balance.

#include <iostream>
using namespace std;
class Node{
    public:
        char exp;
        Node *next;
};

Node *top = NULL;

void push(char a){
    Node *temp = new Node;
    temp->exp = a;
    temp->next = top;
    top = temp;
}

void pop(){
    Node *temp = top;
    top = top->next;
    delete temp;
}

bool isEmpty(){
    return top == NULL;
}

bool isBalance(char exp[]){
    for(int i = 0; exp[i] != '\0'; i++){
        if(exp[i] == '(')
            push(exp[i]);
        else if(exp[i] == ')'){
            if(isEmpty())
                return false;
            pop();
        }
    }
    return isEmpty();
}

int main()
{
    char exp[] = "((a+b)*(a-b))";
    cout << isBalance(exp);
}

⬆ Back to Top

How to check balance with conditions of matching brackets?

Concept: Expands on parenthesis matching by handling {}, [], and () while ensuring correct pair matching.

#include <iostream>
using namespace std;

class Node{
    public:
        char data;
        Node *next;
};
Node *top = NULL;

void push(char data){
    Node *temp = new Node;
    temp->data = data;
    temp->next = top;
    top = temp;
}

char pop(){
    Node *temp = top;
    char poppedData = temp->data;
    top = top->next;
    delete temp;
    return poppedData;
}

bool isEmpty(){
    return top == NULL;
}

bool isBalanced(char expression[]){
    for(int i = 0; expression[i] != '\0'; i++){
        if(expression[i] == '[' || expression[i] == '{' || expression[i] == '(')
            push(expression[i]);
        else if(expression[i] == ']' || expression[i] == '}' || expression[i] == ')'){
            if(isEmpty())
                return false;
            char x = pop();
            if((expression[i] == ')' && x != '(') ||
               (expression[i] == ']' && x != '[') ||
               (expression[i] == '}' && x != '{'))
                return false;
        }
    }
    return isEmpty();
}

int main(){
    char expression[] = "[a(b+c)*(b)+d]";
    cout << isBalanced(expression);
}

⬆ Back to Top

How to perform Infix to Postfix Conversion using Stack?

Concept

Infix: Operand Operator Operand (e.g., a + b).
Postfix: Operand Operand Operator (e.g., a b +).
Converting infix to postfix allows for single-pass evaluation without operator precedence ambiguity.

Infix to Postfix Conversion Associativity and Unary Operators

All unary operators have right-to-left precedence.

Infix to Postfix Conversion Methods

Method 1

Ignore operand; if an operator is found, push it onto the stack.
From the second occurrence onward, check the precedence of the operator.
If precedence is less or equal, pop the operator from the stack.
If at the end of the expression, empty the stack.

Method 2

Every symbol from the expression is pushed onto the stack.
Operands are given higher precedence.
A for loop does not work because we don't move forward when pushing onto the stack.

class Node {
public:
    char data;
    Node *next;
};

Node *top = NULL;

void push(char a) {
    Node *temp = new Node;
    if (!temp)
        cout << "Stack is empty";
    else {
        temp->data = a;
        temp->next = top;
        top = temp;
    }
}

char pop() {
    Node *temp = top;
    char p = -1;
    if (temp == NULL)
        cout << "Stack is empty";
    else {
        p = temp->data;
        top = top->next;
        delete temp;
    }
    return p;
}

bool isEmpty() {
    return top == NULL;
}

char getTop() {
    return top->data;
}

bool isOperand(char x) {
    return !(x == '+' || x == '-' || x == '*' || x == '/');
}

int pre(char x) {
    if (x == '+' || x == '-')
        return 1;
    else
        return 2;
}

char *convert(const char *exp) {
    char *postfix = new char[strlen(exp) + 1];
    int i = 0, j = 0;
    while (exp[i] != '\0') {
        if (isOperand(exp[i]))
            postfix[j++] = exp[i++];
        else {
            if (isEmpty() || pre(exp[i]) > pre(getTop()))
                push(exp[i++]);
            else {
                postfix[j++] = pop();
            }
        }
    }
    while (!isEmpty()) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';
    return postfix;
}

int main() {
    const char *infix = "a-b+c-e*s";
    char *postfix = convert(infix);
    cout << "Postfix: " << postfix;
    delete[] postfix;
}

Infix to Postfix Conversion with Associativity and Parentheses

The in and out stack is used:
- Left to Right: Increase
- Right to Left: Decrease

class Node {
public:
    char data;
    Node *next;
};

Node *top = NULL;

void push(char z) {
    Node *temp = new Node;
    if (!temp)
        cout << "Stack is full" << endl;
    else {
        temp->data = z;
        temp->next = top;
        top = temp;
    }
}

char pop() {
    Node *temp = top;
    char poppedData = '\0';
    if (temp == NULL)
        cout << "Stack is empty" << endl;
    else {
        poppedData = temp->data;
        top = top->next;
        delete temp;
    }
    return poppedData;
}

bool isEmpty() {
    return top == NULL;
}

bool isOperand(char x) {
    return !(x == '+' || x == '-' || x == '*' || x == '/' || x == '^' || x == '(' || x == ')');
}

int inStack(char x) {
    if (x == '+' || x == '-') return 2;
    if (x == '*' || x == '/') return 4;
    if (x == '^') return 5;
    if (x == '(') return 0;
    if (x == ')') return -1;
    return -1;
}

int outStack(char x) {
    if (x == '+' || x == '-') return 1;
    if (x == '*' || x == '/') return 3;
    if (x == '^') return 6;
    if (x == '(') return 7;
    if (x == ')') return 0;
    return -1;
}

char* infixToPostfix(const char* data) {
    int length = strlen(data);
    char* postfix = new char[length + 1];
    int i = 0, j = 0;

    while (data[i] != '\0') {
        if (isOperand(data[i])) {
            postfix[j++] = data[i++];
        } else {
            if (isEmpty() || outStack(data[i]) > inStack(top->data)) {
                push(data[i++]);
            } else if (data[i] == ')') {
                while (top->data != '(') {
                    postfix[j++] = pop();
                }
                pop(); // Pop '('
                i++;
            } else {
                postfix[j++] = pop();
            }
        }
    }
    while (!isEmpty()) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';
    return postfix;
}

int main() {
    const char *data = "(a+b)*c-d^e^f";
    char *postfix = infixToPostfix(data);
    cout << "Postfix: " << postfix << endl;
    delete[] postfix;
}

Evaluation of Postfix Expression

Maintain a stack.
When popping, the topmost value is the right operand and the next value is the left operand.

class Node{
public:
    int data;
    Node *next;
};

Node *top = NULL;

void push(int x){
    Node *temp = new Node;
    if(!temp)
        cout << "Stack is full" << endl;
    else{
        temp->data = x;
        temp->next = top;
        top = temp;
    }
}

int pop(){
    Node *temp = top;
    int poppedData = -1;
    if(top == NULL)
        cout << "Stack is empty";
    else{
        poppedData = temp->data;
        top = top->next;
        delete temp;
    }
    return poppedData;
}

⬆ Back to Top

Queue

What is Queue?

A queue is a linear data structure that follows the FIFO (First In First Out) principle. The element inserted first is removed first, like a queue of people waiting in line.

Examples:

People standing in line at a ticket counter.
WhatsApp message queue.
Task scheduling in operating systems.

⬆ Back to Top

What is ADT in Queue?

ADT (Abstract Data Type) defines the logical structure and operations for a queue.

ADT Components:

Data:
- Storage (Array or Linked List)
- Front (for Deletion)
- Rear (for Insertion)
Operations:
- Enqueue(x): Insert an element.
- Dequeue(): Remove an element.
- IsEmpty(): Check if queue is empty.
- IsFull(): Check if queue is full.
- First(): Get the first element.
- Last(): Get the last element.

⬆ Back to Top

What are the benefits of Queue over Array, Linked List, and Stack?

Compared to Arrays: Queue allows efficient O(1) enqueue and dequeue operations without shifting elements.
Compared to Linked List: Queue has a defined structure (Front and Rear), making it easier for sequential access.
Compared to Stack: Queue follows FIFO, which is necessary for many real-world applications like scheduling.

⬆ Back to Top

How to implement Queue using Array?

// Using Single Pointer
class Queue {
public:
    int* data;
    int size;
    int rear;

    Queue(int sz) : size(sz), rear(-1) {
        data = new int[size];
    }

    ~Queue() {
        delete[] data;
    }
};

Queue* q;

void enqueue(int x) {
    if (q->rear < q->size - 1) {
        q->rear++;
        q->data[q->rear] = x;
    } else {
        cout << "Queue is full" << endl;
    }
}

int dequeue() {
    int x = -1;
    if (q->rear == -1)
        cout << "Queue is empty" << endl;
    else {
        x = q->data[0];
        for (int i = 0; i < q->rear; i++) {
            q->data[i] = q->data[i + 1];
        }
        q->rear--;
    }
    return x;
}

void display() {
    cout << "Elements in Queue: ";
    for (int i = 0; i <= q->rear; i++)
        cout << q->data[i] << " ";
    cout << endl;
}

int main() {
    int size;
    cout << "Enter size: ";
    cin >> size;

    q = new Queue(size);

    enqueue(5);
    enqueue(10);
    enqueue(15);
    cout << "Dequeued element: " << dequeue() << endl;
    enqueue(20);
    cout << "Dequeued element: " << dequeue() << endl;
    display();

    delete q;
}

⬆ Back to Top

What are the drawbacks of Queue?

Fixed size in Arrays: A queue implemented using an array has a fixed size, leading to overflow issues.
Wasted space: Deleted elements' space cannot be reused in a normal queue.
Queue appears empty but is full: If front and rear pointers reach the end, no more elements can be inserted.

⬆ Back to Top

What is Circular Queue?

A circular queue overcomes the issue of wasted space by making the queue wrap around when the end is reached.

class CircularQueue {
public:
    int size, *A, front, rear;
    CircularQueue(int sz) : size(sz), front(0), rear(0) {
        A = new int[size];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }

    void enqueue(int x) {
        if (isFull())
            cout << "Queue is full" << endl;
        else {
            rear = (rear + 1) % size;
            A[rear] = x;
        }
    }

    void dequeue() {
        if (isEmpty())
            cout << "Queue is empty" << endl;
        else
            front = (front + 1) % size;
    }

    void display() {
        int i = (front + 1) % size;
        while (i != (rear + 1) % size) {
            cout << A[i] << " ";
            i = (i + 1) % size;
        }
        cout << endl;
    }

    ~CircularQueue() {
        delete[] A;
    }
};

int main() {
    CircularQueue q(5);
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    q.display();
    q.dequeue();
    q.display();
    q.enqueue(6);
    q.display();
}

⬆ Back to Top

How to implement Queue using Linked List?

class Node {
public:
    int data;
    Node* next;
};

class Queue {
private:
    Node *front, *rear;
public:
    Queue() { front = rear = NULL; }

    void enqueue(int x);
    void dequeue();
    void display();
};

void Queue::enqueue(int x) {
    Node* temp = new Node();
    temp->data = x;
    temp->next = NULL;
    if (rear) rear->next = temp;
    else front = temp;
    rear = temp;
}

void Queue::dequeue() {
    if (!front) return;
    Node* temp = front;
    front = front->next;
    delete temp;
    if (!front) rear = NULL;
}

void Queue::display() {
    Node* temp = front;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

⬆ Back to Top

DEQueue (Double Ended Queue)

What is DEQueue?

A DEQueue (Double-Ended Queue) is a type of queue in which elements can be inserted and removed from both ends. Unlike a simple queue, which follows the FIFO (First In, First Out) principle, DEQueue allows more flexible data manipulation.

⬆ Back to Top

What are the Restrictions in DEQueue?

Implemented using both array and linked list: DEQueue can be implemented using either arrays or linked lists, providing different efficiency trade-offs.
Does not strictly follow FIFO: Unlike a standard queue, DEQueue allows insertion and deletion from both ends.
Front and Rear Pointers: In a simple queue, the rear pointer is used for insertion, and the front pointer is used for deletion. However, in DEQueue, both pointers can be used for insertion and deletion operations.

Types of Restrictions in DEQueue

Input Restricted DEQueue
- Insertion is restricted to only the rear end.
- Deletion can be performed from both front and rear.
Output Restricted DEQueue
- Deletion is restricted to only the front end.
- Insertion can be performed from both front and rear.

Visual Representation

Front ---> [ 10 | 20 | 30 | 40 ] <--- Rear
Operations:
- Insert at Front: Adds element at the beginning.
- Insert at Rear: Adds element at the end.
- Delete from Front: Removes element from the beginning.
- Delete from Rear: Removes element from the end.

DEQueue Implementation (Array-Based)

#define SIZE 5  // Max size of DEQueue

class DEQueue {
private:
    int arr[SIZE];
    int front, rear;

public:
    DEQueue() {
        front = -1;
        rear = -1;
    }

    bool isFull() {
        return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
    }

    bool isEmpty() {
        return (front == -1);
    }

    void insertFront(int value) {
        if (isFull()) {
            cout << "Queue is Full!\n";
            return;
        }
        if (front == -1) { // First element
            front = rear = 0;
        } else if (front == 0) {
            front = SIZE - 1;
        } else {
            front--;
        }
        arr[front] = value;
    }

    void insertRear(int value) {
        if (isFull()) {
            cout << "Queue is Full!\n";
            return;
        }
        if (rear == -1) { // First element
            front = rear = 0;
        } else if (rear == SIZE - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = value;
    }

    void deleteFront() {
        if (isEmpty()) {
            cout << "Queue is Empty!\n";
            return;
        }
        if (front == rear) {
            front = rear = -1;
        } else if (front == SIZE - 1) {
            front = 0;
        } else {
            front++;
        }
    }

    void deleteRear() {
        if (isEmpty()) {
            cout << "Queue is Empty!\n";
            return;
        }
        if (front == rear) {
            front = rear = -1;
        } else if (rear == 0) {
            rear = SIZE - 1;
        } else {
            rear--;
        }
    }
};

int main() {
    DEQueue dq;
    dq.insertRear(10);
    dq.insertRear(20);
    dq.insertFront(5);
    dq.deleteRear();
    dq.deleteFront();
    return 0;
}

DEQueue Implementation (Linked List-Based)

struct Node {
    int data;
    Node* next;
    Node* prev;
};

class DEQueue {
private:
    Node* front;
    Node* rear;

public:
    DEQueue() {
        front = rear = NULL;
    }

    bool isEmpty() {
        return front == NULL;
    }

    void insertFront(int value) {
        Node* newNode = new Node{value, front, NULL};
        if (isEmpty()) {
            rear = newNode;
        } else {
            front->prev = newNode;
        }
        front = newNode;
    }

    void insertRear(int value) {
        Node* newNode = new Node{value, NULL, rear};
        if (isEmpty()) {
            front = newNode;
        } else {
            rear->next = newNode;
        }
        rear = newNode;
    }

    void deleteFront() {
        if (isEmpty()) {
            cout << "Queue is Empty!\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front) front->prev = NULL;
        else rear = NULL;
        delete temp;
    }

    void deleteRear() {
        if (isEmpty()) {
            cout << "Queue is Empty!\n";
            return;
        }
        Node* temp = rear;
        rear = rear->prev;
        if (rear) rear->next = NULL;
        else front = NULL;
        delete temp;
    }
};

int main() {
    DEQueue dq;
    dq.insertRear(10);
    dq.insertFront(5);
    dq.deleteFront();
    dq.deleteRear();
}

Operation	Array-Based	Linked List-Based
Insert Front	✅ O(1)	✅ O(1)
Insert Rear	✅ O(1)	✅ O(1)
Delete Front	✅ O(1)	✅ O(1)
Delete Rear	✅ O(1)	✅ O(1)
Memory Usage	Limited (fixed size)	Dynamic (grows/shrinks)

⬆ Back to Top

Priority Queue

What is Priority Queue?

A Priority Queue is a data structure similar to a regular queue but with an added feature: each element has a priority. The element with the highest priority is dequeued before elements with lower priority.

⬆ Back to Top

What does it mean by Limited Set of Priorities?

A Limited Set of Priorities means that only a fixed number of priority levels are available for elements. This is commonly used in operating systems and scheduling algorithms where tasks are assigned predefined priority levels.

⬆ Back to Top

What does it mean by Element Priority? Explain methods.

Element Priority refers to the rule that determines the order of element processing in a priority queue.

Methods:

Unordered List or Queue
- Elements are inserted in the same order as they arrive.
- The highest-priority element is searched and removed.
- Time Complexity: Insertion: O(1), Deletion: O(n).
Ordered List or Queue
- Elements are inserted in increasing priority order.
- The highest-priority element is always at the end and is removed first.
- Time Complexity: Insertion: O(n), Deletion: O(1).
Heap-based Priority Queue
- Uses a Min-Heap or Max-Heap for efficient priority management.
- Time Complexity: Both Insertion and Deletion: O(log n).

⬆ Back to Top

How to implement Queue using 2 Stacks?

A Queue using two stacks can be implemented in two ways:

Push Efficient Approach
- The enqueue operation is performed in O(1).
- The dequeue operation moves all elements from stack1 to stack2 and removes the top.
Pop Efficient Approach
- The enqueue operation moves all elements to stack1.
- The dequeue operation is performed in O(1).

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s1, s2;
public:
    void enqueue(int x) {
        s1.push(x);
    }

    int dequeue() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int topVal = s2.top();
        s2.pop();
        return topVal;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << endl;
    cout << q.dequeue() << endl;
}

// Implementation of a Priority Queue (Min-Heap)

#include <iostream>
#include <queue>
using namespace std;

class PriorityQueue {
    priority_queue<int, vector<int>, greater<int>> pq; // Min-Heap

public:
    void push(int val) {
        pq.push(val);
    }

    int pop() {
        if (pq.empty()) {
            cout << "Priority Queue is empty!" << endl;
            return -1;
        }
        int topVal = pq.top();
        pq.pop();
        return topVal;
    }

    bool isEmpty() {
        return pq.empty();
    }
};

int main() {
    PriorityQueue pq;
    pq.push(10);
    pq.push(5);
    pq.push(20);
    pq.push(1);

    cout << "Elements in Priority Queue (Min-Heap):\n";
    while (!pq.isEmpty()) {
        cout << pq.pop() << " ";
    }
    cout << endl;
    return 0;
}

This implementation uses a Min-Heap priority queue, where the smallest element is always dequeued first.

Trees

What is a Tree?

A Tree is a hierarchical data structure composed of nodes connected by edges. Unlike graphs, trees follow a parent-child relationship and do not contain cycles.

A tree is defined as a non-linear data structure where nodes are arranged in a specific hierarchical order.

Each node may have multiple child nodes.
Nodes that do not have children are called Leaf Nodes (also known as Terminal Nodes or External Nodes).
If a tree has n nodes, it always has (n-1) edges.
Trees can be traversed using Preorder, Inorder, Levelorder or Postorder traversal techniques.

⬆ Back to Top

What are the terminologies in a tree?

2.1. What is the Root Node?

The topmost node in the tree with no parent.
Every tree has exactly one root.

    A (Root)
   / \
  B   C

2.2. What are Edges in a Tree?

A connection between two nodes.
Each edge represents a direct relationship (parent-child) between nodes.

    A
   / \  (Edges)
  B   C

2.3. What is a Parent and Child Node?

A Parent node has one or more child nodes directly connected by edges.
A Child node is any node that has a parent.

    A (Parent)
   /   \
  B     C (Children)

2.4. What are Siblings in a Tree?

Nodes that share the same parent.

    A
   / \
  B   C  (Siblings)

2.5. What is a Subtree?

A portion of the tree that can be considered as a smaller tree within the larger tree.

    A
   / \
  B   C
 / \
D   E   (Subtree rooted at B)

2.6. What are Descendants in a Tree?

All nodes that can be reached from a given node, including its children and further levels.

    A
   / \
  B   C
 / \
D   E  (Descendants of B: D and E)

2.7. What are Ancestors in a Tree?

All nodes along the path from a given node up to the root.

    A (Ancestor of D)
   / \
  B   C
 /
D  (Node)

2.8. What is the Degree of a Node?

The number of children a node has.

    A (Degree = 2)
   / \
  B   C

2.9. What is the Degree of a Tree?

The maximum degree of any node in the tree.

Example: If the highest number of children a node has is 3, then the tree’s degree is 3.

2.10. What is a Leaf Node (External Node)?

A node with no children (degree = 0).

    A
   / \
  B   C  (Leaf nodes)

2.11. What is an Internal Node (Non-Leaf Node)?

A node that has at least one child.

    A (Internal Node)
   / \
  B   C

2.12. What is Level in a Tree?

The depth of a node in the tree, starting from the root at level 1.

Level 1: A
Level 2: B, C
Level 3: D, E
    A
   / \
  B   C
 / \
D   E

2.13. What is the Height of a Tree?

The length of the longest path from the root to a leaf node.
Height starts from 0 (when counting from the root to the farthest leaf).

Height = 2
    A
   / \
  B   C
 / \
D   E

2.14. What is a Forest in Tree Data Structures?

A collection of disjoint trees.
If the root of a tree is removed, the remaining components form a forest.

Before removing root:
    A
   / \
  B   C

After removing A:
  B   C  (Forest)

2.15. What is the Maximum Number of Nodes in a Tree?

A tree with height h has a maximum of 2^(h+1) - 1 nodes.
Example: If h = 3, maximum nodes = 2^(3+1) - 1 = 15.

       A
      / \
     B   C
    /|   |\
   D E   F G
  /
 H (Height = 3, Max Nodes = 15)

⬆ Back to Top

What is a Binary Tree?

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

⬆ Back to Top

How to find Height or Nodes of a Binary Tree if one is given?

If Height (h) is given:
- Minimum Nodes: n = h + 1
- Maximum Nodes: n = 2^(h+1) - 1
If Nodes (n) are given:
- Minimum Height: h = log₂(n+1) - 1
- Maximum Height: h = n - 1

⬆ Back to Top

What is a Strict Binary Tree?

A strict binary tree is a binary tree where each node has either exactly 2 children or no children at all (i.e., a node cannot have only one child).

⬆ Back to Top

How to find Height or Nodes of a Strict Binary Tree if one is given?

If Height (h) is given:
- Minimum Nodes: n = 2h + 1
- Maximum Nodes: n = 2^(h+1) - 1
If Nodes (n) are given:
- Minimum Height: h = log₂(n+1) - 1
- Maximum Height: h = (n - 1) / 2
Relation Between Internal and External Nodes:
- External Nodes = Internal Nodes + 1

⬆ Back to Top

What are n-ary trees?

An n-ary tree is a tree where each node can have at most n children. n is the maximum degree of any node in the tree.

⬆ Back to Top

What are strict n-ary trees?

A strict n-ary tree is a tree where each node has either exactly n children or none at all.

Find Height or Nodes of a Strict n-ary Tree?

If Height (h) is given:
- Minimum Nodes: n = m * h + 1
- Maximum Nodes: n = (m^(h+1) - 1) / (m - 1)
If Nodes (n) are given:
- Minimum Height: h = logₘ[(n * (m - 1)) + 1] - 1
- Maximum Height: h = (n - 1) / m
Relation Between Internal and External Nodes:
- External Nodes = (m - 1) * Internal Nodes + 1

⬆ Back to Top

How to implement a Binary Tree using an array?

Elements are stored level by level.
Indexing Relation:
- If element is at index i:
  - Left Child = 2 * i
  - Right Child = 2 * i + 1
  - Parent = i / 2

Example:

       1 (index 1)
      /   \
     2(2)  3(3)
    / \    / \
  4(4) 5(5) 6(6) 7(7)

Stored as [1, 2, 3, 4, 5, 6, 7] in an array.

⬆ Back to Top

How to implement a Binary Tree using a linked list?

Each node consists of three fields:
- Left Child Pointer
- Data Value
- Right Child Pointer

Node Structure (C++ Example):

struct Node {
    int data;
    Node* left;
    Node* right;
};

For n nodes, we will have n + 1 NULL pointers.

⬆ Back to Top

Relations and Formulas in Binary Trees

1. Catalan Number (For Unique Binary Trees)

Unlabeled Nodes: (2nCn) / (n + 1)
Labeled Nodes: (2nCn * n!) / (n + 1)

2. Relation Between Internal and External Nodes in a Binary Tree

deg(0) = deg(2) + 1 (Leaf Nodes = Internal Nodes + 1)

Visual Representations of Tree Concepts

Binary Tree Example:

Strict Binary Tree Example:

n-ary Tree Example (n=3):

         A
       / | \
      B  C  D
     /|  |\   \
    E F  G H   I

Binary Tree Representation in an Array:

 Index:  1  2  3  4  5  6  7
 Values: A  B  C  D  E  F  G

Linked List Representation of a Node:

[Left Child Pointer] <- Data -> [Right Child Pointer]

⬆ Back to Top

What are the Types of Binary Trees?

Binary trees come in different types based on their structure. Two important types are Full Binary Tree and Complete Binary Tree.

1. What is a Full Binary Tree?

A Full Binary Tree is a tree where every node has either 0 or 2 children. This means:

Each node is either a leaf node (no children) or has exactly two children.
There are no nodes with only one child.
A full binary tree of height h has a maximum of 2^(h+1) - 1 nodes.

Every node has 0 or 2 children.
A full binary tree is always a complete binary tree.

2. What is a Complete Binary Tree?

A Complete Binary Tree is a binary tree where:

All levels are completely filled except possibly for the last level.
The last level nodes are filled from left to right without skipping any position.

If stored in an array, there should be no blank spaces between elements.
A complete binary tree of height h will be a full binary tree up to height h - 1.
At height h, nodes are filled from left to right without skipping any positions.
A full binary tree is always a complete binary tree, but a complete binary tree may or may not be a full binary tree.

Type	Definition	Properties
Full Binary Tree	Every node has 0 or 2 children	No node has only one child, Always a complete binary tree
Complete Binary Tree	All levels except last are fully filled; last level is filled left to right	If stored in an array, there should be no empty spaces in between

⬆ Back to Top

What are the Types/Different Methods of Tree Traversals?

Tree traversal is a process of visiting all the nodes in a tree in a specific order. There are several methods of tree traversal, each serving a different purpose.

Types of Tree Traversals:

PreOrder Traversal: Visit the node first, then traverse the left subtree, followed by the right subtree. Order: Node → Left → Right
InOrder Traversal: Traverse the left subtree first, visit the node, then traverse the right subtree. Order: Left → Node → Right
PostOrder Traversal: Traverse the left subtree first, then the right subtree, and visit the node last. Order: Left → Right → Node
LevelOrder Traversal: Traverse the tree level by level, from top to bottom and left to right. Order: Level by Level

Methods to Perform Tree Traversal

Method 1: Attaching Lines to the Bottom from Left, Middle, or Right

Attach lines under the node and process nodes from left to right.

Method 2: Drawing Small Lines to the Side and Moving

Draw small connector lines to represent branches and traverse accordingly.

Method 3: Finger Traversal (Manual Approach)

Place your finger on the tree and move through it. If a node is completely visible, write it down following traversal rules.

PreOrder Traversal:

      A
     / \
    B   C
   / \   \
  D   E   F

Output: A B D E C F

InOrder Traversal:

      A
     / \
    B   C
   / \   \
  D   E   F

Output: D B E A C F

PostOrder Traversal:

      A
     / \
    B   C
   / \   \
  D   E   F

Output: D E B F C A

LevelOrder Traversal:

      A
     / \
    B   C
   / \   \
  D   E   F

Output: A B C D E F

⬆ Back to Top

1. What is Preorder Traversal? Explain and provide code for both recursive and iterativees.

Preorder traversal visits nodes in the following order:

Visit the root node.
Traverse the left subtree.
Traverse the right subtree.

Recursive

void preorder(Node *t){
    if(t != nullptr){
        cout << t->data << " ";
        preorder(t->leftChild);
        preorder(t->rightChild);
    }
}

Iterative

Take a stack.
Start at the Root:
- Print the data.
- Store the root's address in the stack.
- Move to the left child.
Now follow the repeating procedure:
- Print the data of the current node.
- Move to the left child.
- If the left child is NULL, pop the address from the stack to go back to that node.
- Then move to the right child.
- If the right child is also NULL, pop the next address from the stack and continue the procedure.

void preorder(Node *t){
    stack<Node*> stk;
    while(t != nullptr || !stk.empty()){
        if(t != nullptr){
            cout << t->data << " ";
            stk.push(t);
            t = t->leftChild;
        }else{
            t = stk.top();
            stk.pop();
            t = t->rightChild;
        }
    }
}

⬆ Back to Top

2. What is Inorder Traversal? Explain and provide code for both recursive and iterativees.

Inorder traversal visits nodes in the following order:

Traverse the left subtree.
Visit the root node.
Traverse the right subtree.

Recursive

void inorder(Node *t){
    if(t != nullptr){
        inorder(t->leftChild);
        cout << t->data << " ";
        inorder(t->rightChild);
    }
}

Iterative

Take a stack.
Start at the Root:
- Store the root's address in the stack.
- Move to the left child.
Now follow the repeating procedure:
- Keep moving to the left child and storing the address in the stack.
- If the left child is NULL, pop the address from the stack to go back to that node.
- Print the data of the current node.
- Move to the right child.
- If the right child is NULL, pop the next address from the stack and continue the procedure.

void inorder(Node *t){
    stack<Node*> stk;
    while(t != nullptr || !stk.empty()){
        if(t != nullptr){
            stk.push(t);
            t = t->leftChild;
        }else{
            t = stk.top();
            stk.pop();
            cout << t->data << " ";
            t = t->rightChild;
        }
    }
}

⬆ Back to Top

3. What is Postorder Traversal? Explain and provide code for both recursive and iterativees.

Postorder traversal visits nodes in the following order:

Traverse the left subtree.
Traverse the right subtree.
Visit the root node.

Recursive

void postorder(Node *p){
    if(p != nullptr){
        postorder(p->leftChild);
        postorder(p->rightChild);
        cout << p->data << " ";
    }
}

Iterative

Take a queue of type Node*.
Start at the Root:
- Print the root's data.
- Push the root's address into the queue.
Now follow the repeating procedure:
- While the queue is not empty:
  - Remove (pop) the front node's address from the queue.
  - For the current node:
    - If it has a left child, print its data and push the left child's address into the queue.
    - If it has a right child, print its data and push the right child's address into the queue.

void postorder(Node *p){
    stack<long int> stk;
    long int temp;
    while (p != nullptr || ! stk.empty()){
        if (p != nullptr){
            stk.emplace((long int)p);
            p = p->leftChild;
        } else {
            temp = stk.top();
            stk.pop();
            if (temp > 0){
                stk.emplace(-temp);
                p = ((Node*)temp)->rightChild;
            } else {
                cout << ((Node*)(-1 * temp))->data << " ";
                p = nullptr;
            }
        }
    }
}

⬆ Back to Top

4. What is Level Order Traversal? Explain and provide code for both recursive and iterativees.

Level-order traversal visits nodes level by level:

Start from the root.
Process all nodes at the current level before moving to the next level.

void levelorder(Node *p){
    queue<Node *> q;
    cout << p->data << " ";
    q.push(p);
    while(!q.empty()){
        p = q.front();
        q.pop();
        if(p->leftChild){
            cout << p->leftChild->data << " ";
            q.push(p->leftChild);
        }
        if(p->rightChild){
            cout << p->rightChild->data << " ";
            q.push(p->rightChild);
        }
    }
}

⬆ Back to Top

Total activation records for these traversals: 2n + 1
Time Complexity: O(n) for all methods

How to implement/create a Binary Tree?

A Binary Tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. To create a Binary Tree dynamically, we use a queue-based approach:

Initialize a queue that will store node pointers.
Create the root node, set its left and right children as NULL, and insert it into the queue.
Iterate through the queue:
- Extract a node from the queue.
- Prompt the user for its left child. If it exists, create the node and add it to the queue.
- Prompt the user for its right child. If it exists, create the node and add it to the queue.

This ensures a level-order creation of the binary tree.

class Node{
  public:
      Node *leftChild;
      int data;
      Node *rightChild;
};

Node *root;

void create(){
    Node *p, *t;
    int x;
    queue<Node*> q;
    cout << "Enter root value: ";
    cin >> x;
    root = new Node;
    root->data = x;
    root->leftChild = root->rightChild = nullptr;
    q.push(root);

    while(!q.empty()){
        p = q.front();
        q.pop();
        cout << "Enter left child value: ";
        cin >> x;
        if(x != -1){
            t = new Node;
            t->data = x;
            t->leftChild = t->rightChild = nullptr;
            p->leftChild = t;
            q.push(t);
        }
        cout << "Enter right child value: ";
        cin >> x;
        if(x != -1){
            t = new Node;
            t->data = x;
            t->leftChild = t->rightChild = nullptr;
            p->rightChild = t;
            q.push(t);
        }
    }
}

#include <iostream>
#include <queue>
using namespace std;

class Node {
    public:
        Node *lChild;
        int data;
        Node *rChild;
};

Node *root = NULL;

// Function to create a Binary Tree
void create() {
    int x;
    queue<Node*> q;
    Node *p, *t;
    cout << "Enter root value: ";
    cin >> x;
    root = new Node;
    root->data = x;
    root->lChild = root->rChild = NULL;
    q.push(root);

    while (!q.empty()) {
        p = q.front();
        q.pop();

        // Left Child
        cout << "Enter left child of " << p->data << " (-1 for no child): ";
        cin >> x;
        if (x != -1) {
            t = new Node;
            t->data = x;
            t->lChild = t->rChild = NULL;
            p->lChild = t;
            q.push(t);
        }

        // Right Child
        cout << "Enter right child of " << p->data << " (-1 for no child): ";
        cin >> x;
        if (x != -1) {
            t = new Node;
            t->data = x;
            t->lChild = t->rChild = NULL;
            p->rChild = t;
            q.push(t);
        }
    }
}

// Function to perform Level Order Traversal
void levelorder(Node *p) {
    if (p == NULL) return;

    queue<Node *> q;
    cout << p->data << " ";
    q.push(p);

    while (!q.empty()) {
        p = q.front();
        q.pop();

        if (p->lChild) {
            cout << p->lChild->data << " ";
            q.push(p->lChild);
        }
        if (p->rChild) {
            cout << p->rChild->data << " ";
            q.push(p->rChild);
        }
    }
}

// Function to count the total number of nodes in the tree
int count(Node *p) {
    if (p == NULL) return 0;
    int x = count(p->lChild);
    int y = count(p->rChild);
    return x + y + 1;
}

int main() {
    create();
    cout << "Level Order Traversal: ";
    levelorder(root);
    cout << "\nTotal Nodes: " << count(root) << endl;
}

Explanation

1. Creating a Binary Tree (create function)

A queue is used to manage the nodes in a FIFO (First-In-First-Out) manner.
The root node is created first and stored in the queue.
For each node dequeued:
- The left child is created if a valid value is entered.
- The right child is created if a valid value is entered.
This process continues until all levels of the tree are filled.

2. Level Order Traversal (levelorder function)

A queue is used to print the tree level by level.
Nodes are processed in FIFO order, ensuring nodes are visited left to right at each level.
Each dequeued node’s children are enqueued for further processing.

3. Counting Nodes (count function)

Uses recursion to count the nodes in the tree.
Returns 1 + left subtree count + right subtree count.

Enter root value: 10
Enter left child of 10 (-1 for no child): 20
Enter right child of 10 (-1 for no child): 30
Enter left child of 20 (-1 for no child): 40
Enter right child of 20 (-1 for no child): -1
Enter left child of 30 (-1 for no child): -1
Enter right child of 30 (-1 for no child): 50
Enter left child of 40 (-1 for no child): -1
Enter right child of 40 (-1 for no child): -1
Enter left child of 50 (-1 for no child): -1
Enter right child of 50 (-1 for no child): -1

Level Order Traversal: 10 20 30 40 50
Total Nodes: 5

Queue-based approach ensures level-order insertion.
Linked list-based structure dynamically allocates memory for nodes.
Recursive node count efficiently computes the total nodes.
Time Complexity:
- Creation: O(n) (each node is processed once).
- Traversal: O(n) (each node is visited once).
- Counting Nodes: O(n) (each node is counted once).

Additional Tasks

Implement Preorder, Inorder, Postorder traversals.
Add delete node functionality.
Implement tree height calculation.
Convert into Binary Search Tree (BST) for efficient searching.

⬆ Back to Top

How to generate a Tree from Traversal?

Can We Generate a Unique Tree from Traversal?

No, a single unique tree is not always possible.

Given a single traversal (Preorder, Inorder, or Postorder), we cannot determine a unique tree. Multiple trees can be formed from the same order.
Given Preorder and Postorder together, a unique tree is still not possible.
We can generate a unique tree only if we have:
- Inorder + Preorder
- Inorder + Postorder

Understanding Tree Generation

1. Single Order

Preorder
- If only Preorder is given, we cannot construct a unique tree.
- Given n elements, the number of possible trees is ²ⁿCⁿ / (n + 1) (Catalan number).
Inorder
- Similarly, a unique tree cannot be formed.
Postorder
- Again, a unique tree cannot be constructed.

2. Combining Traversals

Preorder + Inorder OR Postorder + Inorder
- A unique tree can be generated using these combinations.

Method to Generate a Tree

Identify the first node from Preorder (or last node from Postorder), which will be the root.
Find this node's position in the Inorder sequence.
Divide Inorder into left and right subtrees based on this root node.
Recursively repeat the process for left and right subtrees.

// Tree Construction using Inorder and Preorder
struct Node {
    char data;
    Node* left;
    Node* right;
    Node(char val) : data(val), left(nullptr), right(nullptr) {}
};

int search(char arr[], int start, int end, char value) {
    for (int i = start; i <= end; i++) {
        if (arr[i] == value) return i;
    }
    return -1;
}

Node* buildTree(char inorder[], char preorder[], int inStart, int inEnd, int& preIndex) {
    if (inStart > inEnd) return nullptr;

    Node* node = new Node(preorder[preIndex++]);
    if (inStart == inEnd) return node;

    int inIndex = search(inorder, inStart, inEnd, node->data);
    node->left = buildTree(inorder, preorder, inStart, inIndex - 1, preIndex);
    node->right = buildTree(inorder, preorder, inIndex + 1, inEnd, preIndex);

    return node;
}

Single traversal alone is not enough to construct a unique tree.
Combining Inorder with either Preorder or Postorder allows us to build a unique tree.
The key idea is to identify root nodes and recursively divide subtrees based on Inorder.

⬆ Back to Top

How to Count Total Nodes, Nodes with Data, Full Nodes, Nodes with One or Two Children, Leaf Nodes, and Nodes with Exactly One Child in a Tree?

Counting Total Nodes

This follows the post-order traversal approach.
First, recursively call the function on the root node.
Traverse to the left child, then to the right child. Instead of printing, add both counts together.

int countNodes(Node *p){
    if (p == nullptr)
        return 0;
    return countNodes(p->leftChild) + countNodes(p->rightChild) + 1;
}

Counting Node Data

Instead of counting nodes with +1, sum p->data for each node.

int countNodeData(Node *p){
    if (p == nullptr)
        return 0;
    return countNodeData(p->leftChild) + countNodeData(p->rightChild) + p->data;
}

Counting Nodes with Both Children (Full Nodes)

Check if both the left and right children exist. If they do, add 1, otherwise just add the counts of both subtrees.

int countFullNodes(Node *p){
    if (p == nullptr)
        return 0;
    int count = countFullNodes(p->leftChild) + countFullNodes(p->rightChild);
    return (p->leftChild && p->rightChild) ? count + 1 : count;
}

Counting Nodes with One or Two Children

If either the left or right child exists, add 1, otherwise add both subtrees.

int countOneOrTwoChildren(Node *p){
    if (p == nullptr)
        return 0;
    int count = countOneOrTwoChildren(p->leftChild) + countOneOrTwoChildren(p->rightChild);
    return (p->leftChild || p->rightChild) ? count + 1 : count;
}

Counting Leaf Nodes

Check if both the left and right children are absent. If neither child exists, add 1, otherwise just add both subtrees.

int countLeafNodes(Node *p){
    if (p == nullptr)
        return 0;
    if (!p->leftChild && !p->rightChild)
        return 1;
    return countLeafNodes(p->leftChild) + countLeafNodes(p->rightChild);
}

Counting Nodes with Exactly One Child

Check if one child exists and the other doesn't. If so, add 1, otherwise just add both subtrees.

int countNodesWithOneChild(Node *p){
    if (p == nullptr)
        return 0;
    int count = countNodesWithOneChild(p->leftChild) + countNodesWithOneChild(p->rightChild);
    return ((p->leftChild && !p->rightChild) || (!p->leftChild && p->rightChild)) ? count + 1 : count;
}

⬆ Back to Top

Binary Search Tree (BST)

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a binary tree where each node follows the property:

Left subtree nodes contain values smaller than the node.
Right subtree nodes contain values greater than the node.
BSTs are efficient for search operations, typically taking O(log n) time in balanced trees.

⬆ Back to Top

What are the Key Properties of a Binary Search Tree (BST)?

Every node in the left subtree is smaller than the root.
Every node in the right subtree is greater than the root.
An in-order traversal of a BST produces a sorted sequence.
BSTs provide efficient insert, delete, and search operations.
The tree does not allow duplicate values.
The number of unique BSTs that can be formed with 'n' nodes is given by the Catalan number.

⬆ Back to Top

How to Search in a BST? Explain and provide code for both recursive and iterativees.

The maximum number of comparisons to find an element in a BST is proportional to the height of the tree.
The time complexity is O(h), where 'h' is the height of the tree.
The height of a binary tree ranges between log(n) and n.
In a balanced BST, the search time in the best case is O(log(n)).
In the worst case (unbalanced), the search time is O(n).

Recursive

If the root node is null, return null.
If the node's data matches the key, return the node's address.
If the node's data is smaller than the key, search the right child recursively.
If the node's data is larger than the key, search the left child recursively.
This process follows tail recursion because the recursive call is the last operation in the function.

Node* search(Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

Iterative

Use a loop to traverse the tree until the root node is null, then return null after the loop.
If the node's data matches the key, return the node's address.
If the node's data is smaller than the key, move to the right child.
If the node's data is larger than the key, move to the left child.
Unlike converting most recursive methods to iterative, in this case, no stack is needed.

Node* search(Node* root, int key) {
    while (root != NULL) {
        if (root->data == key)
            return root;
        root = (key < root->data) ? root->left : root->right;
    }
    return NULL;
}

⬆ Back to Top

How to Insert in a BST? Explain and provide code for both recursive and iterativees.

Creating a Binary Search Tree (BST) takes O(n log n) time on average.
This is because inserting each node takes O(log n) time due to the height of the tree, and you insert n nodes in total.
The log n factor comes from the time needed to find the correct position for each new node during insertion.
Therefore, the overall time complexity of creating a BST is O(n log n).

Recursive

Node* insert(Node* root, int key) {
    if (root == NULL) return new Node(key);
    if (key < root->data)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);
    return root;
}

Iterative

Node* insert(Node* root, int key) {
    Node* newNode = new Node(key);
    if (root == NULL) return newNode;
    Node* parent = NULL, *current = root;
    while (current != NULL) {
        parent = current;
        current = (key < current->data) ? current->left : current->right;
    }
    (key < parent->data) ? parent->left = newNode : parent->right = newNode;
    return root;
}

⬆ Back to Top

How to Delete a Node in a BST? Explain and provide code for both recursive and iterativees. Also, explain what a Predecessor and Successor are.

When deleting any node, its inorder predecessor or inorder successor can take its place.
We perform predecessor or successor replacement to avoid multiple modifications to the tree structure.
In some cases, multiple changes may still be necessary, especially if the node to be deleted has two children.
The time complexity for deletion depends on the height of the tree, which can range from O(log n) for balanced trees to O(n) for skewed trees.

Inorder Predecessor & Successor

Predecessor: Largest value in the left subtree.
Successor: Smallest value in the right subtree.

Steps for Deletion:

Find the node to be deleted.
If the node has no children, simply remove it.
If the node has one child, link its parent to its child.
If the node has two children, find either the inorder predecessor or successor, copy its value to the node to be deleted, and then delete the predecessor or successor.

Recursive

Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) return root->right;
        if (root->right == NULL) return root->left;
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Iterative

Node* deleteNode(Node* root, int key) {
    Node* parent = NULL, *current = root;
    while (current && current->data != key) {
        parent = current;
        current = (key < current->data) ? current->left : current->right;
    }
    if (!current) return root;
    if (!current->left || !current->right) {
        Node* temp = current->left ? current->left : current->right;
        if (!parent) return temp;
        (parent->left == current) ? parent->left = temp : parent->right = temp;
    } else {
        Node* temp = minValueNode(current->right);
        current->data = temp->data;
        current->right = deleteNode(current->right, temp->data);
    }
    return root;
}

⬆ Back to Top

How to Construct a BST from a Given Preorder Traversal?

1. Why is Preorder Traversal Used for BST Construction?

Preorder traversal is used because the first element is always the root, which helps in constructing the tree recursively.

2. Steps to Build a BST from Preorder

// Recursive
Node* buildBST(vector<int>& preorder, int& index, int min, int max) {
    if (index >= preorder.size() || preorder[index] < min || preorder[index] > max)
        return NULL;
    Node* root = new Node(preorder[index++]);
    root->left = buildBST(preorder, index, min, root->data);
    root->right = buildBST(preorder, index, root->data, max);
    return root;
}

For a binary tree, we typically need both preorder + inorder or postorder + inorder to generate the tree. However, since the inorder traversal of a BST is a sorted list, we can generate the BST from just preorder or postorder alone.

Steps to build BST from Preorder:

Create the root node and set its left and right children as NULL.
Use a stack to manage the nodes.
Iterate through the preorder sequence:
- If the next value is smaller than the current node, it becomes the left child.
- If the next value is greater, it becomes the right child of the closest ancestor with a smaller value.
This process ensures the correct BST structure with O(n) time complexity.

How BST is Constructed from Preorder Traversal?

Given Preorder: [40, 20, 10, 30, 60, 50, 70]

   40
  /  \
Step 2: 20 goes to left of 40
   40
  /
 20
Step 3: 10 goes to left of 20
   40
  /
 20
 /
10
Step 4: 30 goes to right of 20
   40
  /
 20
 /  \
10   30
Step 5: 60 goes to right of 40
   40
  /   \
 20    60
 /  \
10   30
Step 6: 50 goes to left of 60
   40
  /   \
 20    60
 /  \   /
10   30 50
Step 7: 70 goes to right of 60
   40
  /   \
 20    60
 /  \   /  \
10   30 50  70

⬆ Back to Top

What are the Drawbacks of BST and How Can They Be Solved?

1️. Uncontrolled Height

A BST can become skewed, leading to inefficient operations. If elements are inserted in sorted order, the tree degrades into a linked list.

Example of a Skewed BST:

Given Input: [10, 20, 30, 40, 50, 60, 70]

❌ Problem:

The height becomes O(n) instead of O(log n).
Operations like search, insert, and delete take O(n) time instead of O(log n).

2️. Unbalanced Cases

Some insertion sequences create a balanced tree, while others lead to an unbalanced (skewed) structure.

✅ Example 1: Balanced BST

Given Input: [40, 20, 30, 60, 50, 10, 70]

       40
      /  \
    20    60
   /  \   /  \
 10   30 50  70

✔ Advantages:

Balanced structure ensures O(log n) operations.
Efficient search, insert, and delete.

❌ Example 2: Unbalanced BST

Given Input: [10, 20, 30, 40, 50, 60, 70]

❌ Disadvantages:

Essentially a linked list.
O(n) worst-case time complexity for operations.

3️. Expectation vs Reality

Although we expect BST height to be O(log n), inserting sorted data leads to O(n) height.

Expectation	Reality
`O(log n)` height for efficient search	`O(n)` height if inserted in order
Balanced BST	Skewed BST
`O(log n)` insertion/deletion	`O(n)` insertion/deletion

4️. Performance Degradation

When a BST becomes unbalanced, its operations degrade from O(log n) to O(n).

Operation	Balanced BST (O(log n))	Unbalanced BST (O(n))
Search	✅ Fast	❌ Slow
Insert	✅ Efficient	❌ Slower
Delete	✅ Optimized	❌ Inefficient

Solution

AVL Trees

Uses rotations to maintain a balanced height.
Ensures |height(left) - height(right)| ≤ 1.
Ensures O(log n) operations.

Red-Black Trees

Uses color properties (red & black nodes) to maintain balance.
Ensures search, insert, and delete stay O(log n).

⬆ Back to Top

BST is only efficient if balanced.
Use AVL or Red-Black Trees for better performance.
Inserting sorted data into BST without balancing leads to poor efficiency.

class Node {
    public:
        Node* lChild;
        int data;
        Node* rChild;
}*root = NULL;

Node* insert(Node* p, int key) {
    Node* t = p;
    Node* r = NULL;

    if (p == NULL) {
        p = new Node;
        p->data = key;
        p->lChild = p->rChild = NULL;
        return p;
    }

    while (p != NULL) {
        r = p;

        if (p->data == key) {
            return NULL;
        }

        if (p->data > key) {
            p = p->lChild;
        } else {
            p = p->rChild;
        }
    }

    Node* newNode = new Node;
    newNode->data = key;
    newNode->lChild = newNode->rChild = NULL;

    if (r->data > key) {
        r->lChild = newNode;
    } else {
        r->rChild = newNode;
    }

    return t;
}

Node* search(Node* p, int key){
    while(p != NULL){
        if(p->data == key)
            return p;
        if(p->data > key)
            p = p->lChild;
        else
            p = p->rChild;
    }
    return NULL;
}

Node* del(Node* p, int key){
    if(p != NULL){
        if(p->data == key){
    }
}

void preorder(Node* p) {
    if (p != NULL) {
        cout << p->data << " ";
        preorder(p->lChild);
        preorder(p->rChild);
    }
}

int main() {
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 20);
    insert(root, 3);
    insert(root, 7);
    insert(root, 15);
    insert(root, 30);

    cout << search(root, 6) << endl;
    cout << del(root, 8) << endl;

    cout << "Pre-order Traversal: ";
    preorder(root);
}

⬆ Back to Top

AVL Trees

What is AVL Tree?

AVL trees are height-balanced binary search trees (BSTs). The balance is maintained using a balance factor (bf):

Balance Factor (bf) = height of left subtree - height of right subtree.
The balance factor should be within {-1, 0, 1} for a tree to be balanced.
If |hl - hr| > 1 for any node, that node is considered imbalanced.
Rotations are performed to restore the balance when a node becomes imbalanced.

⬆ Back to Top

How to Balance AVL Trees?

There are 4 types of rotations used to balance an AVL tree:

LL (Left-Left) Rotation → When a node's left child has its own left child.
RR (Right-Right) Rotation → When a node's right child has its own right child.
LR (Left-Right) Rotation → When a node's left child has a right child.
RL (Right-Left) Rotation → When a node's right child has a left child.

LL & RR rotations are single rotations.
LR & RL rotations are double rotations.

After performing these rotations, the balance factor should be restored to {-1, 0, 1}.

LL is also called a clockwise rotation, and RR is called a counter-clockwise rotation.
LR requires an RR first, followed by an LL.
RL requires an LL first, followed by an RR.

⬆ Back to Top

What are the Types of Rotations Used for Balancing AVL Trees?

1. LL (Left-Left) Rotation

LL rotation involves 3 nodes: A, B, and C.
Node B becomes the new root, A becomes B's right child, and C remains B's left child.
The original left child of B, if any, becomes A's right child.
Example:
- Initially: A (imbalanced node) has B as its left child, and B has C as its left child.
- After LL Rotation: B becomes the new root, A becomes the right child of B, and C remains the left child of B.

Before Rotation:

    A
   /
  B
 /
C

After LL Rotation:

    B
   / \
  C   A

2. RR (Right-Right) Rotation

Works symmetrically to LL but in the opposite direction.
C becomes the root, B becomes the left child of C, and A remains the left child of B.

Before Rotation:

After RR Rotation:

    B
   / \
  A   C

3. LR (Left-Right) Rotation

LR rotation requires two steps:
1. Perform an RR rotation on the left child of the imbalanced node (this converts it into an LL imbalance).
2. Perform an LL rotation on the imbalanced node itself to restore balance.
Example:
- Initially: A (imbalanced node) has B as its left child, and B has C as its right child.
- After LR Rotation: C becomes the new root, B becomes the left child of C, and A becomes the right child of C.

Before Rotation:

Step 1 (RR Rotation on B):

    A
   /
  C
 /
B

Step 2 (LL Rotation on A):

    C
   / \
  B   A

4. RL (Right-Left) Rotation

RL rotation is the reverse of LR:
1. Perform an LL rotation on the right child of the imbalanced node.
2. Perform an RR rotation on the imbalanced node itself.
Example:
- Initially: A (imbalanced node) has B as its right child, and B has C as its left child.
- After RL Rotation: C becomes the new root, A becomes the left child of C, and B becomes the right child of C.

Before Rotation:

Step 1 (LL Rotation on B):

Step 2 (RR Rotation on A):

    C
   / \
  A   B

⬆ Back to Top

How to Perform Deletion in AVL Tree?

Deletion in AVL trees works similarly to deletion in standard Binary Search Trees (BSTs), with additional steps to maintain balance. After deleting a node (using the in-order successor or predecessor method), we must ensure that the tree remains balanced. The key task is to check and correct the balance factor of the nodes after deletion.

Two Important Scenarios to Handle:

Deleting from the Right Subtree:

After deletion, the balance factor of the left subtree may change, so we check its balance:
- L 1 (Left-heavy): Perform LL rotation to restore balance.
- L -1 (Right-heavy): Perform LR rotation to restore balance.
- L 0 (Balanced): Simply delete the node, but still check for imbalances later.

Deleting from the Left Subtree:

When deleting from the left subtree, we check the balance factor of the right subtree:
- R 1 (Right-heavy): Perform RR rotation to restore balance.
- R -1 (Left-heavy): Perform RL rotation to restore balance.
- R 0 (Balanced): After deletion, check for imbalances and perform necessary rotations.

Steps in Deletion:

Delete the node using the standard in-order successor or in-order predecessor method.
Update the balance factor of the affected nodes.
If the balance factor of a node becomes +2 or -2, the tree is imbalanced, and you must perform rotations.
Perform one of the following rotations based on balance factor:
- LL Rotation (Left-Left case)
- RR Rotation (Right-Right case)
- LR Rotation (Left-Right case)
- RL Rotation (Right-Left case)
Continue checking and rebalancing the tree upwards if necessary.

AVL trees require rebalancing after every deletion to ensure the height remains logarithmic O(log n).
The balance factor of every node should always be -1, 0, or 1. If it goes beyond these values after deletion, perform the appropriate rotations.
LL, RR, LR, and RL rotations help maintain AVL properties.

⬆ Back to Top

How to Find Height or Nodes of an AVL Tree?

If Height is Given:

Maximum Nodes: The maximum number of nodes in an AVL tree with height h occurs when the tree is perfectly balanced.
- Formula: Maximum nodes = 2^h - 1
- Example: If h = 3, Maximum nodes = 2^3 - 1 = 7
Minimum Nodes: The minimum number of nodes in an AVL tree with height h occurs when the tree is minimally balanced.
- Formula: Minimum nodes = N(h - 2) + N(h - 1) + 1
- Where:
  - N(h - 2) = Minimum nodes for height h-2
  - N(h - 1) = Minimum nodes for height h-1
- For h = 1, the minimum number of nodes is 1.

If Nodes are Given:

Maximum Height: The maximum height occurs when the tree is completely unbalanced (like a linked list).
- Formula: Maximum height = n - 1
- Example: For 4 nodes, Maximum height = 4 - 1 = 3
Minimum Height: The minimum height occurs when the tree is perfectly balanced.
- Formula: Minimum height = log2(n + 1)
- Example: For 7 nodes, Minimum height = log2(7 + 1) = log2(8) = 3

⬆ Back to Top

Comparison of AVL Trees and BSTs: Benefits Over BSTs

AVL trees are always balanced, ensuring O(log n) height, whereas BSTs can become skewed and degrade to O(n) height in the worst case.
AVL trees perform faster searches, insertions, and deletions compared to unbalanced BSTs.
They are more memory efficient than Red-Black Trees but require slightly more rotations for balancing.

⬆ Back to Top

What are the Applications of AVL Trees: When Are They Preferred?

Databases and Indexing: AVL trees are used in databases for fast lookups due to their self-balancing property.
Network Routing: They help optimize routing algorithms by maintaining sorted data structures.
Memory Management: Used in OS memory allocation techniques where efficient searching is needed.
Compiler Design: AVL trees help in symbol table implementations for efficient data retrieval.

⬆ Back to Top

#include<iostream>
using namespace std;

class Node{
    public:
        Node* lChild;
        int data;
        int height;
        Node* rChild;
}* root = NULL;

int nodeHeight(Node* p){
    int hl, hr;
    hl = p && p->lChild ? p->lChild->height : 0;
    hr = p && p->rChild ? p->rChild->height : 0;

    return hl > hr ? hl + 1 : hr + 1;
}

int balanceFactor(Node* p){
    int hl, hr;
    hl = p && p->lChild ? p->lChild->height : 0;
    hr = p && p->rChild ? p->rChild->height : 0;

    return hl - hr;
}

Node* llRotation(Node* p){ // Height of pl and p will changed
    Node* pl = p->lChild;
    Node* plr = p->rChild;

    pl->rChild = p;
    p->lChild = plr;
    p->height = nodeHeight(p);
    pl->height = nodeHeight(pl);

    if(root == p) // If rotation are performed on root
        root = pl;
    return pl;
}

Node* lrRotation(Node* p) {
    Node* pl = p->lChild;
    Node* plr = pl->rChild;

    pl->rChild = plr->lChild;
    p->lChild = plr->rChild;

    plr->lChild = pl;
    plr->rChild = p;

    pl->height = nodeHeight(pl);
    p->height = nodeHeight(p);
    plr->height = nodeHeight(plr);

    if(p == root)
        root = plr;
    return plr;
}


Node* rrRotation(Node* p){
    Node* pr = p->rChild;
    Node* prl = pr->lChild;

    pr->lChild = p;
    p->rChild = prl;

    p->height = nodeHeight(p);
    pr->height = nodeHeight(pr);

    return pr;
}

Node* rlRotation(Node* p){
    Node* pr = p->rChild;
    Node* prl = pr->lChild;

    pr->lChild = prl->rChild;
    p->rChild = prl->lChild;

    prl->rChild = pr;
    prl->lChild = p;

    pr->height = nodeHeight(pr);
    p->height = nodeHeight(p);
    prl->height = nodeHeight(prl);

    if(root == p)
        root = prl;

    return prl;
}

Node* create(Node* p, int data){
    if(p == NULL){
        Node* temp;
        temp = new Node;
        temp->data = data;
        temp->height = 1;
        temp->lChild = temp->rChild = NULL;

        return temp;
    }

    if(p->data < data){
        p->rChild = create(p->rChild, data);
    }else{
        p->lChild = create(p->lChild, data);
    }

    p->height = nodeHeight(p); // We create new temp pointer we will calculate height of its children
    // cout << "C = " << balanceFactor(p)
    if(balanceFactor(p) == 2 && balanceFactor(p->lChild) == 1){
        return llRotation(p);
    }else if(balanceFactor(p) == 2 && balanceFactor(p->lChild) == -1){
        return lrRotation(p);
    }else if(balanceFactor(p) == -2 && balanceFactor(p->rChild) == -1){
        return rrRotation(p);
    }else if(balanceFactor(p) == -2 && balanceFactor(p->rChild) == 1){
        return rlRotation(p);
    }

    return p;
}

Node* inPre(Node* p){
    while(p && p->rChild != NULL){
        p = p->rChild;
    }
    return p;
}
Node* inSucc(Node* p){
    while(p && p->lChild != NULL){
        p = p->lChild;
    }
    return p;
}

Node* del(Node*p, int key){
    if(p == NULL){
        return NULL;
    }

    if(p && p->rChild == NULL && p->lChild == NULL){
        if(p == root)
            root = NULL;
        delete p;
        return NULL;
    }


    if(p->data > key){
        p->lChild = del(p->lChild, key);
    }else if(p->data < key){
        p->rChild = del(p->rChild, key);
    }else{
        Node* q;
        if(nodeHeight(p->lChild) > nodeHeight(p->rChild)){
            q = inPre(p->lChild);
            p->data = q->data;
            p->lChild = del(p->lChild, q->data);
        }else{
            q = inSucc(p->rChild);
            p->data = q->data;
            p->rChild = del(p->rChild, q->data);
        }
    }

    p->height = nodeHeight(p);

    if (balanceFactor(p) == 2 && balanceFactor(p->lChild) == 1) {  // L1 Rotation
        return llRotation(p);
    } else if (balanceFactor(p) == 2 && balanceFactor(p->lChild) == -1){  // L-1 Rotation
        return lrRotation(p);
    } else if (balanceFactor(p) == -2 && balanceFactor(p->rChild) == -1){  // R-1 Rotation
        return rrRotation(p);
    } else if (balanceFactor(p) == -2 && balanceFactor(p->rChild) == 1){  // R1 Rotation
        return rlRotation(p);
    } else if (balanceFactor(p) == 2 && balanceFactor(p->lChild) == 0){  // L0 Rotation
        return llRotation(p);
    } else if (balanceFactor(p) == -2 && balanceFactor(p->rChild) == 0){  // R0 Rotation
        return rrRotation(p);
    }

    return p;
}

void preorder(Node* p) {
    if(p != NULL) {
        cout << p->data << " ";
        preorder(p->lChild);
        preorder(p->rChild);
    }
}

int main() {
    root = create(root, 10);
    root = create(root, 20);
    root = create(root, 30);
    root = create(root, 25);
    root = create(root, 28);
    root = create(root, 27);
    root = create(root, 5);

    preorder(root);

    cout << endl << root->data << endl;
}

Binary Heap

What is Binary Heap? What are its Characteristics?

A binary heap is a complete binary tree that maintains the heap property. There are two types:

Max Heap: Each parent node is greater than or equal to its children. The largest value is at the root.
Min Heap: Each parent node is less than or equal to its children. The smallest value is at the root.

Characteristics:

Complete Binary Tree: All levels are fully filled, except possibly the last, which is filled from left to right.
Heap Property:
- Max Heap: Every node is greater than or equal to its descendants.
- Min Heap: Every node is less than or equal to its descendants.

⬆ Back to Top

Which is the Preferred Way to Implement Binary Heap?

Binary heaps are typically implemented using arrays for efficiency:

Array Representation:
- Node at index i.
- Left child at index 2 * i + 1.
- Right child at index 2 * i + 2.

This representation ensures O(1) access to the root and O(log n) insertion and deletion.

⬆ Back to Top

How to Implement Binary Heap Using an Array?

Binary heaps can be implemented efficiently using an array without explicit pointers:

Insertion: Add the element at the next available position and heapify up.
Deletion: Remove the root, replace it with the last element, and heapify down.
Heapify: Restore heap properties after insertion or deletion.

⬆ Back to Top

How to Perform Operations on Binary Heap?

1. Insertion:

Insert the element at the next available position to maintain completeness.
Heapify Up: Compare with its parent and swap if necessary to maintain the heap property.
Time Complexity: O(log n)

2. Deletion:

Remove the root (highest or lowest value, depending on heap type).
Replace it with the last element.
Heapify Down: Compare with children and swap with the correct one.
Time Complexity: O(log n)

3. Heapify:

Convert an arbitrary array into a heap.
Process each node from bottom to top, ensuring the heap property holds.
Time Complexity: O(n)

⬆ Back to Top

Explain the Concept of Heapify Process

Used to restore the heap property after insertion or deletion.
Bottom-up heapify: Used for insertion (heapify up).
Top-down heapify: Used for deletion (heapify down).
Heapify ensures O(n) complexity for building a heap.

⬆ Back to Top

What is Binary Heap as a Priority Queue?

A priority queue can be implemented efficiently using a binary heap:

The element with the highest priority (the root) is always deleted first.
Insertion is O(1), and deletion takes O(log n).
Used in scheduling algorithms, Dijkstra’s shortest path, and Huffman coding.

⬆ Back to Top

Heap Operations

#include <iostream>
#include <vector>
using namespace std;

// Insert an element into a max-heap
void Insert(vector<int>& heap, int key) {
    int i = heap.size();
    heap.push_back(key);
    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
        swap(heap[i], heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Heapify down function
void Heapify(vector<int>& heap, int i, int n) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && heap[left] > heap[largest])
        largest = left;
    if (right < n && heap[right] > heap[largest])
        largest = right;

    if (largest != i) {
        swap(heap[i], heap[largest]);
        Heapify(heap, largest, n);
    }
}

// Delete the root element
void Delete(vector<int>& heap) {
    int n = heap.size();
    if (n == 0) return;
    swap(heap[0], heap[n - 1]);
    heap.pop_back();
    Heapify(heap, 0, heap.size());
}

// Print heap
void PrintHeap(const vector<int>& heap) {
    for (int val : heap) cout << val << " ";
    cout << endl;
}

int main() {
    vector<int> heap;
    Insert(heap, 50);
    Insert(heap, 30);
    Insert(heap, 40);
    Insert(heap, 10);
    Insert(heap, 20);
    Insert(heap, 35);
    PrintHeap(heap);
    Delete(heap);
    PrintHeap(heap);
}

Max Heap

#include <iostream>
#include <vector>

using namespace std;

// Function to insert a key into the max-heap represented as a vector
void Insert(vector<int>& vec, int key) {
    auto i = vec.size();         // Get current size of the vector
    vec.emplace_back(key);       // Insert key at the end of the vector

    // Rearrange elements to maintain the max-heap property: O(log n)
    while (i > 0 && key > vec[i % 2 == 0 ? (i / 2) - 1 : i / 2]) {
        vec[i] = vec[i % 2 == 0 ? (i / 2) - 1 : i / 2]; // Move parent down
        i = i % 2 == 0 ? (i / 2) - 1 : i / 2;            // Move up the heap
    }
    vec[i] = key; // Place the new key in its correct position
}

// Function to insert an element into a max-heap represented as an array
void InsertInplace(int A[], int n) {
    int i = n;                  // Start at the last index
    int temp = A[n];           // Store the value to be inserted
    while (i > 0 && temp > A[i % 2 == 0 ? (i / 2) - 1 : i / 2]) {
        A[i] = A[i % 2 == 0 ? (i / 2) - 1 : i / 2]; // Move parent down
        i = i % 2 == 0 ? (i / 2) - 1 : i / 2;       // Move up the heap
    }
    A[i] = temp; // Place the new element in its correct position
}

// Function to create a max-heap from an array using a vector
void CreateHeap(vector<int>& vec, int A[], int n) {
    // O(n log n)
    for (int i = 0; i < n; i++) {
        Insert(vec, A[i]); // Insert each element from the array into the vector
    }
}

// Function to create a max-heap from an array in-place
void createHeap(int A[], int n) {
    for (int i = 0; i < n; i++) {
        InsertInplace(A, i); // Insert each element into the array
    }
}

// Template function to print the contents of a container
template <class T>
void Print(T& vec, int n, char c) {
    cout << c << ": [" << flush; // Start of output
    for (int i = 0; i < n; i++) {
        cout << vec[i] << flush; // Print each element
        if (i < n - 1) {
            cout << ", " << flush; // Add a comma between elements
        }
    }
    cout << "]" << endl; // End of output
}

int main() {
    cout << "Create Heap" << endl;
    int b[] = {10, 20, 30, 25, 5, 40, 35};
    Print(b, sizeof(b) / sizeof(b[0]), 'b'); // Print the initial array

    vector<int> v;
    CreateHeap(v, b, sizeof(b) / sizeof(b[0])); // Create a max-heap from the array into the vector
    Print(v, v.size(), 'v'); // Print the max-heap vector

    cout << "Inplace Insert" << endl;
    createHeap(b, sizeof(b) / sizeof(b[0])); // Create a max-heap in-place from the array
    Print(b, sizeof(b) / sizeof(b[0]), 'b'); // Print the updated array
}

Heap Sort

Heap sort is a sorting algorithm using a heap.

Step 1: Convert the array into a heap.
Step 2: Swap the root with the last element and reduce the heap size.
Step 3: Heapify down to maintain the heap.
Time Complexity: O(n log n)

#include <stdio.h>

void Insert(int A[], int n) {
    int i = n;         // Start from the last index
    int temp = A[i];  // Store the value to be inserted

    // Rearrange the heap to maintain max-heap property
    while (i > 1 && temp > A[i / 2]) {
        A[i] = A[i / 2]; // Move the parent down
        i = i / 2;       // Move up the tree
    }
    A[i] = temp; // Place the new value in its correct position
}

int Delete(int A[], int n) {
    int i, j, x, temp, val;
    val = A[1];   // Store the root value (maximum)
    A[1] = A[n];  // Move the last element to the root
    A[n] = val;   // Replace the last element with the root value
    i = 1;        // Start from the root
    j = i * 2;    // Get the left child index

    // Rearrange the heap to maintain max-heap property
    while (j <= n - 1) {
        if (j < n - 1 && A[j + 1] > A[j]) // Choose the larger child
            j = j + 1; // Move to the right child if it's larger
        if (A[i] < A[j]) { // If the current node is less than the larger child
            temp = A[i];   // Swap them
            A[i] = A[j];
            A[j] = temp;
            i = j;         // Move down the tree
            j = 2 * j;     // Update the child index
        } else
            break; // No more swaps needed
    }
    return val; // Return the maximum value (the root)
}

int main() {
    int H[] = {0, 14, 15, 5, 20, 30, 8, 40}; // Array representation of the heap (0 index unused)
    int i;

    // Build the heap using insertions
    for (i = 2; i <= 7; i++)
        Insert(H, i);

    // Delete elements to sort the array
    for (i = 7; i > 1; i--) {
        Delete(H, i);
    }

    // Print sorted elements
    for (i = 1; i <= 7; i++)
        printf("%d ", H[i]);
    printf("\n");
}

Heapify

#include <iostream>
using namespace std;

void swap(int A[], int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int Delete(int A[], int n){
    int x = A[0];  // Max element
    A[0] = A[n-1];

    int i = 0;
    int j = 2 * i + 1;

    while (j < n-1){
        // Compare left and right children
        if (A[j] < A[j+1]){
            j = j+1;
        }

        // Compare parent and largest child
        if (A[i] < A[j]){
            swap(A, i, j);
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }
    return x;
}

void Heapify(int A[], int n){
    // # of leaf elements: (n+1)/2, index of last leaf element's parent = (n/2)-1
    for (int i=(n/2)-1; i>=0; i--){

        int j = 2 * i + 1;  // Left child for current i

        while(j < n-1){
            // Compare left and right children of current i
            if (A[j] < A[j+1]){
                j = j+1;
            }

            // Compare parent and largest child
            if (A[i] < A[j]){
                swap(A, i, j);
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }
}

template <class T>
void Print(T& vec, int n, string s){
    cout << s << ": [" << flush;
    for (int i=0; i<n; i++){
        cout << vec[i] << flush;
        if (i < n-1){
            cout << ", " << flush;
        }
    }
    cout << "]" << endl;
}

int main() {

    int A[] = {5, 10, 30, 20, 35, 40, 15};
    Print(A, sizeof(A)/sizeof(A[0]), "A");

    Heapify(A, sizeof(A)/sizeof(A[0]));
    Print(A, sizeof(A)/sizeof(A[0]), "Heapified A");
    cout << endl;

    int B[] = {5, 10, 30, 20};
    Print(B, sizeof(B)/sizeof(B[0]), "B");

    Heapify(B, sizeof(B)/sizeof(B[0]));
    Print(B, sizeof(B)/sizeof(B[0]), "Heapified B");
}

⬆ Back to Top

Sorting Techniques

What are Sorting Techniques?

Sorting techniques are algorithms used to arrange elements in a particular order, typically ascending or descending. Different sorting algorithms have unique characteristics, efficiencies, and use cases.

⬆ Back to Top

What are the Criteria for Analyzing a Sorting Algorithm?

Sorting algorithms can be analyzed based on:

Number of Comparisons - Determines time complexity.
Number of Swaps - Measures efficiency in terms of swapping operations.
Adaptivity - Determines if the algorithm takes less time for an already sorted array.
Stability - Preserves the relative order of equal elements.
Extra Memory Usage - Some algorithms require additional space.

⬆ Back to Top

What are the Different Types of Sorting Algorithms? (Comparison-Based and Index-Based)

Sorting algorithms are classified into two main types:

Comparison-Based Sorting Algorithms:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Heap Sort
- Merge Sort
- Quick Sort
- Tree Sort
- Shell Sort
Index-Based Sorting Algorithms:
- Counting Sort
- Bucket Sort
- Radix Sort

Time Complexity Overview:

Bubble, Insertion, Selection Sort: O(n²) (less efficient for large datasets)
Heap, Merge, Quick, Tree Sort: O(n log n) (efficient for large datasets)
Counting, Bucket, Radix Sort: O(n) (faster but uses more space)
Shell Sort: O(n^(3/2)) or O(n^1.5) (faster than Bubble, Insertion, and Selection Sort but slower than Merge and Quick Sort)

⬆ Back to Top

What is Bubble Sort? Explain with an Example.

Bubble Sort is a simple sorting algorithm where elements are repeatedly swapped if they are in the wrong order. The largest element is placed in its correct position after each pass.

Total passes needed: n - 1
Comparisons: n(n - 1) / 2 → O(n²)
Maximum number of swaps: O(n²)

Lighter elements "bubble" up while heavier ones sink, similar to floating objects in water. If no swaps occur in a pass, the list is already sorted, making Bubble Sort adaptive.

To get k largest numbers, perform k iterations. If no swaps occur, the list is already sorted. This can be optimized with a flag:

If swaps happen, increment the flag.
If no swaps occur after the first loop, break out of the loop—indicating the algorithm is adaptive.

Example

Unsorted Array: [7, 3, 5, 1]

Steps

Pass 1 (Largest element moves to the end):

Compare 7 and 3 → Swap → [3, 7, 5, 1]
Compare 7 and 5 → Swap → [3, 5, 7, 1]
Compare 7 and 1 → Swap → [3, 5, 1, 7]

Pass 2 (Next largest element moves to its position):

Compare 3 and 5 → No swap
Compare 5 and 1 → Swap → [3, 1, 5, 7]

Pass 3 (Final sorting step):

Compare 3 and 1 → Swap → [1, 3, 5, 7]

void swap(int* x, int* y){
    int z = *x;
    *x = *y;
    *y = z;
}

void bubbleSort(int A[], int n){
    for(int i = 0; i < n - 1; i++){
        int flag = 0;
        for(int j = 0; j < n - i - 1; j++){
            if(A[j] > A[j + 1]){
                flag++;
                swap(&A[j], &A[j + 1]);
            }
        }
        if(!flag){
            cout << "List is already sorted" << endl;
            break;
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

⬆ Back to Top

What is Insertion Sort? Explain with an Example.

Insertion Sort is a simple and intuitive sorting algorithm that works similarly to how we sort playing cards in our hands. It picks an element and places it in its correct position by shifting larger elements to the right.

How Insertion Sort Works:

The algorithm assumes that the first element is already sorted.
It picks the next element and compares it with the elements in the sorted portion of the array.
If the element is smaller than the previous elements, it is shifted to its correct position.
This process repeats until the entire array is sorted.

Stable Sort: Maintains the relative order of equal elements.
Adaptive: Performs well on nearly sorted data with O(n) complexity in the best case.
In-Place: Requires no extra memory, unlike merge sort.
Time Complexity:
- Best case (already sorted): O(n)
- Worst case (reverse sorted): O(n²)
- Average case: O(n²)

Example:

Unsorted Array: [7, 3, 5, 1]

Steps:

Consider 3, compare with 7, shift 7, and place 3: [3, 7, 5, 1]
Consider 5, compare with 7, shift 7, place 5: [3, 5, 7, 1]
Consider 1, shift 7, 5, and 3, then place 1: [1, 3, 5, 7]

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void insertionSortRecursive(int arr[], int n) {
    if (n <= 1)
        return;

    insertionSortRecursive(arr, n - 1);

    int key = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}

Why is Insertion Sort Suitable for Linked Lists?

Unlike arrays, linked lists do not require shifting elements, making insertion sort more efficient for linked lists.
The insertion process in a linked list takes only O(1) in the best case and O(n) in the worst case.
It is easier to maintain sorted order in a linked list compared to an array where shifting is required.

⬆ Back to Top

What is the Difference between Bubble Sort and Insertion Sort

Feature	Bubble Sort	Insertion Sort
Minimum Comparisons	O(1)	O(1) (Ascending Order)
Maximum Comparisons	O(n²)	O(n²) (Descending Order)
Minimum Swaps	O(1)	O(1) (Ascending Order)
Maximum Swaps	O(n²)	O(n²) (Descending Order)
Adaptive	Yes	Yes
Stable	Yes	Yes
Suitable for Linked List	No	Yes
Passes Benefit	Yes (k passes give top k elements)	No

Bubble Sort: Compares adjacent elements and swaps them if necessary.
Insertion Sort: Inserts each element in its correct position by shifting elements.

⬆ Back to Top

What is Selection Sort? Explain with an Example.

Selection Sort repeatedly finds the smallest element from the unsorted part and moves it to the sorted part.

For n elements:

Total passes needed: n - 1
Comparisons: O(n²)
Swaps: O(n) (minimally swaps elements compared to other sorts)

Concept:

Selection Sort is not adaptive as it always takes O(n²) time.
It is not stable, as swapping can change the relative order of equal elements.
Advantage: Minimum number of swaps.

Performance:

Best Case: O(n²)
Worst Case: O(n²)

Example

Unsorted Array: [7, 3, 5, 1]

Steps:

Pass 1 (Find the minimum and swap with the first element):

Find min (1), swap with 7 → [1, 3, 5, 7]

Pass 2 (Find the next minimum and swap):

Find min (3), already in place → [1, 3, 5, 7]

Pass 3 (Find the next minimum and swap):

Find min (5), already in place → [1, 3, 5, 7]

void selectionSort(int A[], int n){
    int i, j, k;
    for(i = 0; i < n - 1; i++){
        for(j = k = i; j < n; j++)
            if(A[j] < A[k])
                k = j;
        swap(A[i], A[k]);
    }
}

⬆ Back to Top

What is Quick Sort? Explain with an Example.

Concept:

Quick Sort is a divide and conquer algorithm that sorts an array by partitioning it around a pivot.
An element is in its sorted position if all elements before it are smaller, and all elements after it are larger.
Quick Sort does not always mean faster sorting; performance depends on the pivot selection.
Similar to how a teacher asks students to arrange themselves in height order.
Process: You check on your left side if anyone is taller than you, and on the right side if anyone is shorter. If so, swap them.
Quick Sort is a recursive procedure.

Pivot Selection:

The pivot is the element whose sorted position we want to determine.
i scans for any element greater than the pivot, while j scans for any element smaller or equal.
Swap the pivot with j to place it in its correct partition.
Recursively apply Quick Sort on both partitions until there are at least two elements left.

Worst Cases:

Already sorted (ascending order): Quick Sort performs O(n²) comparisons.
Sorted in descending order: Another worst-case scenario, also O(n²) comparisons.

Best Case:

Randomly ordered elements: Yields an optimal performance of O(n log n).

Performance:

Sorted (ascending/descending): O(n²).
Unsorted (with middle partitioning): O(n log n).
Average case: O(n log n).

Selecting the Middle Element as Pivot:

Moving the middle element as the pivot can make an already sorted list the best case at O(n log n), while middle partitioning can become the worst case.

Randomized Quick Sort:

Selecting a random element as the pivot is known as Randomized Quick Sort.
Also referred to as Selection Exchange Sort, Partition Sort, and Quick Sort.

Example

Unsorted Array: [7, 3, 5, 1]

Steps:

Step 1 (Choose a Pivot and Partition):

Choose a pivot (7).
Partition the array such that all elements smaller than the pivot are on the left, and all elements larger are on the right.
- After partitioning: [3, 5, 1, 7]
- Pivot 7 is now in the correct position.

Step 2 (Sort the Left Subarray):

Left subarray: [3, 5, 1]
Choose a pivot (3).
Partition the subarray: [1, 3, 5]
- Pivot 3 is now in the correct position.

Step 3 (Sort the Left Subarray of `[1, 3, 5]`):

Left subarray: [1] (already sorted, no changes).
Right subarray: [5] (already sorted, no changes).

Final Sorted Array: `[1, 3, 5, 7]`

void swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int A[], int l, int h) {
    int pivot = A[l];
    int i = l, j = h;

    do {
        do { i++; } while (A[i] <= pivot);
        do { j--; } while (A[j] > pivot);

        if (i < j) swap(&A[i], &A[j]);
    } while (i < j);

    swap(&A[l], &A[j]);
    return j;
}

void QuickSort(int A[], int l, int h) {
    int j;
    if (l < h) {
        j = partition(A, l, h);
        QuickSort(A, l, j);
        QuickSort(A, j + 1, h);
    }
}

int main() {
    int A[] = {10, 7, 8, 9, 1, 5, INT32_MAX}; // Sentinel INT32_MAX
    int n = 6;
    QuickSort(A, 0, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;
}

Partition Function (partition):
- The pivot is chosen as the first element.
- Two pointers i and j traverse the array: i moves forward searching for a larger element, while j moves backward searching for a smaller or equal element.
- If i < j, swap A[i] and A[j].
- Finally, swap the pivot with A[j] to place it correctly.
Quick Sort Function (QuickSort):
- Recursively sorts the left and right partitions.
- Base case: If the segment has fewer than two elements, the recursion stops.

⬆ Back to Top

What is the Difference between Selection Sort and. Quick Sort

Selection Sort: In Selection Sort, we select a position and then find the appropriate element for it.
Quick Sort: In Quick Sort, we select an element (the pivot) and then find its correct position.

⬆ Back to Top

What is Merge Sort? Explain and Provide Code for Both Recursive and Iterativees.

Merge Sort is a divide-and-conquer algorithm that divides an array into two halves, recursively sorts them, and then merges them back together. It is a stable, O(n log n) sorting algorithm with a worst-case time complexity of O(n log n) and requires extra space for the merge process.

Merging Process

Introduction:
- Merge sort is the only sorting algorithm that requires additional space for sorting. It works by dividing the array into smaller sub-arrays and then merging them back in a sorted manner.
Ways to Merge:
1. Merging Two Separate Lists: Combines two pre-sorted lists into one sorted list.
2. Merging Two Sublists Within a Single List: Divides a list into two sublists and merges them back in a sorted order.
3. Merging Multiple Lists: Merges multiple lists iteratively using pairwise merging.
Extra Array:
- An additional array is required to temporarily store the merged data before copying it back to the original array.
Merging Two Separate Lists:
- Use pointers to traverse both lists and compare elements. The smaller element is added to the new list, and the process continues until all elements are merged.
- Time Complexity: O(m + n), where m and n are the sizes of the two lists.
Merging Two Sublists Within a Single List:
- Divide the list into two halves and apply the merging process to merge these two sorted sublists into one.
Merging Multiple Lists:
- For multi-way merging, merge pairs of lists recursively until all lists are combined into one.

Example

Unsorted Array: [7, 3, 5, 1]

Steps:

Step 1 (Divide the Array):

Split the array into two halves:
- Left: [7, 3]
- Right: [5, 1]

Step 2 (Recursively Sort Left Half):

Split [7, 3] into:
- Left: [7]
- Right: [3]
Since each contains only one element, they are already sorted.
Merge [7] and [3] into [3, 7].

Step 3 (Recursively Sort Right Half):

Split [5, 1] into:
- Left: [5]
- Right: [1]
Since each contains only one element, they are already sorted.
Merge [5] and [1] into [1, 5].

Step 4 (Merge the Two Sorted Halves):

Merge [3, 7] and [1, 5]:
- Compare 3 and 1 → Place 1
- Compare 3 and 5 → Place 3
- Compare 7 and 5 → Place 5
- Place 7 (remaining element)
Result after merging: [1, 3, 5, 7]

Final Sorted Array: `[1, 3, 5, 7]`

Iterative Merge Sort

Approach:
- Start with 1-element lists (each element is considered sorted) and iteratively merge pairs of lists.
- Merge in increasing sizes (2, 4, 8, etc.), which resembles a binary tree structure.
Performance:
- Time Complexity: O(n log n).
- Handling Odd Elements: If the number of elements is odd, the last list remains unmerged until the final pass.

void MergeSort(int A[], int n) {
    int p, i, l, mid, h;

    for(p = 1; p < n; p *= 2) {
        for(i = 0; i + p - 1 < n; i += p * 2) {
            l = i;
            mid = i + p - 1;
            h = (i + p * 2 - 1 < n) ? (i + p * 2 - 1) : (n - 1);
            merge(A, l, mid, h);
        }
    }

    if(p / 2 < n) {
        l = 0;
        mid = p / 2 - 1;
        h = n - 1;
        merge(A, l, mid, h);
    }
}


void MergeSort(int A[], int n) {
    int p, l, h, mid, i;
    for (p = 2; p <= n; p *= 2) {
        for (i = 0; i + p - 1 < n; i += p) {
            l = i;
            h = i + p - 1;
            mid = (l + h) / 2;
            merge(A, l, mid, h);
        }
        if (n - i > p / 2) {
            l = i;
            h = i + p - 1;
            mid = (l + h) / 2;
            merge(A, l, mid, n - 1);
        }
    }
    if (p / 2 < n) {
        merge(A, 0, p / 2 - 1, n - 1);
    }
}

void MergeSort(int A[], int n) {
    int p, l, h, mid, i;

    for (p = 2; p <= n; p *= 2) {
        for (i = 0; i + p - 1 < n; i += p) {
            l = i;
            h = i + p - 1;
            mid = (l + h) / 2;
            merge(A, l, mid, h);
        }
    }

    if (p / 2 < n) {
        merge(A, 0, p / 2 - 1, n - 1);
    }
}

Recursive Merge Sort

Approach:
- Recursively divide the array into sublists until each sublist has only one element.
- After dividing, the sublists are merged back together in sorted order.
Performance:
- Time Complexity: O(n log n), since the array is divided log n times, and each merge step takes O(n).
- Required Space: O(n) for the temporary array used in merging.

void MergeSort(int A[], int low, int high){
    if (low < high){
        // Calculate mid point
        int mid = low + (high-low)/2;

        // Sort sub-lists
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);

        // Merge sorted sub-lists
        merge(A, low, mid, high);
    }
}

Merge Function

This function merges two sorted lists into one sorted list.

void Merge(int x[], int y[], int z[], int m, int n){
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < m && j < n){
        if (x[i] < y[j]){
            z[k++] = x[i++];
        } else {
            z[k++] = y[j++];
        }
    }
    while (i < m){
        z[k++] = x[i++];
    }
    while (j < n){
        z[k++] = y[j++];
    }
}

Merging a Single List:

This function merges a portion of an array, dividing it into two sublists.

void MergeSingle(int A[], int low, int mid, int high){
    int i = low;
    int j = mid + 1;
    int k = low;
    int B[high + 1];
    while (i <= mid && j <= high){
        if (A[i] < A[j]){
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }
    while (i <= mid){
        B[k++] = A[i++];
    }
    while (j <= high){
        B[k++] = A[j++];
    }
    for (int i = low; i <= high; i++){
        A[i] = B[i];
    }
}

⬆ Back to Top

What is Counting Sort? Explain with an Example.

Counting Sort is a non-comparative, index-based sorting algorithm that efficiently sorts numbers within a limited range. It utilizes an auxiliary array to count occurrences of each element and reconstructs the sorted array based on these counts.

How Counting Sort Works?

Find Maximum Value: Determine the maximum element in the array to define the range.
Create Auxiliary Array: Initialize an auxiliary array (C[]) of size equal to the max value +1, filled with zeros.
Count Elements: Traverse the input array and store the frequency of each number at its corresponding index in C[].
Reconstruct Sorted Array: Iterate through C[], placing elements back into the original array based on their counts.

Performance:

Time Complexity: O(n + k), where n is the number of elements and k is the range of input values.
Space Complexity: O(k), since it requires additional space for the auxiliary array.

Example

Unsorted Array: [4, 2, 2, 8, 3, 3, 1]

Step 1: Find Maximum Value

Maximum value in array = 8

Step 2: Create Frequency Array

Index:   0 1 2 3 4 5 6 7 8
Count:   0 1 2 2 1 0 0 0 1

Step 3: Reconstruct Sorted Array

Extract elements based on counts: [1, 2, 2, 3, 3, 4, 8]

Final Sorted Array: `[1, 2, 2, 3, 3, 4, 8]`

void countSort(int A[], int n) {
    int max = A[0];
    for (int i = 1; i < n; i++)
        if (max < A[i])
            max = A[i];

    int C[max + 1] = {0};

    for (int i = 0; i < n; i++) {
        C[A[i]]++;
    }

    int j = 0;
    for (int i = 0; i <= max; i++) {
        while (C[i] > 0) {
            A[j++] = i;
            C[i]--;
        }
    }
}

int main() {
    int A[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(A) / sizeof(A[0]);
    countSort(A, n);

    cout << "Sorted Array: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
}

Advantages:

Works in linear time for small ranges.
Does not involve comparisons like Quick Sort or Merge Sort.
Stable sorting algorithm, preserving the relative order of duplicate elements.

Disadvantages:

Requires extra space proportional to the range of input values.
Inefficient for large ranges or negative numbers.

⬆ Back to Top

What is Bucket/Bin Sort? Explain with an Example.

Bucket Sort is a distribution-based sorting algorithm that distributes elements into multiple buckets.
Each bucket contains a range of values and is sorted individually using another sorting algorithm or recursively applying Bucket Sort.

Method

Create m buckets, where m is chosen based on the input size or value range.
Distribute elements into respective buckets based on their values.
Sort individual buckets using another sorting technique (e.g., Insertion Sort).
Concatenate all sorted buckets to obtain the final sorted array.

Differences from Counting Sort

Counting Sort increments a count for each occurrence, while Bucket Sort places elements in linked lists or arrays.
Bucket Sort is better suited for uniformly distributed data.

Performance:

Time Complexity: Average-case O(n + k), where n is the number of elements and k is the number of buckets.
Space Complexity: O(n + m), where m is the number of buckets.

Example

Unsorted Array: [4, 2, 2, 8, 3, 3, 1]

Step 1: Find Maximum Value

Maximum value in array = 8

Step 2: Create Bins and Insert Elements

Bin 0: []
Bin 1: [1]
Bin 2: [2, 2]
Bin 3: [3, 3]
Bin 4: [4]
Bin 5: []
Bin 6: []
Bin 7: []
Bin 8: [8]

Step 3: Extract Elements in Sorted Order

Extract elements from bins in order: [1, 2, 2, 3, 3, 4, 8]

Final Sorted Array: `[1, 2, 2, 3, 3, 4, 8]`

int Max(int A[], int n){
    int max = -32768;
    for (int i=0; i<n; i++){
        if (A[i] > max){
            max = A[i];
        }
    }
    return max;
}

// Linked List node
class Node{
public:
    int value;
    Node* next;
};

void Insert(Node** ptrBins, int idx){
    Node* temp = new Node;
    temp->value = idx;
    temp->next = nullptr;

    if (ptrBins[idx] == nullptr){ // ptrBins[idx] is head ptr
        ptrBins[idx] = temp;
    } else {
        Node* p = ptrBins[idx];
        while (p->next != nullptr){
            p = p->next;
        }
        p->next = temp;
    }
}

int Delete(Node** ptrBins, int idx){
    Node* p = ptrBins[idx];  // ptrBins[idx] is head ptr
    ptrBins[idx] = ptrBins[idx]->next;
    int x = p->value;
    delete p;
    return x;
}

void BinSort(int A[], int n){
    int max = Max(A, n);

    // Create bins array
    Node** bins = new Node* [max + 1];

    // Initialize bins array with nullptr
    for (int i=0; i<max+1; i++){
        bins[i] = nullptr;
    }

    // Update count array values based on A values
    for (int i=0; i<n; i++){
        Insert(bins, A[i]);
    }

    // Update A with sorted elements
    int i = 0;
    int j = 0;
    while (i < max+1){
        while (bins[i] != nullptr){
            A[j++] = Delete(bins, i);
        }
        i++;
    }

    // Delete heap memory
    delete [] bins;
}

Bucket Sort is highly efficient for sorting small range values efficiently using bins.
It is preferable when dealing with values that are uniformly distributed across a range.

⬆ Back to Top

What is Radix Sort? Explain with an Example.

Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD).
It uses a fixed number of bins (usually 10 for decimal numbers) instead of an auxiliary array based on the maximum input values.
This method is efficient for sorting numbers with a known range of digits.

Method

Initialize bins: Create 10 bins corresponding to digits 0-9 and set them to NULL.
Distribute elements by LSD: Extract the last digit of each number using A[i] % 10 and place them in the corresponding bin.
Reconstruct array: Collect elements from bins following FIFO (First In, First Out) order and write them back to the array.
Repeat for next digit: Divide each number by 10 (A[i] / 10 % 10), process the second last digit, and place elements into bins again.
Continue for all digits: Repeat the process for the remaining digits until all numbers are sorted.

Performance

Time Complexity: O(d * n), where d is the number of digits and n is the number of elements.
Space Complexity: O(n), as additional space is needed for the output array.

Example

Unsorted Array: [170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sorting by Least Significant Digit (Unit Place)

Bins:
0 -> [170]
2 -> [802, 2]
4 -> [24]
5 -> [75, 45]
6 -> [66]
9 -> [90]

Sorted after first pass: [170, 802, 2, 24, 75, 45, 66, 90]

Step 2: Sorting by Tens Place

Bins:
0 -> [802, 2]
2 -> [24]
4 -> [45]
5 -> [75]
6 -> [66]
7 -> [170]
9 -> [90]

Sorted after second pass: [802, 2, 24, 45, 75, 66, 170, 90]

Step 3: Sorting by Hundreds Place

Bins:
0 -> [2, 24, 45, 66, 75, 90]
1 -> [170]
8 -> [802]

Sorted after third pass: [2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted Array: `[2, 24, 45, 66, 75, 90, 170, 802]`

#include <iostream>
#include <cmath>
using namespace std;

class Node {
public:
    int value;
    Node* next;
};

int Max(int A[], int n){
    int max = -32768;
    for (int i=0; i<n; i++){
        if (A[i] > max){
            max = A[i];
        }
    }
    return max;
}

int countDigits(int x){
    int count = 0;
    while (x != 0){
        x = x / 10;
        count++;
    }
    return count;
}

void initializeBins(Node** p, int n){
    for (int i=0; i<n; i++){
        p[i] = nullptr;
    }
}

void Insert(Node** ptrBins, int value, int idx){
    Node* temp = new Node;
    temp->value = value;
    temp->next = nullptr;

    if (ptrBins[idx] == nullptr){
        ptrBins[idx] = temp;
    } else {
        Node* p = ptrBins[idx];
        while (p->next != nullptr){
            p = p->next;
        }
        p->next = temp;
    }
}

int Delete(Node** ptrBins, int idx){
    Node* p = ptrBins[idx];
    ptrBins[idx] = ptrBins[idx]->next;
    int x = p->value;
    delete p;
    return x;
}

int getBinIndex(int x, int idx){
    return (int)(x / pow(10, idx)) % 10;
}

void RadixSort(int A[], int n){
    int max = Max(A, n);
    int nPass = countDigits(max);
    Node** bins = new Node* [10];
    initializeBins(bins, 10);

    for (int pass=0; pass<nPass; pass++){
        for (int i=0; i<n; i++){
            int binIdx = getBinIndex(A[i], pass);
            Insert(bins, A[i], binIdx);
        }

        int i = 0, j = 0;
        while (i < 10){
            while (bins[i] != nullptr){
                A[j++] = Delete(bins, i);
            }
            i++;
        }
        initializeBins(bins, 10);
    }
    delete [] bins;
}

int main(){
    int A[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(A)/sizeof(A[0]);
    RadixSort(A, n);

    cout << "Sorted Array: ";
    for (int i=0; i<n; i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

⬆ Back to Top

What is Shell Sort? Explain with an Example.

Shell Sort, introduced by Donald Shell, is useful for sorting large lists and extends the idea of Insertion Sort.
In Insertion Sort, if an array is nearly sorted, it can perform very efficiently. Shell Sort uses this principle by breaking the list into smaller segments, sorting those first, and progressively narrowing gaps between elements.

Method:

Instead of sorting elements consecutively, Shell Sort introduces a gap between elements.
The initial gap is set to half the array's length and reduces by half with each pass until it reaches 1.
With each gap, the list undergoes a modified Insertion Sort process.

Process:

Start with pointers i and j. Place i at the start and j at a position gap steps ahead.
Compare elements at i and j.
- If the element at j is smaller, swap the elements.
- Otherwise, move the pointers forward and repeat.
Continue this process across the entire list for each gap size.
After each pass, reduce the gap by half and repeat until the gap becomes 1, at which point only minor adjustments are needed.

Adaptivity: As Shell Sort is an extension of Insertion Sort, it is adaptive and performs efficiently when elements are nearly sorted.
In-place Sorting: No extra memory is required, as sorting happens within the array.
Flexible Gaps: Gaps can also be chosen based on prime numbers or other strategies.

Performance:

Time Complexity: Varies depending on gap choice. Commonly analyzed as:
- O(n log n) for general cases.
- Improved versions are analyzed as O(n^(2/3)) or O(n^(5/3)), providing faster performance with certain gap sequences.
Space Complexity: O(1) since it performs in-place sorting.
Applications: Effective for sorting large datasets due to its reduced number of comparisons over traditional methods like Insertion Sort.

Comparison with Other Sorts:

Comparison-based: Similar to Merge Sort, Shell Sort compares elements to find order but does so without requiring extra space.
Insertion Sort Relation: Shell Sort uses a larger initial gap, making it faster for large, unsorted lists compared to standard Insertion Sort.

void ShellSort(int A[], int n)
{
    int gap, i, j, temp;

    for (gap = n / 2; gap >= 1; gap /= 2)
    {
        for (i = gap; i < n; i++)
        {
            temp = A[i];
            j = i - gap;
            while (j >= 0 && A[j] > temp)
            {
                A[j + gap] = A[j];
                j = j - gap;
            }
            A[j + gap] = temp;
        }
    }
}

⬆ Back to Top

Visual Representation / Working of Different Sorting Algorithms

Hashing Techniques

What is Hashing?

Hashing is a technique used to store and retrieve data efficiently by mapping keys to indices in a hash table using a hash function. - - It ensures fast searching, insertion, and deletion.

⬆ Back to Top

Why is Hashing Useful for Searching?

Hashing provides O(1) average time complexity for searching, unlike linear search (O(n)) or binary search (O(log n)). This makes it highly efficient for large datasets.

⬆ Back to Top

How Does Hashing Work?

Hashing uses a hash function to convert a key into an index, where the value is stored in a hash table. If two keys hash to the same index, collision resolution techniques are used.

⬆ Back to Top

What are the Different Types of Mappings in Hashing?

One-to-One Mapping: Each key maps to a unique index.
- Each key maps to one index in the table.
- H(x) = x
- Uses a hash function for indexing, providing O(1) time complexity.
- Drawback: Requires array size equal to the largest element (Space consumption). Hash function can be adjusted to reduce space consumption.
Many-to-One Mapping: Multiple keys may hash to the same index, causing collisions.
- Maps keys using modulus 10, causing key collision. Uses space from 0-10.
- H(x) = x % 10
- Modifying the ideal hash function introduces collision problems.
One-to-Many Mapping: Less common, involves multiple values associated with a single key.

⬆ Back to Top

What is a Hash Collision?

A hash collision occurs when two keys map to the same index in a hash table. This is resolved using various collision handling techniques.

⬆ Back to Top

What are the Methods for Resolving Hash Collisions?

Chaining: Uses linked lists at each index.
Open Addressing: Finds another available index.
- Linear Probing: Searches sequentially for the next free slot.
- Quadratic Probing: Uses a quadratic function to find an empty slot.
- Double Hashing: Uses a second hash function to resolve collisions.

⬆ Back to Top

What is Chaining in Hashing? (With Analysis)

Chaining stores multiple values at the same index using linked lists. It allows dynamic growth but may lead to increased search time if the chain becomes too long.

Analysis:

Successful search: O(1 + λ/2)
Unsuccessful search: O(1 + λ)

where λ (load factor) = number of keys / table size.

// Linked List node
class Node{
   public:
	int data;
	Node* next;
};

// Hash Table
class HashTable{
   public:
	Node** HT;
	HashTable();
	int hash(int key);
	void Insert(int key);
	int Search(int key);
	~HashTable();
};

HashTable::HashTable() {
	HT = new Node* [10];
	for (int i=0; i<10; i++){
		HT[i] = nullptr;
	}
}

int HashTable::hash(int key) {
	return key % 10;
}

void HashTable::Insert(int key) {
	int hIdx = hash(key);
	Node* t = new Node;
	t->data = key;
	t->next = nullptr;

	// Case: No nodes in the linked list
	if (HT[hIdx] == nullptr){
		HT[hIdx] = t;
	} else {
		Node* p = HT[hIdx];
		Node* q = HT[hIdx];

		// Traverse to find insert position
		while (p && p->data < key){
			q = p;
			p = p->next;
		}

		// Case: insert position is first
		if (q == HT[hIdx]){
			t->next = HT[hIdx];
			HT[hIdx] = t;
		} else {
			t->next = q->next;
			q->next = t;
		}
	}
}

int HashTable::Search(int key) {
	int hIdx = hash(key);
	Node* p = HT[hIdx];
	while (p){
		if (p->data == key){
			return p->data;
		}
		p = p->next;
	}
	return -1;
}

HashTable::~HashTable() {
	for (int i=0; i<10; i++){
		Node* p = HT[i];
		while (HT[i]){
			HT[i] = HT[i]->next;
			delete p;
			p = HT[i];
		}
	}
	delete [] HT;
}

int main() {
	int A[] = {16, 12, 25, 39, 6, 122, 5, 68, 75};
	int n = sizeof(A)/sizeof(A[0]);
	HashTable H;
	for (int i=0; i<n; i++){
		H.Insert(A[i]);
	}
	cout << "Successful Search" << endl;
	int key = 6;
	int value = H.Search(key);
	cout << "Key: " << key << ", Value: " << value << endl;
	cout << "Unsuccessful Search" << endl;
	key = 95;
	value = H.Search(key);
	cout << "Key: " << key << ", Value: " << value << endl;
}

⬆ Back to Top

What is Linear Probing? (With Analysis)

Linear probing places colliding elements in the next available slot in a circular manner. It is simple but suffers from primary clustering.

Analysis:

Successful search: O(1 / λ * ln(1 / (1 - λ)))
Unsuccessful search: O(1 / (1 - λ))

Concepts:

Uses a modified hash function H'(x) = (H(x) + f(i)) % 10 where f(i) = i, i = 0, 1, 2, ...
Stores elements using the hash function; if collision occurs, stores in the next free space (following a linear order).
Linearly probes until a free space is found. Moves linearly; when reaching the end, it wraps around (circular probing).

Searching:

Go to H(x) % 10; if found, return.
If not found, move to the next available elements (linear search).
Searching can be time-consuming, especially for unsuccessful searches.

Time Complexity:

Successful Search: O(1 / λ * ln(1 / (1 - λ)))
Unsuccessful Search: O(1 / (1 - λ))
Deletion: Similar to linked list operations (with rehashing required in some cases).

Loading Factor:

Should be ≤ 0.5 to maintain efficiency.
A high number of keys in one place leads to primary clustering.

Drawbacks:

Half of the hash table must remain vacant (balance factor = 0.5).
Clustering leads to inefficient searching.
Deletion requires rehashing or using a deletion flag.

#include <iostream>
#define SIZE 10
using namespace std;

template <class T>
void Print(T& vec, int n, string s){
    cout << s << ": [" << flush;
    for (int i=0; i<n; i++){
        cout << vec[i] << flush;
        if (i < n-1){
            cout << ", " << flush;
        }
    }
    cout << "]" << endl;
}

int Hash(int key){
    return key % SIZE;
}

int LinearProbe(int H[], int key){
    int idx = Hash(key);
    int i = 0;
    while (H[(idx+i) % SIZE] != 0){
        i++;
    }
    return (idx + i) % SIZE;
}

void Insert(int H[], int key){
    int idx = Hash(key);

    if (H[idx] != 0){
        idx = LinearProbe(H, key);
    }
    H[idx] = key;
}

int Search(int H[], int key){
    int idx = Hash(key);
    int i = 0;
    while (H[(idx+i) % SIZE] != key){
        i++;
        if (H[(idx + i) % SIZE] == 0){
            return -1;
        }
    }
    return (idx + i) % SIZE;
}

int main() {
    int A[] = {26, 30, 45, 23, 25, 43, 74, 19, 29};
    int n = sizeof(A)/sizeof(A[0]);
    Print(A, n, " A");

    // Hash Table
    int HT[10] = {0};
    for (int i=0; i<n; i++){
        Insert(HT, A[i]);
    }
    Print(HT, SIZE, "HT");

    int index = Search(HT, 25);
    cout << "Key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "Key found at: " << index << endl;
}

⬆ Back to Top

What is Quadratic Probing? (With Analysis)

Quadratic probing is a collision resolution technique in open addressing hash tables. Unlike linear probing, it reduces primary clustering by using a quadratic function to find the next available slot.

How Quadratic Probing Works

Uses the formula H'(x) = (H(x) + f(i)) % SIZE, where f(i) = i², i = 0, 1, 2, ...
If a collision occurs at index H(x), the algorithm checks (H(x) + 1²) % SIZE, (H(x) + 2²) % SIZE, etc.
Helps reduce primary clustering but may still suffer from secondary clustering.

Analysis

Successful Search: O(-ln(1 - λ) / λ)
Unsuccessful Search: O(1 / (1 - λ)
Deletion: Requires a special flag or rehashing, similar to linked lists.

#include <iostream>
#define SIZE 10
using namespace std;

int Hash(int key) {
    return key % SIZE;
}

int QuadraticProbe(int H[], int key) {
    int idx = Hash(key);
    int i = 0;
    while (H[(idx + i * i) % SIZE] != 0) {
        i++;
    }
    return (idx + i * i) % SIZE;
}

void Insert(int H[], int key) {
    int idx = Hash(key);
    if (H[idx] != 0) {
        idx = QuadraticProbe(H, key);
    }
    H[idx] = key;
}

int Search(int H[], int key) {
    int idx = Hash(key);
    int i = 0;
    while (H[(idx + i * i) % SIZE] != key) {
        i++;
        if (H[(idx + i * i) % SIZE] == 0) {
            return -1;
        }
    }
    return (idx + i * i) % SIZE;
}

int main() {
    int A[] = {26, 30, 45, 23, 25, 43, 74, 19, 29};
    int n = sizeof(A) / sizeof(A[0]);

    int HT[SIZE] = {0};
    for (int i = 0; i < n; i++) {
        Insert(HT, A[i]);
    }

    int index = Search(HT, 25);
    cout << "Key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "Key found at: " << index << endl;
}

Advantages

Reduces primary clustering compared to linear probing.
Works efficiently if the table size is prime and the load factor is kept low.

Drawbacks

Secondary clustering still occurs.
Load factor should be kept under 0.5 to minimize performance degradation.

⬆ Back to Top

What is Double Hashing?

Double hashing is an open-addressing technique for resolving collisions in a hash table. It uses a second hash function to determine the probing sequence, ensuring a more uniform distribution of keys and reducing clustering significantly.

Uses two hash functions: H1(x) and H2(x).
Formula: H'(x) = (H1(x) + i * H2(x)) % table_size, where H2(x) ensures a different probe sequence.
Prevents primary and secondary clustering seen in linear and quadratic probing.

Analysis:

Successful Search Complexity: O(1 / λ * ln(1 / (1 - λ)))
Unsuccessful Search Complexity: O(1 / (1 - λ))

#include <iostream>
#define SIZE 10
#define PRIME 7

using namespace std;

// Utility function to print the hash table
template <class T>
void Print(T& vec, int n, string s){
    cout << s << ": [" << flush;
    for (int i=0; i<n; i++){
        cout << vec[i] << flush;
        if (i < n-1){
            cout << ", " << flush;
        }
    }
    cout << "]" << endl;
}

// Primary hash function
int Hash(int key){
    return key % SIZE;
}

// Secondary hash function for double hashing
int PrimeHash(int key){
    return PRIME - (key % PRIME);
}

// Function to find the next available index using double hashing
int DoubleHash(int H[], int key){
    int idx = Hash(key);
    int i = 0;
    while (H[(Hash(idx) + i * PrimeHash(idx)) % SIZE] != 0){
        i++;
    }
    return (idx + i * PrimeHash(idx)) % SIZE;
}

// Insert key into hash table using double hashing
void Insert(int H[], int key){
    int idx = Hash(key);

    if (H[idx] != 0){
        idx = DoubleHash(H, key);
    }
    H[idx] = key;
}

// Search for a key in the hash table
int Search(int H[], int key){
    int idx = Hash(key);
    int i = 0;
    while (H[(Hash(idx) + i * PrimeHash(idx)) % SIZE] != key){
        i++;
        if (H[(Hash(idx) + i * PrimeHash(idx)) % SIZE] == 0){
            return -1; // Key not found
        }
    }
    return (Hash(idx) + i * PrimeHash(idx)) % SIZE;
}

int main() {
    int A[] = {5, 25, 15, 35, 95};
    int n = sizeof(A)/sizeof(A[0]);
    Print(A, n, " A");

    // Hash Table
    int HT[10] = {0};
    for (int i=0; i<n; i++){
        Insert(HT, A[i]);
    }
    Print(HT, SIZE, "HT");

    int index = Search(HT, 25);
    cout << "Key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "Key found at: " << index << endl;
}

Double hashing is more efficient than linear and quadratic probing as it reduces clustering.
Uses two hash functions for better key distribution.
Helps in handling collisions effectively in a hash table.

⬆ Back to Top

Comparison: Linear Probing vs. Quadratic Probing vs. Double Hashing

Method	Pros	Cons
Linear Probing	Simple and cache-friendly	Causes primary clustering
Quadratic Probing	Reduces clustering impact	Still prone to secondary clustering
Double Hashing	Distributes keys uniformly	Slightly more computation required

⬆ Back to Top

What are Hash Functions?

A hash function transforms a key into a fixed-size value (hash code) to index data efficiently in a hash table.

⬆ Back to Top

What are the Different Types of Hash Functions?

Modulo Division: h(x) = x % table_size
Mid-Square Method: Squares the key and extracts middle digits.
Folding Method: Breaks key into parts, sums them, and hashes.
Multiplication Method: Uses multiplication by a constant factor.
Custom Hash Functions: Defined based on application needs.

⬆ Back to Top

STL

What is STL?

The Standard Template Library (STL) is a collection of template classes and functions that provide general-purpose, reusable implementations for common data structures and algorithms. The STL in C++ is designed to provide flexibility, efficiency, and ease of use for developers working with various data structures and algorithms.

⬆ Back to Top

Why Use STL?

Code Reusability: STL provides pre-built data structures and algorithms, reducing the need to implement them from scratch.
Efficiency: STL functions and classes are optimized for performance.
Flexibility: A wide variety of data structures (like vectors, sets, and maps) are available.
Consistency: STL follows a uniform structure across different containers and algorithms.

⬆ Back to Top

When to Use Which STL Container?

Container	When to Use	Time Complexity for Basic Operations
Vector	When elements need dynamic resizing and random access	O(1) access, O(n) insert/remove (from middle)
List	When frequent insertions and deletions are needed from both ends	O(1) insert/remove (from both ends)
Deque	When elements are inserted/removed from both ends	O(1) for front and back operations
Stack	When you need LIFO (Last-In, First-Out) access	O(1) push/pop, O(1) top
Queue	When you need FIFO (First-In, First-Out) access	O(1) push/pop, O(1) front/back
Priority Queue	When you need elements sorted based on priority	O(log n) for insertion/removal
Set	When you need unique elements in sorted order	O(log n) for insert/remove/search
Map	When you need key-value pairs with unique keys in sorted order	O(log n) for insert/remove/search

⬆ Back to Top

⬆ Back to Top

Main Components of STL

STL consists of four main components:

Algorithms – Sorting, searching, etc.
Containers – Data structures like vector, list, queue, etc.
Functions – Function objects for greater flexibility.
Iterators – Used to traverse containers.

⬆ Back to Top

Pairs

Pairs are used to store two related values together, making them useful for associative operations like mapping keys to values.

Basic Pair

#include <iostream>
#include <utility> // For std::pair
using namespace std;

int main() {
    pair<int, int> A = {1, 3};
    cout << A.first << " " << A.second << endl; // Output: 1 3
}

Nested Pair

Nested pairs allow storing more than two values by embedding one pair inside another.

#include <iostream>
#include <utility>
using namespace std;

int main() {
    pair<int, pair<int, int>> B = {1, {1, 3}};
    cout << B.first << " " << B.second.first << " " << B.second.second << endl; // Output: 1 1 3
}

Pair Array

An array of pairs stores multiple pairs together, useful for storing related data in sequences.

#include <iostream>
#include <utility>
using namespace std;

int main() {
    pair<int, int> Arr[] = {{1, 2}, {3, 4}, {5, 6}};
    cout << Arr[0].first << " " << Arr[0].second << endl; // Output: 1 2
}

⬆ Back to Top

Vectors

Purpose: Vectors allow you to store elements similarly to arrays but with dynamic sizing.
Iterator: Points to the memory location where elements are stored.

Basic Operations

// Create an empty vector
vector<int> A;

// Add elements to the vector
A.push_back(1);      // Adds 1 to the end
A.emplace_back(2);   // Faster than push_back

// Create a vector of pairs
vector<pair<int, int>> B;
B.push_back({1, 2});       // Adds a pair (1, 2)
B.emplace_back(1, 2);      // No need for curly braces

// Create a vector with 5 elements, each initialized to 100
vector<int> C(5, 100);

// Create a vector with 5 default-initialized elements (garbage or 0)
vector<int> D(5);
D.emplace_back(1);  // Vector automatically resizes if needed
D.emplace_back(6);  // Example of appending more elements

// Create a vector with 5 elements, each initialized to 1
vector<int> E(5, 1);

Accessing Elements

// Print elements
cout << E[0] << " " << E[1] << " " << E[2] << " " << E[3] << " " << E[4] << endl;

// Copy vector D into F
vector<int> F(D);

Using Iterators

// Initialize an iterator to the beginning of vector F
vector<int>::iterator it = F.begin();
it++;
cout << *(it) << " ";  // Output: 2nd element

it = it + 2;
cout << *(it) << " ";  // Output: 4th element

// Reverse iterator example
vector<int>::reverse_iterator itb = F.rbegin();
cout << *itb << endl;  // Output: Last element

Traversing the Vector

// Using a normal iterator
for(vector<int>::iterator it = F.begin(); it != F.end(); it++)
    cout << *(it) << " ";

// Using an auto iterator
for(auto it = F.begin(); it != F.end(); it++)
    cout << *it << " ";

// Using a range-based loop
for(auto it : F)
    cout << it << " ";

Modifying the Vector

// Erase elements
F.erase(F.begin());                 // Remove the first element
F.erase(F.begin() + 1, F.begin() + 3); // Remove a range of elements

// Insert elements
vector<int> v(2, 100);
v.insert(v.begin(), 300);           // Insert 300 at the beginning
v.insert(v.begin() + 1, 2, 10);     // Insert two 10s at the second position

// Insert elements from another vector
vector<int> copy(2, 50);
v.insert(v.begin(), copy.begin(), copy.end());  // Insert copy at the beginning

// Remove the last element
v.pop_back();

// Swap two vectors
v1.swap(v2);

// Clear the vector
v1.clear();

// Check if the vector is empty
v1.empty();

⬆ Back to Top

Lists

Purpose: list is a doubly linked list that allows easy insertion and deletion of elements from both ends.

Basic Operations

list<int> ls;

// Adding elements to the back
ls.push_back(1);
ls.push_back(2);
ls.emplace_back(3);  // Faster than push_back

// Adding elements to the front
ls.push_front(0);
ls.push_front(-1);
ls.emplace_front(-2);  // Faster than push_front

// Iterating and printing the list
for(auto l : ls)
    cout << l << " ";  // Output: -2 -1 0 1 2 3

begin, end, rbegin, rend, clear, insert, size, swap: functions are same as vector

⬆ Back to Top

Deques

Purpose: deque (Double-Ended Queue) allows fast insertion and deletion of elements from both the front and back.

Basic Operations

deque<int> dq;

// Adding elements to the back
dq.push_back(1);
dq.emplace_back(2);  // Faster than push_back

// Adding elements to the front
dq.push_front(3);
dq.emplace_front(4);  // Faster than push_front

// Iterating and printing the deque
for(auto it : dq)
    cout << it << " ";  // Output: 4 3 1 2
cout << endl;

// Removing elements from the front and back
dq.pop_back();    // Removes 2
dq.pop_front();   // Removes 4

// Printing the deque after pop operations
for(auto it : dq)
    cout << it << " ";  // Output: 3 1
cout << endl;

// Accessing the first and last elements
cout << dq.front() << " " << dq.back();  // Output: 3 1

begin, end, rbegin, rend, clear, insert, size, swap: functions are same as vectors.

⬆ Back to Top

Stack (LIFO)

Purpose: stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added is the first one removed.

Basic Operations

stack<int> s;

// Pushing elements onto the stack
s.push(1);
s.push(2);
s.push(3);
s.emplace(4);  // Faster than push

// Displaying size and top element of the stack
cout << "Size: " << s.size() << endl;        // Output: 4
cout << "Stack Top: " << s.top() << endl;    // Output: 4

// Popping elements from the stack
s.pop();  // Removes 4
s.pop();  // Removes 3

// Displaying top element and checking if the stack is empty
cout << "Stack Top: " << s.top() << endl;    // Output: 2
cout << "Stack Empty: " << s.empty() << endl; // Output: 0 (false)

// Swapping contents with another stack
stack<int> s2;
s2.swap(s);

// Displaying top element of the second stack
cout << "Stack 2 Top: " << s2.top() << endl; // Output: 2

Other functions like empty, size, and swap are commonly used and work similarly to other STL containers.

⬆ Back to Top

Queue (FIFO)

Purpose: queue is a First-In-First-Out (FIFO) data structure, meaning the first element added is the first one removed.

Basic Operations

queue<int> q;

// Pushing elements onto the queue
q.push(1);
q.push(2);
q.emplace(3);  // Faster than push

// Displaying the front and back elements
cout << "Queue Front: " << q.front() << endl;  // Output: 1
cout << "Queue Back: " << q.back() << endl;    // Output: 3

// Modifying the back element
cout << "Queue Back: " << (q.back() += 5) << endl;  // Changes 3 to 8, Output: 8

// Removing the front element
q.pop();  // Removes 1

// Displaying the front and back elements after pop
cout << "Queue Front: " << q.front() << ", Queue Back: " << q.back() << endl;  // Output: Front: 2, Back: 8

Functions like size, empty, and swap work similarly to how they are used in stack.

⬆ Back to Top

Priority Queue

Purpose: priority_queue is a data structure where the element with the highest priority (greater value by default) is always at the top.

Maximum Heap (Default Behavior)

Elements with greater values are at the top.

priority_queue<int> pq;

// Pushing elements onto the priority queue
pq.push(7);
pq.push(2);
pq.push(5);
pq.emplace(4);  // Faster than push

// Displaying the top element
cout << "Priority queue top: " << pq.top() << endl;  // Output: 7

// Removing the top element
pq.pop();

// Displaying the new top element
cout << "Priority queue top: " << pq.top() << endl;  // Output: 5

Minimum Heap

Elements with smaller values are at the top.

priority_queue<int, vector<int>, greater<int>> pmq;  // Min-heap using `greater<int>`

// Pushing elements onto the priority queue
pmq.push(5);
pmq.push(2);
pmq.push(4);
pmq.emplace(1);  // Faster than push

// Displaying the top element
cout << "Priority queue top: " << pmq.top() << endl;  // Output: 1

// Removing the top element
pmq.pop();

// Displaying the new top element
cout << "Priority queue top: " << pmq.top() << endl;  // Output: 2

Functions like size, swap, and empty work similarly to other STL containers.

⬆ Back to Top

Set

Purpose: set stores unique elements in a sorted order. It provides fast lookup and modification operations.

Basic Operations

set<int> s;

// Inserting elements
s.insert(1);
s.insert(4);
s.emplace(3);  // Faster than insert
s.insert(1);   // Duplicate, will be ignored
s.emplace(2);

// Displaying elements
for(auto it : s)
    cout << it << " ";  // Output: 1 2 3 4
cout << endl;

// Finding and erasing elements
auto it = s.find(2);
cout << *it << endl;  // Output: 2

s.erase(2);  // Removes 2

it = s.find(2);
if (it == s.end()) cout << "Element not found" << endl;  // Output: Element not found

// Counting occurrences of an element
int cnt = s.count(1);  // Output: 1 (since 1 is present)
cout << cnt << endl;

// Erasing a range of elements
auto it1 = s.find(2);
auto it2 = s.find(4);
s.erase(it1, it2);  // Removes elements from 2 to 3 (exclusive)

// Displaying elements after range erase
for(auto it : s)
    cout << it << " ";  // Output: 1 4

// Finding bounds
auto it3 = s.upper_bound(4);  // Points to the first element greater than 4
auto it4 = s.lower_bound(5);  // Points to the first element greater than or equal to 5

cout << *it3 << " " << *it4 << endl;  // Output: (undefined behavior as no elements greater than 4)

auto it5 = s.lower_bound(4);  // Finds 4 or next greater element
cout << *it5 << " ";  // Output: 4

// Using lower_bound and upper_bound with arrays
int a[] = {1, 4, 6, 8, 10};
int* ptr = lower_bound(a, a + 5, 4);  // Returns address of first element >= 4
int ind = ptr - a;
cout << *ptr << " " << ind << endl;  // Output: 4 1

int ind2 = lower_bound(s.begin(), s.end(), 4) - s.begin();
cout << ind2 << endl;  // Output: 1 (index of 4)

// Finding the next greater element after a given value
auto it6 = s.upper_bound(4);  // Finds the next greater element
int ind3 = upper_bound(a, a + 5, 4) - a;
int ind4 = upper_bound(s.begin(), s.end(), 4) - s.begin();
cout << ind3 << " " << ind4 << endl;  // Output: 2 1

Functions like begin, end, size, empty, and others work similarly to other STL containers.

⬆ Back to Top

Multiset

Purpose: multiset stores elements in a sorted order, but allows duplicate elements. Unlike set, multiset does not enforce uniqueness.

Basic Operations

multiset<int> s;

// Inserting elements
s.insert(1);
s.insert(2);
s.emplace(3);  // Faster than insert
s.insert(1);   // Duplicate allowed
s.insert(4);
s.insert(2);

// Displaying elements
for(auto i : s)
    cout << i << " ";  // Output: 1 1 2 2 3 4
cout << endl;

// Removing elements
s.erase(1);  // Removes all occurrences of 1

s.erase(s.find(2));  // Removes just one occurrence of 2

// Removing a range of elements
auto start = s.find(1);  // Iterator to the first occurrence of 1
auto end = next(start, 2);  // Iterator 2 positions ahead of 'start'
s.erase(start, end);  // Removes elements from 'start' to 'end' (exclusive)

// Displaying elements after removals
cout << endl;
for(auto i : s)
    cout << i << " ";  // Output: 2 2 3 4

Functions like begin, end, size, empty, and others work similarly to set.

⬆ Back to Top

Unordered Set

Purpose: unordered_set stores elements in a hash table, providing average constant-time complexity for insertions, deletions, and lookups. Elements are stored uniquely, but their order is not guaranteed.
Bound Functions: lower_bound and upper_bound are not available in unordered_set.

Basic Operations

unordered_set<int> s;

// Inserting elements
s.insert(1);
s.insert(2);
s.emplace(3);  // Faster than insert
s.insert(1);   // Duplicate, will be ignored
s.insert(4);

// Displaying elements
for (auto i : s)
  cout << i << " ";  // Output: (elements in arbitrary order) e.g., 1 2 3 4
cout << endl;

// Checking existence
auto it = s.find(2);
if (it != s.end())
  cout << "Element 2 found." << endl;  // Output: Element 2 found.

// Erasing elements
s.erase(1);  // Removes all occurrences of 1

s.erase(s.find(2));  // Removes just one occurrence of 2

// Displaying elements after removals
for (auto i : s)
  cout << i << " ";  // Output: (elements in arbitrary order) e.g., 3 4
cout << endl;

// Size and emptiness check
cout << "Size: " << s.size() << endl;  // Output: Size: (remaining number of elements)
cout << "Empty: " << s.empty() << endl;  // Output: Empty: (1 if empty, 0 if not empty)

// Clearing all elements
s.clear();
cout << "Size after clear: " << s.size() << endl;  // Output: Size after clear: 0

Functions: insert, erase, find, size, empty, clear work similarly to set.

⬆ Back to Top

Map

Purpose: map stores data as key-value pairs. Keys are unique and sorted. It allows efficient retrieval, insertion, and deletion operations based on the key.
Key-Value Storage: Keys are unique and sorted; values can be of any data type.

Basic Operations

// Declare maps with different key and value types
map<int, int> mp1;
map<int, pair<int, int>> mp2;
map<pair<int, int>, int> mp3;

// Inserting elements
mp1[0] = 1;                  // At key 0 store value 1
mp1.emplace(1, 2);           // At key 1 store value 2
mp1.insert({2, 3});          // At key 2 store value 3

mp3[{0, 1}] = 1;             // Insert with pair key

// Displaying all elements
for(auto it : mp1)
  cout << it.first << " " << it.second << endl;  // Output: keys and values in sorted order

// Accessing values
cout << mp1[0] << " " << mp1[1] << " " << mp1[2] << " " << mp1[4] << endl;
// Output: 1 2 3 0 (value for key 4 is 0, as default value for int is 0)

// Finding elements
auto it = mp1.find(1);
if (it != mp1.end()) {
  cout << it->first << " " << it->second << " ";  // Output: 1 2
} else {
  cout << "Key not found";
}

Functions like begin, end, size, empty, clear work similarly to other associative containers.

⬆ Back to Top

Multimap

Purpose: multimap stores data as key-value pairs where multiple elements can have the same key. Keys are unique and sorted, but values associated with each key can be multiple.
Key-Value Storage: Allows multiple values for the same key.
Key Access: Unlike map, operator[] does not work for multimap. Use insert and emplace to add elements.

Basic Operations

// Declare a multimap
multimap<int, int> mm;

// Inserting elements
mm.insert({1, 2});
mm.insert({1, 3});
mm.insert({2, 4});
mm.emplace(2, 5);
mm.insert({3, 6});

// Displaying all elements
for(auto it : mm) {
    cout << it.first << " " << it.second << endl;  // Output: keys and values in sorted order
}

// Finding elements
auto range = mm.equal_range(1); // Get the range of elements with key 1
for(auto it = range.first; it != range.second; ++it) {
    cout << it->second << " ";  // Output: 2 3
}
cout << endl;

// Removing elements
mm.erase(1);  // Removes all elements with key 1

// Displaying remaining elements
for(auto it : mm) {
    cout << it.first << " " << it.second << endl;  // Output: keys and values in sorted order after removal
}

// Using iterators
auto it = mm.find(2);
if (it != mm.end()) {
    cout << it->first << " " << it->second << " ";  // Output: 2 4 (or 2 5 depending on insertion order)
} else {
    cout << "Key not found";
}

Functions like begin, end, size, empty, clear work similarly to other associative containers.

⬆ Back to Top

Unordered Map

Purpose: unordered_map stores data as key-value pairs with unique keys, but the keys are not stored in a sorted order. It uses hashing to organize and access elements quickly.
Key-Value Storage: Allows unique keys with values.
Order: Elements are not stored in sorted order; the order is determined by the hash function.
Funtions like begin, end, size, empty, clear work similarly to other associative containers.

Basic Operations

// Declare an unordered_map
unordered_map<int, int> um;

// Inserting elements
um[0] = 1;           // Insert with key 0 and value 1
um.emplace(1, 2);    // Insert with key 1 and value 2
um.insert({2, 3});   // Insert with key 2 and value 3

// Displaying all elements
for(const auto& it : um) {
  cout << it.first << " " << it.second << endl;  // Output: keys and values in no particular order
}

// Finding elements
auto it = um.find(1); // Find key 1
if (it != um.end()) {
  cout << it->first << " " << it->second << " ";  // Output: 1 2
} else {
  cout << "Key not found";
}
cout << endl;

// Removing elements
um.erase(1);  // Removes the element with key 1

// Displaying remaining elements
for(const auto& it : um) {
  cout << it.first << " " << it.second << endl;  // Output: keys and values after removal
}

// Using iterators
auto it2 = um.begin(); // Get iterator to the first element
cout << it2->first << " " << it2->second << endl;  // Output: first element in the unordered_map

// Size and empty checks
cout << "Size: " << um.size() << endl; // Output: number of elements
cout << "Empty: " << um.empty() << endl; // Output: 0 if not empty, 1 if empty

// Clear all elements
um.clear();
cout << "Size after clear: " << um.size() << endl; // Output: 0
}

⬆ Back to Top

Algorithms

Sorting

sort: Used to sort elements in a container or array. Can sort in ascending or descending order.

// Example vector of pairs
vector<pair<int, int>> vec = {{1, 4}, {2, 3}, {4, 2}, {3, 1}};

// Sort entire vector of pairs
sort(vec.begin(), vec.end()); // Sorts by first element then second element

// Sort array in ascending order
int a[] = {4, 1, 3, 2};
int n = sizeof(a) / sizeof(a[0]);
sort(a, a + n);

// Sort a subarray (elements from index 2 to 4)
sort(a + 2, a + 4);

// Sort array in descending order
sort(a, a + n, greater<int>());

cout << "Sorted values: ";
for (const auto& p : vec) {
    cout << p.second << " "; // Print second element of each pair
}
cout << endl;

Bit Manipulation

**builtin_popcount: Counts the number of 1s in the binary representation of an integer. **builtin_popcountll: Counts the number of 1s in the binary representation of a long long integer.

int num = 7; // Binary: 0111
int cnt = __builtin_popcount(num); // Count of 1s
cout << "Number of 1s in binary representation of " << num << ": " << cnt << endl;

long long int nums = 2132142313; // Example long long integer
int cnt2 = __builtin_popcountll(nums); // Count of 1s
cout << "Number of 1s in binary representation of " << nums << ": " << cnt2 << endl;

Sorting:

sort(begin, end): Sorts elements from begin to end in ascending order.
sort(begin, end, comparator): Sorts elements using a custom comparator. Bit Manipulation:
__builtin_popcount(x): Counts the number of 1 bits in an integer.
__builtin_popcountll(x): Counts the number of 1 bits in a long long integer.

⬆ Back to Top

✨ Hope you find these OOP questions helpful! If you do, please consider starring ⭐ this repository.

📌 Check out my profile for more repositories: github.com/ahadalireach

💡 Want to contribute? Feel free to open an issue or submit a pull request! Your contributions are always welcome.

📩 For any issues or inquiries, you can also reach out via email: ahadali.reach@gmail.com

Happy Coding! 🚀🎯

ahadalireach/dsa.concepts.interview.questions

About

Topics

Resources

Uh oh!

Stars

Watchers

Forks