description: Some of my collections and notes

🧮 Data Structure and Algorithms

What is DSA?

DSA stands for Data Structure and Algorithms. It's a fundamental concept in computer science that focuses on organizing and storing data efficiently, and using algorithms to manage, manipulate, and perform operations on that data.

• Data Structures are ways of organizing data so it can be used effectively. Examples include arrays, linked lists, stacks, queues, trees, and graphs.
• Algorithms are step-by-step procedures or formulas for solving a problem. Common algorithm types include sorting, searching, optimization, and dynamic programming.

Understanding DSA is crucial for developing efficient and optimized software solutions.

How to access?

This website is available on these domains for free viewing,

• https://sharafat.gitbook.io/dsa (enriched formatting and navigation)
• https://sharafat.is-a.dev/dsa/ (lightweight and PDF export support)

To export PDF, use the second link and, the top right print button.

And source code is available on GitHub. Feel free to edit :tada:.

• https://github.com/SharafatKarim/dsa

How to use this site?

Look left, you will find a left sidebar (scrollable). Use that, for easier navigation. Currently, as of now, structure part is based on the book,

• Data structures by Seymour Lipschutz.

description: >- Some long texts I guess 😆, though we actually don't need to show formality here.

🌸 Welcome!

{% hint style="info" %} This welcome page is totally cloned from my friend sr-tamim's gitbook page. Thanks a lot for letting me steal your page 😆. No hard feelings!

• https://sr-tamim.gitbook.io/algorithm/1.intro_to_algorithms {% endhint %}

Algorithm

An algorithm is a set of well-defined steps or rules to solve a particular problem.

Key Characteristics of an Algorithm:

• Input: Data provided to the algorithm for processing.
• Output: The result produced by the algorithm.
• Definiteness: Each step should be clear and unambiguous.
• Finiteness: The algorithm should terminate after a finite number of steps.
• Effectiveness: Each step should be feasible and computable.

Types of Algorithms:

• Search algorithms: Linear search, binary search, etc.
• Sorting algorithms: Bubble sort, insertion sort, merge sort, quick sort, etc.
• Graph algorithms: Dijkstra's algorithm, A* search algorithm, etc.
• Dynamic programming algorithms: Fibonacci sequence, longest common subsequence, etc.
• Greedy algorithms: Fractional knapsack problem, Huffman coding, etc.

Data Structure

A data structure is a way of organizing and storing data to facilitate efficient access and modification. It's a container for data, designed to support specific operations.

Common data structures:

• Arrays: A collection of elements, accessed by an index.
• Linked lists: A linear data structure where elements are linked together.
• Stacks: A LIFO (Last In, First Out) data structure.
• Queues: A FIFO (First In, First Out) data structure.
• Trees: Hierarchical data structures with a root node and child nodes.
• Graphs: Non-linear data structures representing relationships between nodes.
• Hash tables: Data structures that use a hash function to map keys to values.

Relationship between Algorithms and Data Structures:

Algorithms and data structures are closely intertwined. The efficiency of an algorithm often depends on the choice of data structure. For example, searching for an element in an array is faster using a binary search algorithm if the array is sorted.

In summary:

• Algorithms provide the logic for solving problems.
• Data structures organize and store data.
• The combination of algorithms and data structures is essential for efficient problem-solving in computer science.

Time Complexity

Time complexity is a measure of how long an algorithm takes to run as a function of the input size. It's a way to evaluate the efficiency of an algorithm. Instead of measuring the exact execution time in seconds, we focus on how the running time grows as the input size increases.

Why is it important?

Understanding time complexity is crucial for:

• Choosing the right algorithm: For large datasets, even small differences in time complexity can lead to significant performance improvements.
• Optimizing code: Identifying bottlenecks and areas for improvement.
• Predicting performance: Estimating how an algorithm will perform with different input sizes.

How is it measured?

Time complexity is typically expressed using Big O notation. This notation provides an upper bound on the growth rate of the running time as the input size increases.

Common Big O notations:

1. O $(1)$: Constant time. The running time is independent of the input size.
2. O $(log n)$: Logarithmic time. The running time grows logarithmically with the input size.
3. O $(n)$: Linear time. The running time grows linearly with the input size.
4. O $(n log n)$: Linearithmic time. A combination of linear and logarithmic growth.
5. O $(n^2)$: Quadratic time. The running time grows quadratically with the input size.
6. O $(2^n)$: Exponential time. The running time grows exponentially with the input size.

Factors affecting time complexity:

• Input size: The number of elements in the input.
• Algorithm efficiency: The number of operations performed.
• Hardware and software: The speed of the computer and the programming language.

📚 Standard Template Library

I think geek for geeks is good enough for learning STL. Check that,

{% embed url="https://www.geeksforgeeks.org/containers-cpp-stl/" %}

{% hint style="info" %} I will be using c++ mostly for STL. But other languages also have respective libraries. Feel free to explore! {% endhint %}

🍽️ Prerequisites

There are some things, which may need for future understandings. Let me list some of 'em here.

Recursion

• https://www.geeksforgeeks.org/pointers-vs-references-cpp/
• https://www.geeksforgeeks.org/passing-reference-to-a-pointer-in-c/

Intro

A data structure is a particular way of organizing data in a computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks. Here are some common data structures:

• Arrays
• Linked Lists
• Stacks
• Queues
• Trees
• Graphs
• Hash Tables

Abstract Data Types

An abstract data type (ADT) is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. The interface does not give any specific details about how something should be implemented or in what programming language.

Complexity Analysis

Complexity analysis is a way to analyze the efficiency of an algorithm. It is a way to measure how an algorithm responds to an increase in the size of the input data. It is important to understand the complexity of an algorithm before using it in a real-world application. The complexity of an algorithm is usually expressed using big O notation.

External links

https://github.com/Prince-1501/Complete-DSA-Preparation

{% embed url="https://www.geeksforgeeks.org/learn-data-structures-and-algorithms-dsa-tutorial/" %}

Preliminaries (basics)

2.1 Largest element in array

Using goto with c++,

#include <iostream>
using namespace std;

void LargestElementInArray(int DATA[], int N)
{
    int K = 0, LOC = 0, MAX = DATA[0];
increment_counter:
    K = K + 1;
    if (K == N)
    {
        cout << "LOC = " << LOC << ", MAX = " << MAX << "\n";
        return;
    }
    if (MAX < DATA[K])
    {
        LOC = K;
        MAX = DATA[K];
    }
    goto increment_counter;
}

int main()
{
    int DATA[] = {3, 5, 9, 2};
    int N = sizeof(DATA) / sizeof(int);
    LargestElementInArray(DATA, N);
    return 0;
}

2.2 Quadratic equation

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    int D = B * B - 4 * A * C;
    if (D > 0)
    {
        float X1 = (-B + sqrt(D)) / (2 * A);
        float X2 = (-B - sqrt(D)) / (2 * A);
        cout << X1 << " and " << X2 << "\n";
    }
    else if (D == 0)
    {
        float X = -B / 2 * A;
        cout << "UNIQUE SOLUTION : " << X << "\n";
    }
    else 
    {
        cout << "NO REAL SOLUTIONS" << "\n";
    }
    return 0;
}

2.3 Largest element in array (while loop)

#include <iostream>
using namespace std;

void LargestElementInArray(int DATA[], int N)
{
    int K = 0, LOC = 0, MAX = DATA[0];
    while (K < N)
    {
        if (MAX < DATA[K])
        {
            LOC = K;
            MAX = DATA[K];
        }
        K = K + 1;
    }
    cout << "LOC = " << LOC << ", MAX = " << MAX << "\n";
}

int main()
{
    int DATA[] = {3, 5, 9, 2};
    int N = sizeof(DATA) / sizeof(int);
    LargestElementInArray(DATA, N);
    return 0;
}

Same code as 2.1 but this time with while loop. Steps are as described as DS textbook (SEYMOUR LIPSCHUTZ)

2.4 Linear search

#include <iostream>
using namespace std;

void LinearSearch(int DATA[], int N, int ITEM)
{
    int K = 0, LOC = -1;
    while (LOC == -1 && K < N)
    {
        if (ITEM == DATA[K])
            LOC = K;
        K = K + 1;
    }
    if (LOC == -1)
        cout << "ITEM is not on the array DATA\n";
    else
        cout << LOC << " is the location of ITEM\n";
    return;
}

int main()
{
    int DATA[] = {3, 5, 9, 2};
    int N = sizeof(DATA) / sizeof(int);
    int ITEM = 9;
    LinearSearch(DATA, N, ITEM);
    return 0;
}

String Processing

3.1 Delation

Let's start with some string processing algorithms. The first string processing algorithm is deletion. I'm not actually writin codes for finding the index and deleting the character at that index with user functions. I'm just using the built-in functions of the string class. Feel free to write your own functions.

#include<iostream>
using namespace std;

int main()
{
    // this algorithm deletes every occurrence of pattern from str
    string str = "To be or not 2B, that is the ?";
    string pattern = "B,";

    int index = str.find(pattern);
    while (index != -1)
    {
        str.erase(index, pattern.length());
        index = str.find(pattern);
    }

    cout << str << endl;    
}

And instead of built in function, you can also rewrite your own functions! Here's an example,

#include<iostream>
using namespace std;

int searchPattern(string str, string pattern) {
    int pattern_length = pattern.length();
    int string_length = str.length();

    for (int i=0; i <= string_length - pattern_length; i++) {
        for (int j=0; j <pattern_length; j++) {
            if (str[i+j] != pattern[j]) {
                break;
            } else if (j == pattern_length - 1) {
                return i;
            }
        }
    }
    return -1;
}

string eraseABit(string str, int index, int pattern_length) {
    string temp = "";
    int length = str.length();

    for (int i=0; i <length; i++) {
        if (index <= i && i <= index+pattern_length-1) {
            continue;
        }
        temp += str[i];
    }

    return temp;
}

int main()
{
    string str = "To be or not 2B, that is the B,?";
    string pattern = "B,";

    int index = searchPattern(str, pattern);

    while (index != -1)
    {
        str = eraseABit(str, index, pattern.length());
        index = searchPattern(str, pattern);
    }

    cout << str << endl;
}

3.2 Replacement

The next string processing algorithm is replacement. This algorithm replaces every occurrence of a pattern with another pattern. Again, I'm using the built-in functions of the string class.

#include<iostream>
using namespace std;

int main()
{
    // this algorithm replaces every occurrence of pattern from str with placeholder
    string str = "To be or not 2B, that is the ? that is 2B decided for future!";
    string pattern = "2B";
    string placeholder = "to be";

    int index = str.find(pattern);
    while (index != -1)
    {
        str.replace(index, pattern.length(), placeholder);
        index = str.find(pattern);
    }

    cout << str << endl;    
}

As an alternative, replace can also be done with erase and insert functions.

    // str.replace(index, pattern.length(), placeholder);
    str.erase(index, pattern.length());
    str.insert(index, placeholder);

Or, perhaps your own custom function?

#include<iostream>
using namespace std;

int searchPattern(string str, string pattern) {
    int pattern_length = pattern.length();
    int string_length = str.length();

    for (int i=0; i <= string_length - pattern_length; i++) {
        for (int j=0; j <pattern_length; j++) {
            if (str[i+j] != pattern[j]) {
                break;
            } else if (j == pattern_length - 1) {
                return i;
            }
        }
    }
    return -1;
}

string eraseABit(string str, int index, int pattern_length) {
    string temp = "";
    int length = str.length();

    for (int i=0; i <length; i++) {
        if (index <= i && i <= index+pattern_length-1) {
            continue;
        }
        temp += str[i];
    }

    return temp;
}

string insertABit(string str, int index, string placeholder) {
    string temp = "";
    int length = str.length();

    for (int i=0; i <length; i++) {
        if (i == index) {
            temp += placeholder;
        }
        temp += str[i];
    }

    return temp;
}

int main()
{
    string str = "To be or not 2B, that is the?";
    string pattern = "2B";
    string placeholder = "to be";

    int index = searchPattern(str, pattern);
    str = eraseABit(str, index, pattern.length());
    str = insertABit(str, index, placeholder);

    cout << str << endl;
}

3.3 Pattern Matching

Pattern matching is the process of checking whether a given sequence of characters (pattern) is present in a given string or not. The simplest way to do this is to check each substring of the string with the pattern. If the substring matches the pattern, then return the index of the substring in the string. Otherwise, return -1.

#include <iostream>
using namespace std;

int patternMatching(string str, int str_len, string pattern, int pattern_len)
{
    if (pattern_len > str_len)
        return -1;

    int k = 0, max = str_len - pattern_len + 1;
    while (k < max)
    {
        for (int l = 0; l < pattern_len; l++)
        {
            if (pattern[l] != str[l + k])
                break;
            if (l + 1 == pattern_len)
                return k;
        }
        k++;
    }
    return -1;
}

int main()
{
    string str = "To be or not 2B, that is the ?";
    string pattern = "B,";
    int index = patternMatching(str, str.length(), pattern, pattern.length());
    cout << "Index is : " << index << endl;
    return 0;
}

Array and matrix

Array is the basic data structure for storing, right?
Let's take a look,

4.1 Traversing

In traversing, we will visit every single element. Why?
Well, it's up to you. For now let's print!

#include <iostream>
using namespace std;

void traverse_1(int arr[], int lower_bound, int upper_bound) {
    int temp = lower_bound;
    while (temp <= upper_bound) {
        cout << arr[temp] << " ";
        temp++;
    }
    cout << endl;
}

void traverse_2(int arr[], int lower_bound, int upper_bound) {
    for (int i = lower_bound; i <= upper_bound; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    traverse_1(arr, 0, 4);
    traverse_2(arr, 0, 4);
}

4.2 Insertion into an array

As arrays are stored linearly, so what if I want to insert something in the middle?
yeah! We have to shift things around!

#include <iostream>
using namespace std;

int insert(int arr[], int n, int k, int item) {
    // for (int i = n - 1; i >= k; i--) {
    //     arr[i + 1] = arr[i];
    // }
    
    int j = n - 1;
    while (j >= k) {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[k] = item;
    return n + 1;
}

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

int main() {
    int arr[50] = {1, 2, 3, 4, 5};
    int n = 5; // number of elements in the array
    int k = 2; // position to insert a new value
    int item = 10; // value to insert

    n = insert(arr, n, k - 1, item);
    printArray(arr, n);
}

Here, commented lines are the implemention of the same while logic in if logic. Hope you got that!

4.3 Deletion in arrays

It's just like insertion but much simpler!

#include <iostream>
using namespace std;

int deleteElement(int arr[], int n, int k) {
    // int item = arr[k]; // for processing     
    for (int j=k; j < n-1; j++) {
        arr[j] = arr[j+1];
    }
    return n - 1;
}

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

int main() {
    int arr[50] = {1, 2, 3, 4, 5};
    int n = 5; // number of elements in the array
    int k = 2; // position to deleteElement a new value

    n = deleteElement(arr, n, k - 1);
    printArray(arr, n);
}

{% hint style="info" %} In above codes, I didn't include corner case handlers or any validators, so it's up to you. Nothing to worry much here, I guess. {% endhint %}

4.4 Bubble Sort

As an example on how to do operation on array, let's sort. We will pick bubble buddy for now.

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

void bubbleSort(int *arr, int n) {
    for (int i=0; i< n; i++) {
        for (int j=0; j < n-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

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

int main() {
    int arr[] = {12, 2, 39, -4, 25};
    bubbleSort(arr, sizeof(arr)/sizeof(int));
    printArray(arr, sizeof(arr)/sizeof(int));
}

4.5 Linear Search

And for searching with O(n) complexity,

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int item) {
    for (int i=0; i < n; i++) {
        if (arr[i] == item) {
            return i;
        }
    } // While loop? Try yourself!
    return -1;
}

int main() {
    int arr[] = {12, 2, 39, -4, 25};
    int item = 39;
    cout << linearSearch(arr, sizeof(arr)/sizeof(int), item) << endl;
}

4.6 Binary Search

Accordingly, let's divide and conquer. Get your sword ready to slice the array into half, XD.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int item) {
    int lower_bound = 0;
    int upper_bound = n - 1;
    while (lower_bound <= upper_bound) {
        int mid = (lower_bound + upper_bound) / 2;
        if (arr[mid] == item) {
            return mid;
        } else if (arr[mid] < item) {
            lower_bound = mid + 1;
        } else {
            upper_bound = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {12, 2, 39, -4, 25};
    int item = 39;
    cout << binarySearch(arr, sizeof(arr)/sizeof(int), item) << endl;
}

4.7 Matrix multiplication

And how about 2D array? Let's multiply 2 matrix,

#include <iostream>
using namespace std;

void matrixMultiplication(int matrix_a[][3], int matrix_b[][3], int M, int P, int N) {
    int matrix_c[M][N];
    for (int i=0; i < M; i++) {
        for (int j=0; j < N; j++) {
            matrix_c[i][j] = 0;
            for (int k=0; k < P; k++) {
                matrix_c[i][j] += matrix_a[i][k] * matrix_b[k][j];
            }
        }
    }
    for (int i=0; i < M; i++) {
        for (int j=0; j < N; j++) {
            cout << matrix_c[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int matrix_a[][3] = {{1, -2, 3}, {0, 4, 5}}; // M x P
    int matrix_b[][3] = {{3, 0, -6}, {2, -3, 1}, {2, 5, 3}}; // P x N

    matrixMultiplication(matrix_a, matrix_b, 2, 3, 3);
}

So, we passed an array normally to do something, but what if I want back that array?

Pointer (2D array)

Here's the fun thing, pointer, which will pass as reference,

#include <iostream>
using namespace std;

int** createMatrix(int row, int column) {
    int **matrix = new int*[row];
    for (int i=0; i < row; i++) {
        matrix[i] = new int[column];
    }
    return matrix;
}

void printMatrix(int **matrix, int row, int column) {
    for (int i=0; i < row; i++) {
        for (int j=0; j < column; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

void deleteMatrix(int **matrix, int row) {
    for (int i=0; i < row; i++) {
        delete[] matrix[i];
    }
    delete[] matrix;
}

void matrixMultiplication(int matrix_a[][3], int matrix_b[][3], int **matrix_c, int M, int P, int N) {
    for (int i=0; i < M; i++) {
        for (int j=0; j < N; j++) {
            matrix_c[i][j] = 0;
            for (int k=0; k < P; k++) {
                matrix_c[i][j] += matrix_a[i][k] * matrix_b[k][j];
            }
        }
    }
}

int main() {
    int matrix_a[][3] = {{1, -2, 3}, {0, 4, 5}}; // M x P
    int matrix_b[][3] = {{3, 0, -6}, {2, -3, 1}, {2, 5, 3}}; // P x N

    int **matrix_c;
    matrix_c = createMatrix(2, 3);

    matrixMultiplication(matrix_a, matrix_b, matrix_c, 2, 3, 3);
    printMatrix(matrix_c, 2, 3);
    deleteMatrix(matrix_c, 2);
}

In this way, we can do more than just copy. Hope it helps :).

Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

{% hint style="info" %} This page will be a bit large. Use the right sidebar to navigate withing the page (desktop mode). {% endhint %}

The methodology

There are different ways to implement linked list, like using structures. But I will be using class (OOP) for simplicity. Feel free to use any other websites for exploring different approaches.

5.1 Traversing

To traverse we will use a simple loop. Check this headless code,

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class LinkedList {
private:
    Node *start;
public:
    LinkedList() {
        start = NULL;
    }
    void printAll() {
        if (start == NULL) {
            cout << "List is empty!\n";
            return;
        }
        Node *temp = start;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.printAll();
}

Here for storing data we have used an structure. You may use a class as well for this. Here as for the constructor, we are assigning our head/ start node to NULL. In the printAll method we are using our actual algorithm. As the list is empty, it will print List is empty.

5.2 Searching

Just like in searching, we will traverse and compare!

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class LinkedList {
private:
    Node *start;
public:
    LinkedList() {
        start = NULL;
    }
    Node *search(int item) {
        if (start == NULL) {
            cout << "List is empty!\n";
            return NULL;
        }
        Node *temp = start;
        while (temp != NULL) {
            if (temp->data == item) {
                return temp;
            }
            temp = temp->link;
        }
        return NULL;
    }
};

int main() {
    LinkedList list;
    list.search(5);
}

Here, it'll also print the list is empty. So we actually need some method to append some data into our list so that we can actually display some output. Right?

Let's try altogether in the next example!

5.3 Searching a sorted list

The list is sorted? Yeah! So we can just terminate if we find a value higher that we are aiming.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class LinkedList {
private:
    Node *start;
public:
    LinkedList() {
        start = NULL;
    }
    void insertFirst(int data) {
        Node *new_node = new Node(data);
        new_node->link = start;
        start = new_node;
    }
    void printAll() {
        if (start == NULL) {
            cout << "List is empty!\n";
            return;
        }
        Node *temp = start;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
    Node *search(int item) {
        if (start == NULL) {
            cout << "List is empty!\n";
            return NULL;
        }
        Node *temp = start;
        while (temp != NULL) {
            if (temp->data == item) {
                return temp;
            }
            temp = temp->link;
        }
        return NULL;
    }
    Node *searchSorted(int item) {
        if (start == NULL) {
            cout << "List is empty!\n";
            return NULL;
        }
        Node *temp = start;
        while (temp != NULL) {
            if (temp->data < item)
                temp = temp->link;
            else if (temp->data == item)
                return temp;
        }
        return NULL;
    }
};

int main() {
    LinkedList list;
    list.insertFirst(10);
    list.insertFirst(20);
    list.printAll();
    Node *found_1 = list.search(10);
    if (found_1 != NULL) {
        cout << "Found: " << found_1->data << endl;
    } else {
        cout << "Not found!\n";
    }
    Node *found_2 = list.searchSorted(10);
    if (found_2 != NULL) {
        cout << "Found: " << found_2->data << endl;
    } else {
        cout << "Not found!\n";
    }
}

5.4 Insert at the beginning

Well, here's two thing to consider, if a list is empty then you are the king, MR. DATA. And otherwise we just have to tweak our start/ header node a bit, right? Check the above code's insertFirst method.

5.5 Insert at a location

We can actually insert at a location if we know the location, right? Hope you can imagine that,

void insertIntoLocation(Node *location, int item) {
        if (location == NULL) {
            insertFirst(item);
            return;
        }
        Node *new_node = new Node(item);
        new_node->link = location->link;
        location->link = new_node;
    }

Here we are inserting an item (int) in the location. But the location is a pointer of our node, right? So how can we get this? We have already seen that in 5.2.

Let's assume it's a sorted list. Now what?

5.6 Location of Upper Bound - 1

What is upper bound?
If I have an array with 1 2 2 4 elements, then the upper bound of 3 is position 3 (0 base index). Right?

But for our previous 5.4 algorithm to work, we need the location of last occurrence of 2, so our title is, upper bound - 1

Let's look at the code,
here we need to trace the history.

    Node *findLastSmaller(int item) {
        Node *temp = start;
        Node *prev = NULL;
        while (temp != NULL) {
            if (temp->data < item) {
                prev = temp;
                temp = temp->link;
            } else {
                return prev;
            }
        }
        return prev;
    }

5.7 Insertion in a sorted list

So if we implement two methods we developed in 5.4 and 5.5, our code will be,

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class LinkedList {
private:
    Node *start;
public:
    LinkedList() {
        start = NULL;
    }
    void insertFirst(int data) {
        Node *new_node = new Node(data);
        new_node->link = start;
        start = new_node;
    }
    void insertIntoLocation(Node *location, int item) {
        if (location == NULL) {
            insertFirst(item);
            return;
        }
        Node *new_node = new Node(item);
        new_node->link = location->link;
        location->link = new_node;
    }
    Node *findLastSmaller(int item) {
        Node *temp = start;
        Node *prev = NULL;
        while (temp != NULL) {
            if (temp->data < item) {
                prev = temp;
                temp = temp->link;
            } else {
                return prev;
            }
        }
        return prev;
    }
    void printAll() {
        if (start == NULL) {
            cout << "List is empty!\n";
            return;
        }
        Node *temp = start;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insertFirst(20);
    list.insertFirst(10);
    list.printAll();
    Node *location = list.findLastSmaller(15);
    list.insertIntoLocation(location, 15);
    list.printAll();
}

{% hint style="danger" %} It has a limitation. While inserting into a sorted list, if the item is greater than all the elements in the list, it will not insert the item at the end of the list. It will insert the item at the beginning of the list. So, we need to modify the code to handle this case.

Use 25 instead of 15 in the above code, you will get the fact.

• To solve this issue, we can use an another method like,

    void insertIntoSorted(int item) {
        if (start == NULL || start->data >= item) {
            insertFirst(item);
            return;
        }
        Node *location = findLastSmaller(item);
        if (location == NULL) {
            insertLast(item);
            return;
        }
        insertIntoLocation(location, item);
    }

{% endhint %}

5.8 Delete at a position

For deletion, we will require two locations,

• location which value will be erased
• location before the erased value

Why? If we don't have the previous value we need to traverse once more! Or perhaps 2 way linked list? We will check both of 'em. But wait a bit longer for 2 way linked list.

So our basic method is like,

    void deleteAtLocation(Node *location, Node *prev_location) {
        if (prev_location == NULL) {
            start = start->link;
        } else {
            prev_location->link = location->link;
        }
        delete location;
    }

5.9 Location and it's previous location!

We can use an extra variable for preserving previous location, right? Let's check a method,

    void findLocationAndPrev(int item, Node *&location, Node *&prev) {
        prev = NULL;
        location = start;
        while (location != NULL) {
            if (location->data == item) {
                return;
            } else {
                prev = location;
                location = location->link;
            }
        }
        location = NULL;
        return;
    }

5.10 Deletion at the first occurrence

Now combining 5.8 and 5.9 we can achieve this, right? Here's full code,

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class LinkedList {
private:
    Node *start;
public:
    LinkedList() {
        start = NULL;
    }
    void insertFirst(int data) {
        Node *new_node = new Node(data);
        new_node->link = start;
        start = new_node;
    }
    void insertLast(int data) {
        if (start == NULL) {
            insertFirst(data);
            return;
        }
        Node *temp = start;
        while (temp->link != NULL) {
            temp = temp->link;
        }
        Node *new_node = new Node(data);
        temp->link = new_node;
    }

    void deleteAtLocation(Node *location, Node *prev_location) {
        if (prev_location == NULL) {
            start = start->link;
        } else {
            prev_location->link = location->link;
        }
        delete location;
    }
    void findLocationAndPrev(int item, Node *&location, Node *&prev) {
        prev = NULL;
        location = start;
        while (location != NULL) {
            if (location->data == item) {
                return;
            } else {
                prev = location;
                location = location->link;
            }
        }
        location = NULL;
        return;
    }
    void deleteItem(int item) {
        Node *location, *prev;
        findLocationAndPrev(item, location, prev);
        if (location == NULL) {
            cout << "Item not found!\n";
            return;
        }
        deleteAtLocation(location, prev);
    }

    void printAll() {
        if (start == NULL) {
            cout << "List is empty!\n";
            return;
        }
        Node *temp = start;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insertFirst(20);
    list.insertFirst(10);
    list.insertFirst(30);
    list.printAll();

    list.deleteItem(30);
    list.printAll();
}

I think, this concludes the basics!
There are even more things that can be achieved. So good luck! For now let's explore two more perspective,

• header linked list
• 2 way linked list

and finally we can combine them together into,

• 2 way header linked list

Header linked lists

Let's think in this way, in linked lists, when we iterate, what is our sentinel (the point where we stop our loop) value? Well, it's until we actually find NULL. Right?

To make this looping steps a lil bit easy and NULL free, we are trying this header linked list! Out of two kinds, grounded and circular, we will be using circular.

5.11 Traversing Circular Header List

So just like our 5.1 Traversing, we are traversing, but a bit difference in the looping steps. Compare to understand.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class HeaderLinkedList {
private:
    Node *start;
public:
    HeaderLinkedList() {
        start = NULL;
    }
    void insertAtBeginning(int data) {
        Node *new_node = new Node(data);
        if (start == NULL) {
            start = new Node(0);
            start->link = new_node;
            new_node->link = start;
            return;
        }
        new_node->link = start->link;
        start->link = new_node;
    }
    void listAll() {
        if (start == NULL) {
            cout << "List is empty" << endl;
            return;
        }
        Node *temp = start->link;
        while (temp != start) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    HeaderLinkedList list;
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(50);
    list.insertAtBeginning(5);
    list.listAll();
    return 0;
}

5.12 Searching in Header list

We will return the first occurance (position). So our code is,

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class HeaderLinkedList {
private:
    Node *start;
public:
    HeaderLinkedList() {
        start = NULL;
    }
    void insertAtBeginning(int data) {
        Node *new_node = new Node(data);
        if (start == NULL) {
            start = new Node(0);
            start->link = new_node;
            new_node->link = start;
            return;
        }
        new_node->link = start->link;
        start->link = new_node;
    }
    Node *search(int data) {
        if (start == NULL) {
            cout << "List is empty" << endl;
            return NULL;
        }
        Node *temp = start->link;
        while (temp != start) {
            if (temp->data == data) {
                return temp;
            }
            temp = temp->link;
        }
        cout << "Element not found" << endl;
        return NULL;
    }
    void listAll() {
        if (start == NULL) {
            cout << "List is empty" << endl;
            return;
        }
        Node *temp = start->link;
        while (temp != start) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    HeaderLinkedList list;
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(50);
    list.insertAtBeginning(5);
    list.listAll();
    Node *searched = list.search(10);
    if (searched != NULL) {
        cout << "Element found: " << searched->data << endl;
    }
    return 0;
}

5.13 Searching location and previous location

Just like 5.9, let's implement this one,

    void findLocationAndPrev(int item, Node **prev_location, Node **location) {
        *prev_location = start;
        Node *temp = start->link;
        while (temp != start) {
            if (temp->data == item) {
                *location = temp;
                return;
            }
            *prev_location = temp;
            temp = temp->link;
        }
        *location = NULL;
    }

5.14 Deletion in Header list

With the support of 5.13 we can finally delete a node just like 5.10, right?

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        link = NULL;
    }
};

class HeaderLinkedList {
private:
    Node *start;
public:
    HeaderLinkedList() {
        start = NULL;
    }
    void insertAtBeginning(int data) {
        Node *new_node = new Node(data);
        if (start == NULL) {
            start = new Node(0);
            start->link = new_node;
            new_node->link = start;
            return;
        }
        new_node->link = start->link;
        start->link = new_node;
    }
    Node *search(int data) {
        if (start == NULL) {
            cout << "List is empty" << endl;
            return NULL;
        }
        Node *temp = start->link;
        while (temp != start) {
            if (temp->data == data) {
                return temp;
            }
            temp = temp->link;
        }
        cout << "Element not found" << endl;
        return NULL;
    }
    
    void findLocationAndPrev(int item, Node **prev_location, Node **location) {
        *prev_location = start;
        Node *temp = start->link;
        while (temp != start) {
            if (temp->data == item) {
                *location = temp;
                return;
            }
            *prev_location = temp;
            temp = temp->link;
        }
        *location = NULL;
    }
    void deleteAtLocation(int item) {
        Node *prev_location, *location;
        findLocationAndPrev(item, &prev_location, &location);
        if (location == NULL) {
            cout << "Element not found" << endl;
            return;
        }
        prev_location->link = location->link;
        delete location;
    }

    void listAll() {
        if (start == NULL) {
            cout << "List is empty" << endl;
            return;
        }
        Node *temp = start->link;
        while (temp != start) {
            cout << temp->data << " ";
            temp = temp->link;
        }
        cout << endl;
    }
};

int main() {
    HeaderLinkedList list;
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(50);
    list.insertAtBeginning(5);
    list.listAll();
    list.deleteAtLocation(50);
    list.listAll();
    return 0;
}

Two Way Lists

In two way lists, besides storing the next elements location of each node, we will also gather the previous value's location. And it's more fun if we combine, two way lists and headers lists together! Let's rip it,

5.15 Deletion in 2-way header

So when we have the location, we can actually link the previous one and the next one altogether to perform teh deletion! So our method is like,

    void deleteAtPostion(Node *current) {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

5.16 Insertion in 2-way header

Likewise, if we have the positions of two nodes, we can insert easily like,

    void insertInBetween(int item, Node *prev, Node *next) {
        Node* newNode = new Node();
        newNode->data = item;
        newNode->next = next;
        newNode->prev = prev;
        prev->next = newNode;
        next->prev = newNode;
        size++;
    }

Finally if we wrap 5.15 and 5.16 altogether,

#include <iostream>
using namespace std;

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

class Header2WayLinkedList {
    Node* head;
    Node* tail;
    int size;
public:
    Header2WayLinkedList() {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    void insertBefore(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = head->next;
        newNode->prev = head;
        head->next->prev = newNode;
        head->next = newNode;
        size++;
    }

    void insertInBetween(int item, Node *prev, Node *next) {
        Node* newNode = new Node();
        newNode->data = item;
        newNode->next = next;
        newNode->prev = prev;
        prev->next = newNode;
        next->prev = newNode;
        size++;
    }

    void getLocationAndPrev(int data, Node* &location, Node* &prev) {
        location = head->next;
        prev = head;
        while (location != tail) {
            if (location->data == data) {
                return;
            }
            prev = location;
            location = location->next;
        }
        location = NULL;
    }        

    void deleteAtPostion(Node *current) {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

    void remove(int data) {
        Node* current = head->next;
        while (current != tail) {
            if (current->data == data) {
                deleteAtPostion(current);
                return;
            }
            current = current->next;
        }
    }

    void print() {
        Node* current = head->next;
        while (current != tail) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    int getSize() {
        return size;
    }
};

int main() {
    Header2WayLinkedList list;
    list.insertBefore(1);
    list.insertBefore(2);
    list.insertBefore(3);
    list.insertBefore(4);
    list.insertBefore(5);
    list.print();

    list.remove(4);
    list.print();
    
    Node *location, *prev;
    list.getLocationAndPrev(3, location, prev);
    if (location == NULL) {
        cout << "Not found" << endl;
    } else {
        list.insertInBetween(4, prev, location);
    }
    list.print();

    return 0;
}

{% hint style="info" %} Here I didn't show the implementation of every single items. So best wishes for you! It's more fun to implement rather than just reading. Good luck! {% endhint %}

Python implementation

Once I implemented it on python. If you are familliar with python you can check that out for reference from time to time,

{% embed url="https://gist.github.com/SharafatKarim/0e299e5a115293b4116f8d78076920e2" %} python implementation {% endembed %}

Stack & Queue

Stack Basics

In C++ STL has stacks built in, nothing to fear!

6.1 Push

Insert something to the stack.

#include<iostream>
#include <stack>

using namespace std;

void stack_push_stl() {
    stack<int> st;
    st.push(5);
    cout << st.top() << "\n";
}

int main() {
    stack_push_stl();
    return 0;
}

6.2 Pop

Delete something from the stack!

#include<iostream>
#include <stack>

using namespace std;

void stack_pop_stl() {
    stack<int> st;
    st.push(5);
    st.push(3);
    while (!st.empty()) {
        cout << "-> " << st.top() << "\n";
        st.pop();
    }
}

int main() {
    stack_pop_stl();
    return 0;
}

But if you want to implement this manually like STL does?

Stack Library

An example stack class template,

#include <iostream>
using namespace std;
#define MAX_NUM 1000

template <typename T> class Stack {
    private:
        long long top;
        T arr[MAX_NUM];
    public:
        Stack() {top=-1;}
        T Push(T obj) {
            arr[++top] = obj;
            return arr[top];
        } long long Pop() {
            if (this ->isEmpty())
                return top;
            return --top;
        } T Peek() {
            return arr[top];
        } bool isEmpty() {
            return (top == -1);
        }
};

int main() {
    Stack<int> s;
    s.Push(5);
    cout << s.Peek() << endl;
    cout << (s.isEmpty()?"True":"False") << endl;
    s.Pop();
    cout << (s.isEmpty()?"True":"False") << endl;
    return 0;
}

Postfix notation

Intro

Imagine a pc solving an infix or prefix notation. A bit weird, right?

To solve this issue, we actually use postfix! It's actually kinda easy to solve postfix, but a bit tough to convert from infix to postfix.

First comes the way to solve a postfix notation,

6.3 Postfix Equation solve

#include<iostream>
#include <stack>
#include <queue>

using namespace std;

string solvePostfix_1(queue<string> input_list) {
    stack<string> st;
    while (!input_list.empty()) {
        string token = input_list.front();
        input_list.pop();
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            string operand2 = st.top();
            st.pop();
            string operand1 = st.top();
            st.pop();
            if (token == "+") {
                st.push(to_string(stoi(operand1) + stoi(operand2)));
            } else if (token == "-") {
                st.push(to_string(stoi(operand1) - stoi(operand2)));
            } else if (token == "*") {
                st.push(to_string(stoi(operand1) * stoi(operand2)));
            } else if (token == "/") {
                st.push(to_string(stoi(operand1) / stoi(operand2)));
            }
        } else {
            st.push(token);
        }
    }
    return st.top();
}

string solvePostfix_2(queue<string> input_list) {
    stack<string> st;
    int first_operator, second_operator;
    while (!input_list.empty()){
        switch (input_list.front().at(0))
        {
        case '+':
            second_operator = stoi(st.top()); st.pop();
            first_operator = stoi(st.top()); st.pop();
            st.push(to_string( first_operator + second_operator ));
            break;
        
        case '-':
            second_operator = stoi(st.top()); st.pop();
            first_operator = stoi(st.top()); st.pop();
            st.push(to_string( first_operator - second_operator ));
            break;
        
        case '*':
            second_operator = stoi(st.top()); st.pop();
            first_operator = stoi(st.top()); st.pop();
            st.push(to_string( first_operator * second_operator ));
            break;
        
        case '/':
            second_operator = stoi(st.top()); st.pop();
            first_operator = stoi(st.top()); st.pop();
            st.push(to_string( first_operator / second_operator ));
            break;
        
        default:
            st.push(input_list.front());
            break;
        }
        input_list.pop();
    }
    return st.top();
}

int main() {
    queue<string> input_list({"5","6","2","+","*","12","4","/","-"});
    cout << solvePostfix_1(input_list) << "\n";
    cout << solvePostfix_2(input_list) << "\n";
    return 0;
}    

Here solvePostfix_1 and solvePostfix_2 are 2 different approach. Nothing to worry. But why queue? Actually you can just go ahead and use string or whatever you like, but think of,

512+, is it 5+12 or 51+2 ?

That's the reason of my using queue. And here I just solved an equation but how about the converstion from infix to postfix?

6.4 Postfix conversation

#include<iostream>
#include <stack>
#include <queue>

using namespace std;

int precendenceReturn(string str) {
    switch (str.at(0))
    {
    case '+':
        return 1;
        break;
    case '-':
        return 1;
        break;
    case '*':
        return 2;
        break;
    case '/':
        return 2;
        break;
    case '^':
        return 3;
        break;
    default:
        return 0;
        break;
    }
}

string toPostfix(queue<string> input_list) {
    stack<string> st;
    string postfix = "";
    input_list.push(")");
    while (!input_list.empty()) {
        string token = input_list.front();
        input_list.pop();
        if (token == "+" || token == "-" || token == "*" || token == "/" || token == "^") {
            if (!st.empty() && precendenceReturn(st.top()) > precendenceReturn(token)) {
                postfix += st.top();
                st.pop();
            }
            st.push(token);
        } else if (token == "(") {
            st.push(token);
        } else if (token == ")") {
            while (!st.empty()) {
                if (st.top() == "(") {st.pop(); break;}
                postfix += st.top();
                st.pop();
            }
        } else {
            postfix += token;
        }
    }
    return postfix;
}

int main() {
    // Well we can take input from the user in this way [OPTIONAL]
    // -------------------------------------------------------------------
    // string input;
    // // cin >> input; // If there is space in input this line won't gonna work
    // getline(cin, input); // Taking whole line as input
    // queue<string> input_list;
    // string temp_string = "";
    // for (int i = 0; i < input.size(); i++) {
    //     if (input[i] == ' ') continue; // Avoiding spaces
    //     if (isdigit(input[i])) temp_string += input[i];
    //     else { 
    //         if(!temp_string.empty()) input_list.push(temp_string); 
    //         temp_string = ""; 
    //         input_list.push(string(1, input[i]));
    //     }
    // }
    // if(!temp_string.empty()) input_list.push(temp_string); 

    // The following lines are to print the queue (input list)
    // But the queue will be empty later on [WARNING]
    // while (input_list.size()) {
    //     cout << input_list.front() << " ";
    //     input_list.pop();
    // }

    // Or, We can Directly initialize our queue in this way [OPTIONAL]
    // -------------------------------------------------------------------
    queue<string> input_list({"A","+","(","B","*","C","-","(","D","/","E","^","F",")","*","G",")","*","H"});
    // queue<string> input_list({"A","+","B"}); // Simpler one!
    
    // Finally we can call our function toPostfix
    // -------------------------------------------------------------------
    cout << toPostfix(input_list) << "\n";
    
    return 0;
}

Here a lot of lines are commented out, right? Well, it's so that you can just take the input from the user.

The full version

So how about combining these 2, so that we can take input from the user in anyway he likes, and then solving it? Here's the combined edition (and you can understand why we used queue),

#include<iostream>
#include <stack>
#include <queue>
#include <math.h>

using namespace std;

string solvePostfix(queue<string> input_list) {
    stack<string> st;
    while (!input_list.empty()) {
        string token = input_list.front();
        input_list.pop();
        if (token == "+" || token == "-" || token == "*" || token == "/" || token == "^") {
            string operand2 = st.top();
            st.pop();
            string operand1 = st.top();
            st.pop();
            if (token == "+") {
                st.push(to_string(stoi(operand1) + stoi(operand2)));
            } else if (token == "-") {
                st.push(to_string(stoi(operand1) - stoi(operand2)));
            } else if (token == "*") {
                st.push(to_string(stoi(operand1) * stoi(operand2)));
            } else if (token == "/") {
                st.push(to_string(stoi(operand1) / stoi(operand2)));
            } else if (token == "^") {
                st.push(to_string(pow(stoi(operand1), stoi(operand2))));
            }
        } else {
            st.push(token);
        }
    }
    return st.top();
}

int precendenceReturn(string str) {
    switch (str.at(0))
    {
    case '+':
        return 1;
        break;
    case '-':
        return 1;
        break;
    case '*':
        return 2;
        break;
    case '/':
        return 2;
        break;
    case '^':
        return 3;
        break;
    default:
        return 0;
        break;
    }
}

queue<string> toPostfix(queue<string> input_list) {
    stack<string> st;
    queue<string> postfix;
    input_list.push(")");
    while (!input_list.empty()) {
        string token = input_list.front();
        input_list.pop();
        if (token == "+" || token == "-" || token == "*" || token == "/" || token == "^") {
            if (!st.empty() && precendenceReturn(st.top()) > precendenceReturn(token)) {
                postfix.push(st.top());
                st.pop();
            }
            st.push(token);
        } else if (token == "(") {
            st.push(token);
        } else if (token == ")") {
            while (!st.empty()) {
                if (st.top() == "(") {st.pop(); break;}
                postfix.push(st.top());
                st.pop();
            }
        } else {
            postfix.push(token);
        }
    }
    return postfix;
}

// // Debugging purpose
// void printQueue(queue<string> input_list) {
//     while (!input_list.empty()) {
//         cout << " <-" << input_list.front() << "-> ";
//         // cout << input_list.front();
//         input_list.pop();
//     }
// }

int main() {
    // Well we can take input from the user in this way [OPTIONAL]
    // -------------------------------------------------------------------
    string input;
    // cin >> input; // If there is space in input this line won't gonna work
    getline(cin, input); // Taking whole line as input
    queue<string> input_list;
    string temp_string = "";
    for (int i = 0; i < input.size(); i++) {
        if (input[i] == ' ') continue; // Avoiding spaces
        if (isdigit(input[i])) temp_string += input[i];
        else { 
            if(!temp_string.empty()) input_list.push(temp_string); 
            temp_string = ""; 
            input_list.push(string(1, input[i]));
        }
    }
    if(!temp_string.empty()) input_list.push(temp_string); 

    // The following lines are to print the queue (input list)
    // But the queue will be empty later on [WARNING]
    // while (input_list.size()) {
    //     cout << input_list.front() << " ";
    //     input_list.pop();
    // }

    // Or, We can Directly initialize our queue in this way [OPTIONAL]
    // -------------------------------------------------------------------
    // queue<string> input_list({"A","+","(","B","*","C","-","(","D","/","E","^","F",")","*","G",")","*","H"});
    // queue<string> input_list({"A","+","B"}); // Simpler one!
    
    // Finally we can call our function solvePostfix and toPostfix
    // -------------------------------------------------------------------
    cout << solvePostfix(toPostfix(input_list)) << "\n";
    
    return 0;
}

{% hint style="info" %} Example Input:

4+ 2 ^ 2

Example Output:

8 {% endhint %}

Altered Edition

One more approach, if you are not comfortable with queue approach for handling values!

#include <bits/stdc++.h>

using namespace std;

void postfixEval(string str) {
    vector<string> main;

    string temp = "";
    for (auto i: str) {
        if (i == ' ') {
            main.push_back(temp);
            temp = "";
            continue;        }
            temp += i;
    }
    if (temp  != "") main.push_back(temp);

    stack<string> st;
    for (auto i: main) {
        // cout << "->" << i << endl;
        if (i == "+") {
            int b = stoi(st.top());
            st.pop();

            int a = stoi(st.top());
            st.pop();

            st.push(to_string(a + b));
        } else if (i == "-") {
            int b = stoi(st.top());
            st.pop();

            int a = stoi(st.top());
            st.pop();

            st.push(to_string(a - b));
        } else if (i == "*") {
            int b = stoi(st.top());
            st.pop();

            int a = stoi(st.top());
            st.pop();

            st.push(to_string(a * b));
        } else if (i == "/") {
            int b = stoi(st.top());
            st.pop();

            int a = stoi(st.top());
            st.pop();

            st.push(to_string(a / b));
        } else
            st.push(i);
    }

    cout << st.top();
}

int precendenceReturn(string a) {
    if (a == "+" || a == "-") {
        return 1;
    } else if (a == "*" || a == "/") {
        return 2;
    } else if (a == "^") {
        return 3;
    } else {
        return 0;
    }
}

bool precedenceCheck(string a, string b) {
    return precendenceReturn(a) > precendenceReturn(b);
}

string toPostfix(string str) {
    vector<string> main;

    string temp = "";
    for (auto i: str) {
        if (i == ' ') {
            main.push_back(temp);
            temp = "";
            continue;        }
            temp += i;
    }
    main.push_back(temp);
    main.push_back(")");

    stack<string> st;
    st.push("(");
    string exp = "";
    for (auto i: main) {
        if (i == "(") {
            st.push(i);
        } else if (i == "+" || i == "-" || i == "*" || i == "/" || i == "^") {
            while (precedenceCheck(st.top(), i)) {
                exp += st.top() + " ";
                st.pop();
            } st.push(i);
        } else if (i == ")") {
            while (st.top() != "(") {
                exp += st.top() + " ";
                st.pop();
            } st.pop();
        } else
            exp += i + " ";
    }

    return exp;
}

int main() {
    string str;
    str = "1 + 5 * 62 - 1";
    // cout << toPostfix(str);
    postfixEval(toPostfix(str));
    return 0;
}

Quick Sort

Let's apply quick sort with stack (not recursion)

6.5 Quick sort process

It's the underlying process, which is used in every single step,

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int quickSortProcess(int *arr, int beg, int end) {
    int left = beg, right = end, loc = beg;
    while (true) {
        while (arr[loc] <= arr[right] && loc != right) {
            right--;
        } if (loc == right) return loc; 
        if (arr[loc] > arr[right]) {
            swap(&arr[loc], &arr[right]);
            loc = right;
        } 
        
        while (arr[loc] >= arr[left] && loc != left) {
            left++;
        } if (loc == left) return loc;
        if (arr[loc] < arr[left]) {
            swap(&arr[loc], &arr[left]);
            loc = left;
        }
    }
}

int main() {
    int arr[] = {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66};
    cout << "Final pivot location : " << quickSortProcess(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1) << "\n";
    
    cout << "And the array is : " << "\n";
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        cout << arr[i] << " ";
    }
}

6.6 Quick sort (full)

And now if we implement the above trick, with support of stack,
our quick sort will quite look like this one,

#include <iostream>
#include <stack>
using namespace std;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int quickSortProcess(int *arr, int beg, int end) {
    int left = beg, right = end, loc = beg;
    while (true) {
        while (arr[loc] <= arr[right] && loc != right) {
            right--;
        } if (loc == right) return loc; 
        if (arr[loc] > arr[right]) {
            swap(&arr[loc], &arr[right]);
            loc = right;
        } 
        
        while (arr[loc] >= arr[left] && loc != left) {
            left++;
        } if (loc == left) return loc;
        if (arr[loc] < arr[left]) {
            swap(&arr[loc], &arr[left]);
            loc = left;
        }
    }
}

void quickSort(int *arr, int beg, int end) {
    stack<int> lower, upper;
    lower.push(beg);
    upper.push(end);
    while (!lower.empty()) {
        int loc = quickSortProcess(arr, lower.top(), upper.top());
        beg = lower.top(), end = upper.top();
        lower.pop(), upper.pop();
        if (loc + 1 < end) {
            lower.push(loc+1);
            upper.push(end);
        } if (beg < loc - 1 ) {
            lower.push(beg);
            upper.push(loc - 1);
        }
    }
}

int main() {
    int arr[] = {44, 33, -15, 55, 77, 90, 40, 60, 99, 22, 88, 66};
    quickSort(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1);
    
    cout << "And the sorted array is : " << "\n";
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        cout << arr[i] << " ";
    }
}

Recursion

As we know recursion, the situation where a function is caleed from inside of that function right?

Let's have some examples,

6.7 Factorial

#include<iostream>
using namespace std;

int factorialWithLoop(int n) {
    if (n == 0) return 1;
    int fact = 1;
    for (int i=1; i <= n; i++) {
        fact *= i;
    } return fact;
}

int factorialWithRecursion(int n) {
    if (n == 0) return 1;
    return n * factorialWithRecursion(n-1);
}

int main() {
    int n = 4;
    cout << factorialWithLoop(n) << "\n";
    cout << factorialWithRecursion(n) << "\n";
}

Here both, with and without recursion, trick is shown. Let's have an another one,

6.8 Fibonacci series

The trick will return the value at that place, (don't get confused with sum of Fibonacci series)

#include<iostream>
using namespace std;

int fibonacciSeries(int n) {
    // This function will return the n'th value of the fibonacci series
    if (n == 0 || n == 1) return n;
    return fibonacciSeries(n-1) + fibonacciSeries(n-2);
}

int main() {
    int n = 10;
    cout << fibonacciSeries(n) << "\n";
}

Tower of Hanoi

An interesting game right?

If you don't know about this game, take a look here,

{% embed url="https://www.mathsisfun.com/games/towerofhanoi.html" %} just play and learn {% endembed %}

So to solve it (displaying the steps), carefully analyze what actually happens when you have one and two disks. Then try to recreate the scenario with 3 disks. Maybe you can find a recursive approach here, here's the code,

6.9 Tower of Hanoi (Recursion)

#include<iostream>
using namespace std;

void towerOfHanoi(int n, char beg, char aux, char end) {
    if (n==1) {
        cout << beg << " -> " << end << "\n";
        return;
    }
    towerOfHanoi(n-1, beg, end, aux);
    towerOfHanoi(1, beg, aux, end);
    towerOfHanoi(n-1, aux, beg, end);
}

int main() {
    towerOfHanoi(4, 'A', 'B', 'C');
}

So, with recursion it's too short and feels simple right?

It's not this simple if you want to apply this thing with stack instead of recusion. A bit of trial and error perhaps?

6.10 Tower of Hanoi (Stack)

It's the iterative approach of the above code with stack,

#include<iostream>
#include<stack>
using namespace std;

void towerOfHanoi(int n, char beg, char aux, char end) {
    int add = 2;
    stack<char> st_beg, st_aux, st_end;
    stack<int> st_n, st_add;
    
    while (true) {
        if (n == 1) {
            cout << beg << " -> " << end << "\n";
            add = 5;
        }
        if (add == 2) {
            st_beg.push(beg), st_aux.push(aux), st_end.push(end);
            st_n.push(n), st_add.push(3);
            beg = st_beg.top();
            aux = st_end.top();
            end = st_aux.top();
            n--;
        }
        if (add == 3) {
            cout << beg << " -> " << end << "\n";
            st_beg.push(beg), st_aux.push(aux), st_end.push(end);
            st_n.push(n), st_add.push(5);
            beg = st_aux.top();
            aux = st_beg.top();
            end = st_end.top();
            n--;
            add = 2;
        }
        if (add == 5) {
            if (st_beg.empty()) return;
            beg = st_beg.top();
            aux = st_aux.top();
            end = st_end.top();
            n = st_n.top();
            add = st_add.top();
            st_beg.pop(), st_aux.pop(), st_end.pop(); 
            st_add.pop(), st_n.pop();
        }
    }
}

int main() {
    towerOfHanoi(3, 'A', 'B', 'C');
}

Or, perhaps one even more minimal approach? (Taught to me by MH Nazmul)

#include <bits/stdc++.h>
using namespace std;

void hanoi_stack(int n, char beg, char aux, char end) {
    stack<pair<int, vector<char>>> st;
    st.push({n, {beg, aux, end}});

    while (!st.empty()) {
        int n = st.top().first;
        char beg = st.top().second[0];
        char aux = st.top().second[1];
        char end = st.top().second[2];
        st.pop();
        if (n == 1) {
            cout << beg << " -> " << end << endl;
        } else {
            st.push({n-1, {aux, beg, end}});
            st.push({1, {beg, aux, end}});
            st.push({n-1, {beg, end, aux}});
        }
    }
}

int main() {
    hanoi_stack(3, 'A', 'B', 'C');
}

Queue

Just like stack I hope you can go ahead and implement queue like you did stack with STL in c++. For reference, just use your favorite search engine.

So here's an implementation of queue with class,

6.11 Insertion of queue

In the insertion method, suppose you have total 3 space. And there's an element on 3 but not 1 and 2. So if you just simply use a linked list then, you will have overflow error. But you can actually utilize that 1 and 2 space. Here's the implementation,

int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }

6.12 Deletion of queue

T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }

And finally the full queue template

Queue (full code)

#include <iostream>
using namespace std;
#define MAX_NUM 3

template <typename T> class queue
{
private:
    long long front;
    long long rear;
    T arr[MAX_NUM];
public:
    queue() {
        front = -1;
        rear = -1;
    }
    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }
    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }
    T peek() {
        return arr[front];
    }
    T back() {
        return arr[rear];
    }
};

int main() {
    queue<int> data;
    data.insert(1);
    data.insert(2);
    data.insert(3);
    data.pop();
    data.insert(4); // front 1, rear 0
    data.insert(5);
    cout << data.peek();
    cout << data.back();
    return 0;
}

Priority Queue (one way list)

In priority queue it's just like a queue, but you have to place values with higher priority on the top of the list. Also available in STL. Read here,

{% embed url="https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/" %}

And just like queue you can also implement manually.

6.13 Deletion in priority Queue

To delete we just simple delete like the previous time,

    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }

6.14 Insertion in priority queue

And for insertion, we can go ahead and implement a one way list.
And if you want, you can also try something similar that we did in queue. In this case, we will try to use our free spaces, left in the memory!

    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }

Priority Queue (one way list)

So, here's a full implementation.

#include <iostream>
using namespace std;
#define MAX_NUM 3

template <typename T> class queue
{
private:
    long long front;
    long long rear;
    T arr[MAX_NUM];
public:
    queue() {
        front = -1;
        rear = -1;
    }
    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }
    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }
    T peek() {
        return arr[front];
    }
    T back() {
        return arr[rear];
    }
};

int main() {
    queue<int> data;
    data.insert(1);
    data.insert(2);
    data.insert(3);
    data.pop();
    data.insert(4); // front 1, rear 0
    data.insert(5);
    cout << data.peek();
    cout << data.back();
    return 0;
}

If it's a bit difficult, maybe you can try to do something like,

{% embed url="https://www.geeksforgeeks.org/priority-queue-set-1-introduction/" %}

But in this case it can be more time-consuming than my implementation, cause, here whenever you pop out an element you actually shift the rest.

Priority Queue (2D matrix)

2D matrix? Imagine having each row indicating the priority!

For now, I will be using the code we wrote for queue,

template <typename T> class queue {
private:
    long long front;
    long long rear;
    T arr[MAX_NUM];
public:
    queue() {
        front = -1;
        rear = -1;
    }
    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }
    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }
    T peek() {
        return arr[front];
    }
    T back() {
        return arr[rear];
    }
    bool isEmpty() {
        return front == -1;
    }
};

And we will create another class to implement the 2D matrix like queue. Confused?
Let's take a look,

6.15 Deletion from priority queue (2D matrix)

Once you have the support of base queue class, it's quite easy to implement a 2D matrix :)

    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }

6.16 Insertion into priority queue (2D matrix)

    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }

To wrap it up, here's the full edition,

Priority Queue (2D with queue)

#include <iostream>
using namespace std;
#define MAX_NUM 2

template <typename T> class queue {
private:
    long long front;
    long long rear;
    T arr[MAX_NUM];
public:
    queue() {
        front = -1;
        rear = -1;
    }
    int insert(T item) {
        if ((front == 0 && rear == MAX_NUM - 1) || (front == rear + 1)) {
            cout << "OVERFLOW!\n";
            return -1;
        } 
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_NUM - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = item;
        return rear;
    }
    T pop() {
        if (front == -1) {
            cout << "UNDERFLOW!\n";
            return (T)0;
        }
        T item = arr[front];
        if (front == rear) 
            front = -1, rear = -1;
        else if (front == MAX_NUM - 1)
            front = 0;
        else
            front++;
        return item;
    }
    T peek() {
        return arr[front];
    }
    T back() {
        return arr[rear];
    }
    bool isEmpty() {
        return front == -1;
    }
};

template <typename T> class PriorityQueue {
private:
    queue<T> arr_queue[MAX_NUM];
public:
    int insert(T item, long long priority) {
        if (priority > MAX_NUM || priority < 1) {
            cout << "INVALID PRIORITY!\n";
            return -1;
        }
        return arr_queue[priority - 1].insert(item);
    }
    T pop() {
        long long index = 0;
        while (arr_queue[index].isEmpty() && index != MAX_NUM ) {
            index++;
        }
        if (index == MAX_NUM) return (T)0;
        return arr_queue[index].pop();
    }
    T peek() {
        long long index = 0;
        while (arr_queue[index].isEmpty() && index != MAX_NUM ) {
            index++;
        }
        if (index == MAX_NUM) return (T)0;
        return arr_queue[index].peek();
    } 
    T back() {
        long long index = MAX_NUM - 1;
        while (arr_queue[index].isEmpty() && index != -1 ) {
            index--;
        }
        if (index == -1) return (T)0;
        return arr_queue[index].back();
    }
    bool isEmpty() {
        long long index = 0;
        while (arr_queue[index].isEmpty() && index != MAX_NUM ) {
            index++;
        }
        if (index == MAX_NUM) return true;
        return false;
    }
};

int main() {
    PriorityQueue<int> queue_list;
    queue_list.insert(2, 1);
    queue_list.insert(4, 2);
    queue_list.insert(2, 1);
    queue_list.pop();
    queue_list.insert(1, 1);
    // cout << queue_list.isEmpty();
    cout << queue_list.peek();
    cout << queue_list.back();
    return 0;
}

Want something smaller? Why not try to implement it with STL?

Good luck 🏁

Tree

Binary Tree

Binary tree is more like a tree with at most two branches per each node. So you can easily implement it with linked list. In the programming, you can just go ahead and make your class with left and right pointer variables or perhaps a structure in c++?

Implementation

Here's an example structure,

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

To insert elements, we can implement a function which will simply return the instance of the above structure.

Node *insert(Node *root, int data) {
    Node *newNode = new Node(data);
    if (root == NULL) {
        root = newNode;
        return root;
    }
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        if (temp->left == NULL) {
            temp->left = newNode;
            return root;
        } else {
            q.push(temp->left);
        }
        if (temp->right == NULL) {
            temp->right = newNode;
            return root;
        } else {
            q.push(temp->right);
        }
    }
    return root;
}

7.1 Preorder Traversal

While traversing, each node has left and right elements, and let's not forget the root. So if we print or process root at first and then left and right node sequentially, that will be our preorder. Things can be a bit tricky if our tree is long. So, we can actually go ahead and use stack for implementing so,

void preOrderTraversal_Iterative(Node *root) {
    stack<Node*> s;
    s.push(root);
    while (!s.empty()) {
        Node *temp = s.top();
        s.pop();
        cout << temp->data << " ";
        if (temp->right != NULL) {
            s.push(temp->right);
        }
        if (temp->left != NULL) {
            s.push(temp->left);
        }
    }
}

Want even more crazier method? Check this code and laugh later!

void preOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    preOrderTraversal_Recursion(root->left);
    preOrderTraversal_Recursion(root->right);
}

Preety kool, right?

7.2 Inorder Traversal

In inorder traversal just like preorder we will visit our fellow members but the difference is that we will visit our root after traversing the lefter one!

void inOrderTraversal_Iterative(Node *root) {
    stack<Node*> s;
    Node *curr = root;
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        cout << curr->data << " ";
        curr = curr->right;
    }
}

And for the recursion, just like before, but print after first call,

void inOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal_Recursion(root->left);
    cout << root->data << " ";
    inOrderTraversal_Recursion(root->right);
}

7.3 Postorder Traversal

Finally in postorder we will visit our root after we visit it's left and right childrens. Interesting right?

Let's implement in this way,

void postOrderTraversal_Iterative(Node *root) {
    stack<pair<Node*, bool>> s;
    s.push(make_pair(root, true));
    while (!s.empty()) {
        Node *temp = s.top().first;
        bool right_sided = s.top().second;
        if (right_sided) {
            s.pop();
            while(temp != NULL) {
                s.push(make_pair(temp, false));
                if (temp->right != NULL) {
                    s.push(make_pair(temp->right, true));
                }
                temp = temp->left;
            } 
        }
        right_sided = s.top().second;
        if (!right_sided) {
            cout << s.top().first->data << " ";
            s.pop();
        }
    }
}

Please check the text book for understanding the above code. Here we are using pair for storing two characteristics per each stack element. But feel free to use any other method.

Here's an another interesting method, where we can just go ahead and use 2 different stack for storing and organizing our elements,

void postOrderTraversal_Iterative_2(Node *root) {
    stack<Node*> s1;
    stack<Node*> s2;
    s1.push(root);
    while (!s1.empty()) {
        Node *temp = s1.top();
        s1.pop();
        s2.push(temp);
        if (temp->left != NULL) {
            s1.push(temp->left);
        }
        if (temp->right != NULL) {
            s1.push(temp->right);
        }
    }
    while (!s2.empty()) {
        cout << s2.top()->data << " ";
        s2.pop();
    }
}

And finally le'ts not forget recursion, my most favorite (cause it's easy),

void postOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal_Recursion(root->left);
    postOrderTraversal_Recursion(root->right);
    cout << root->data << " ";
}

And yeah, feel free to try building in your way!

Wrapping up!

Before wrapping lem'me share an another interesting traversing method, that may come handy later, level order traversing,

void levelOrderTraversal(Node *root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        cout << temp->data << " ";
        if (temp->left != NULL) {
            q.push(temp->left);
        }
        if (temp->right != NULL) {
            q.push(temp->right);
        }
    }
}

It's like how we actually build our tree. Kool, right?

Here's the full code, you can go ahead and execute,

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

Node *insert(Node *root, int data) {
    Node *newNode = new Node(data);
    if (root == NULL) {
        root = newNode;
        return root;
    }
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        if (temp->left == NULL) {
            temp->left = newNode;
            return root;
        } else {
            q.push(temp->left);
        }
        if (temp->right == NULL) {
            temp->right = newNode;
            return root;
        } else {
            q.push(temp->right);
        }
    }
    return root;
}
    
void preOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    preOrderTraversal_Recursion(root->left);
    preOrderTraversal_Recursion(root->right);
}

void preOrderTraversal_Iterative(Node *root) {
    stack<Node*> s;
    s.push(root);
    while (!s.empty()) {
        Node *temp = s.top();
        s.pop();
        cout << temp->data << " ";
        if (temp->right != NULL) {
            s.push(temp->right);
        }
        if (temp->left != NULL) {
            s.push(temp->left);
        }
    }
}

void inOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal_Recursion(root->left);
    cout << root->data << " ";
    inOrderTraversal_Recursion(root->right);
}

void inOrderTraversal_Iterative(Node *root) {
    stack<Node*> s;
    Node *curr = root;
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        cout << curr->data << " ";
        curr = curr->right;
    }
}

void postOrderTraversal_Recursion(Node *root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal_Recursion(root->left);
    postOrderTraversal_Recursion(root->right);
    cout << root->data << " ";
}

void postOrderTraversal_Iterative(Node *root) {
    stack<Node*> s1;
    stack<Node*> s2;
    s1.push(root);
    while (!s1.empty()) {
        Node *temp = s1.top();
        s1.pop();
        s2.push(temp);
        if (temp->left != NULL) {
            s1.push(temp->left);
        }
        if (temp->right != NULL) {
            s1.push(temp->right);
        }
    }
    while (!s2.empty()) {
        cout << s2.top()->data << " ";
        s2.pop();
    }
}

void levelOrderTraversal(Node *root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        cout << temp->data << " ";
        if (temp->left != NULL) {
            q.push(temp->left);
        }
        if (temp->right != NULL) {
            q.push(temp->right);
        }
    }
}

int main() {
    Node *tree = NULL;
    tree = insert(tree, 10);
    tree = insert(tree, 20);
    tree = insert(tree, 30);
    tree = insert(tree, 40);
    tree = insert(tree, 50);
    tree = insert(tree, 60);
    tree = insert(tree, 70);
    tree = insert(tree, 80);
    tree = insert(tree, 90);
    tree = insert(tree, 100);

    cout << "Preorder Traversal (Recursion): ";
    preOrderTraversal_Recursion(tree);
    cout << endl;
    cout << "Preorder Traversal (Iterative): ";
    preOrderTraversal_Iterative(tree);
    cout << endl;
    cout << "Inorder Traversal (Recursion): ";
    inOrderTraversal_Recursion(tree);
    cout << endl;
    cout << "Inorder Traversal (Iterative): ";
    inOrderTraversal_Iterative(tree);
    cout << endl;
    cout << "Postorder Traversal (Recursion): ";
    postOrderTraversal_Recursion(tree);
    cout << endl;
    cout << "Postorder Traversal (Iterative): ";
    postOrderTraversal_Iterative(tree);
    cout << endl;

    cout << "Level Order Traversal: ";
    levelOrderTraversal(tree);
    cout << endl;

    return 0;
}

Binary Search Tree

It's just binary tree with some logic! Here our tree has some properties like, our root will be greater than everything of it's left and will be less than it's right subtree and so on... So why? What's the point?

Well, here's the thing, it'll let us find either an elelment exist in our tree or not in O(log_2 n) time complexity. Pretty kool, right?

7.4 Find

Before inserting values, let's actually try to find a value exists in our tree or not. We will iterate through our tree to find the location and previous location of whatever we search for. So if our location is NULL we can just go ahead and use that information while inserting.

void find(Node *&root, Node *&location, Node *&previous, int item) {
    location = root;
    previous = NULL;
    if (location == NULL) {
        return;
    }
    while (location != NULL) {
        if (item == location -> data) {
            return;
        } 
        if (item < location -> data) {
            previous = location;
            location = location -> left;
        }
        else {
            previous = location;
            location = location -> right;
        }
    }
}

Here we are passing pointer as a reference! Pretty kool, right? We will be using these values later!

7.5 Insert

In insertion we will simply use the data of above method. And as always if it's NULL we will try to add that node.

void insert(Node *&root, int item) {
    Node *location, *previous;
    find(root, location, previous, item);
    if (location != NULL) return;
    if (previous == NULL)
        root = new Node(item);
    else if (item < previous -> data) 
        previous -> left = new Node(item);
    else 
        previous -> right = new Node(item);
}

Suppose we have the location of a node and the location of it's parent node and we are gonna delete that node.

7.6 Delete with one child

We will be deleting nodes if any node of our tree has only one child. So we can just go ahead and check either it has a left child or right child and act accordingly.

void delete_with_one_child(Node *&root, Node *&location, Node *&parent) {
    Node *child;
    if (location -> left != NULL) 
        child = location -> left;
    else if (location -> right != NULL)
        child = location -> right;
    else 
        child = NULL;
    
    if (parent != NULL) {
        if (location == parent -> left) 
            parent -> left = child;
        else 
            parent -> right = child;
    } else {
        root = child;
    }
}

But what if we have two child?

7.7 Delete with two child

In this case, things are bit tricky, cause we have to consider which of the successor will take the place of the node that we delete. And actually if we iterate through the right node's left element and so on, we will eventually meet with that guy. Next we can use the above trick to get rid of that alongside joining our new node with parent.

void delete_with_two_children(Node *&root, Node *&location, Node *&parent) {
    Node *successor, *parent_successor;
    parent_successor = location;
    successor = location -> right;
    while (successor -> left != NULL) {
        parent_successor = successor;
        successor = successor -> left;
    }
    delete_with_one_child(root, successor, parent_successor);
    if (parent != NULL) {
        if (location == parent -> left) 
            parent -> left = successor;
        else 
            parent -> right = successor;
    } else {
        root = successor;
    }
    successor -> left = location -> left;
    successor -> right = location -> right;
}

7.8 Deleting an element

As we have seen in the 7.6 and 7.7, we will be needing address of the node that we want to delete. And here in this step we will work around this. We will use 7.4 to find the address of our node and parent and will try to determine either it has one child or two child!

void delete_node(Node *&root, int item) {
    Node *location, *parent;
    find(root, location, parent, item);
    if (location == NULL) return;
    if (location -> left != NULL && location -> right != NULL) 
        delete_with_two_children(root, location, parent);
    else 
        delete_with_one_child(root, location, parent);
    delete location;
}

Wrapping up!

After combining all of the above algorithms here's a full executable code,

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

void find(Node *&root, Node *&location, Node *&previous, int item) {
    location = root;
    previous = NULL;
    if (location == NULL) {
        return;
    }
    while (location != NULL) {
        if (item == location -> data) {
            return;
        } 
        if (item < location -> data) {
            previous = location;
            location = location -> left;
        }
        else {
            previous = location;
            location = location -> right;
        }
    }
}

void insert(Node *&root, int item) {
    Node *location, *previous;
    find(root, location, previous, item);
    if (location != NULL) return;
    if (previous == NULL)
        root = new Node(item);
    else if (item < previous -> data) 
        previous -> left = new Node(item);
    else 
        previous -> right = new Node(item);
}

void delete_with_one_child(Node *&root, Node *&location, Node *&parent) {
    Node *child;
    if (location -> left != NULL) 
        child = location -> left;
    else if (location -> right != NULL)
        child = location -> right;
    else 
        child = NULL;
    
    if (parent != NULL) {
        if (location == parent -> left) 
            parent -> left = child;
        else 
            parent -> right = child;
    } else {
        root = child;
    }
}

void delete_with_two_children(Node *&root, Node *&location, Node *&parent) {
    Node *successor, *parent_successor;
    parent_successor = location;
    successor = location -> right;
    while (successor -> left != NULL) {
        parent_successor = successor;
        successor = successor -> left;
    }
    delete_with_one_child(root, successor, parent_successor);
    if (parent != NULL) {
        if (location == parent -> left) 
            parent -> left = successor;
        else 
            parent -> right = successor;
    } else {
        root = successor;
    }
    successor -> left = location -> left;
    successor -> right = location -> right;
}

void delete_node(Node *&root, int item) {
    Node *location, *parent;
    find(root, location, parent, item);
    if (location == NULL) return;
    if (location -> left != NULL && location -> right != NULL) 
        delete_with_two_children(root, location, parent);
    else 
        delete_with_one_child(root, location, parent);
    delete location;
}

void preorder(Node *root) {
    if (root == NULL) return;
    cout << root -> data << " ";
    preorder(root -> left);
    preorder(root -> right);
}

void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root -> left);
    cout << root -> data << " ";
    inorder(root -> right);
}

void level_order(Node *root) {
    if (root == NULL) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *current = q.front();
        q.pop();
        cout << current -> data << " ";
        if (current -> left != NULL) q.push(current -> left);
        if (current -> right != NULL) q.push(current -> right);
    }
}

int main() {
    Node* tree = NULL;
    insert(tree, 60);
    insert(tree, 25);
    insert(tree, 75);
    insert(tree, 15);
    insert(tree, 50);
    insert(tree, 66);
    insert(tree, 33);
    insert(tree, 44);

    cout << "Before Deletion -> \n";
    cout << "Preorder -> \n";
    preorder(tree);
    cout << "\nInorder -> \n";
    inorder(tree);
    cout << "\nLevel Order -> \n";

    delete_node(tree, 25);

    cout << "After Deletion -> \n";
    cout << "Preorder -> \n";
    preorder(tree);
    cout << "\nInorder -> \n";
    inorder(tree);
    cout << "\nLevel Order -> \n";
    level_order(tree);
}

Heap and Heap Sort

Thinking about heap sort?

well, you are on the right place. Let's get started!

It's another type of binary tree, just like binary seach tree. Here the root is equal or greater than it's childrens. It's also called max heap. Min heap is the vice-versa edition of it!

{% hint style="info" %} For now we will be represing this in a linear array unlike previous two times. And yeah, in programming array's index starts from 0, but we will be storing elements from 1 index for our convenience. {% endhint %}

7.9 Insertion

While inserting, we will simply add it to your linear array, and compare it with it's parent (N/2). If parent is smaller than our new node, we will go higher. In this way we will iterate, until we find our root.

    void insert(T item) {
        if (size == MAX) {
            cout << "Heap is full\n";
            return;
        }
        size++;
        int temp = size, temp_parent;
        while (temp > 1) {
            temp_parent = temp / 2;
            if (item <= arr[temp_parent]) {
                arr[temp] = item;
                return;
            } 
            arr[temp] = arr[temp_parent];
            temp = temp_parent;
        }
        arr[temp] = item;
    }

7.10 Delete Heap

In this step, we will actually delete our topmost index.

Our top most index in a max heap is the highest element, right?

Here we will remove the top element and image the last element is on the top. Now we have to move our top most element (actually the last), to the appropriate place by continuously iterating.

    T deleteMax() {
        T item = arr[1];
        T last = arr[size];
        size--;
        int temp = 1, left = 2, right = 3;
        while (right <= size) {
            if (last >= arr[left] && last >= arr[right]) {
                arr[temp] = last;
                return item;
            }
            if (arr[left] > arr[right]) {
                arr[temp] = arr[left];
                temp = left;
            } else {
                arr[temp] = arr[right];
                temp = right;
            }
            left = 2 * temp;
            right = left + 1;
        }
        if (left == size && last < arr[left]) {
            arr[temp] = arr[left];
            temp = left;
        }
        arr[temp] = last;
        return item;
    }

7.11 Heap Sort

Finally to implement heap sort, remember our top most element is the higest of the entire tree, right? So we are gonna continuously delete our top-most element and keep it in an array or process. And this should enough to get a sorted array!

Here's the full code,

#include <iostream>
#define MAX 100
using namespace std;

template<typename T> class Heap {
    T arr[MAX];
    int size;
public:
    Heap() {
        size = 0;
        arr[0] = -1;
    }
    void insert(T item) {
        if (size == MAX) {
            cout << "Heap is full\n";
            return;
        }
        size++;
        int temp = size, temp_parent;
        while (temp > 1) {
            temp_parent = temp / 2;
            if (item <= arr[temp_parent]) {
                arr[temp] = item;
                return;
            } 
            arr[temp] = arr[temp_parent];
            temp = temp_parent;
        }
        arr[temp] = item;
    }
    void printAll() {
        for (int i=1; i<=size; i++) {
            cout << arr[i] << " ";
        } cout << endl;
    }
    T deleteMax() {
        T item = arr[1];
        T last = arr[size];
        size--;
        int temp = 1, left = 2, right = 3;
        while (right <= size) {
            if (last >= arr[left] && last >= arr[right]) {
                arr[temp] = last;
                return item;
            }
            if (arr[left] > arr[right]) {
                arr[temp] = arr[left];
                temp = left;
            } else {
                arr[temp] = arr[right];
                temp = right;
            }
            left = 2 * temp;
            right = left + 1;
        }
        if (left == size && last < arr[left]) {
            arr[temp] = arr[left];
            temp = left;
        }
        arr[temp] = last;
        return item;
    }
};

int main() {
    int array [] = {-5, 10, 3, 1, 15, -4, 7, 1};
    Heap<int> heap;
    for (int i=0; i<6; i++) {
        heap.insert(array[i]);
    }
    heap.printAll();

    for (int i=0; i<6; i++) {
        cout << heap.deleteMax() << " ";
    } cout << endl;
    return 0;
}

You can go ahead and collect the sorted one in whatever way you prefer. Good luck!

Minimum Spanning Tree

Minimum Spanning Tree (MST)

A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that includes all the vertices of the graph. Or, to say in Layman’s words, it is a subset of the edges of the graph that forms a tree (acyclic) where every node of the graph is a part of the tree.

The minimum spanning tree has all the properties of a spanning tree, with an added constraint of having the minimum possible weights among all possible spanning trees. Like a spanning tree, there can also be many possible MSTs for a graph.

Above texts are taken from Geek for geeks

Now, let's dive deeper with two different algorithms for getting your MST 🙃.

Kruskals

Disjoint Set

Before kruskals let's consider disjoint sets. More information is available here,

{% embed url="https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/" %} Disjoint sets {% endembed %}

Here, we are separating each set from other by setting a root for a certain part.

#include <bits/stdc++.h>
using namespace std;

int parent[INT_MAX];

void makeSet(int n) {
  for (int i = 0; i <= n; i++)
    parent[i] = i;
}

int find(int n) {
  if (parent[n] == n) return n;
  int result = find(parent[n]);
  parent[n] = result;
  return result;
}

void unite(int i, int j) {
  parent[find(i)] = find(j);
}

int main() {
  makeSet(1e6);
  unite(1024, 2048);
  unite(2048, 4096);
  cout << find(1024) << endl;
  cout << find(2048) << endl;
  cout << find(4096) << endl;
  return 0;
}

Actual kruskal

If you have the disjoint, you can sort your data and use the set to do the MST!

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, pair<int, int>>> edges;
int parent[INT_MAX];

void makeSet(int n) {
  for (int i = 0; i <= n; i++)
    parent[i] = i;
}

int find(int n) {
  if (parent[n] == n) return n;
  int result = find(parent[n]);
  parent[n] = result;
  return result;
}

void unite(int i, int j) {
  parent[find(i)] = find(j);
}

void addEdges(int i, int j, int k) {
  edges.push_back({k, {i, j}});
}

void kruskal() {
  sort(edges.begin(), edges.end());
  int weight = 0;
  for (auto it: edges) {
    int i = it.second.first;
    int j = it.second.second;
    int k = it.first;
    if (find(i) != find(j)) {
      unite(i, j);
      cout << i << " " << j << " " << k << endl;
      weight += k;
    }
  }
  cout << "Weight: " << weight << endl;
}

int main() {
  makeSet(1e6);
  
  addEdges(0, 1, 10);
  addEdges(1, 3, 15);
  addEdges(2, 3, 4);
  addEdges(2, 0, 6);
  addEdges(0, 3, 5);
  kruskal();

  return 0;
}

Prim

Adjacency matrix

For prim, you can do with adjacency list without any priority queue,

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
int V = 5;
void printMST(vector<int> &parent);

int minimum(vector<int> &key, vector<bool> &visited) {
  int minimum = INT_MAX, min_index;
  for (int i=0; i<V; i++) {
    if (visited[i] == false && key[i] < minimum) {
      minimum = key[i];
      min_index = i;
    }
  }
  return min_index;
}

void prim() {
  vector<int> key(V, INT_MAX);
  vector<bool> visited(V, false);
  vector<int> parent(V);

  key[0] = 0;
  parent[0] = -1;

  for (int i=0; i < V-1; i++) {
    int u = minimum(key, visited);
    visited[u] = true;

    for (int v=0; v<V; v++) {
      if (graph[u][v] && visited[v] == false && graph[u][v] < key[v]) {
        parent[v] = u;
        key[v] = graph[u][v];
      }
    }
  }

  printMST(parent);
}

void printMST(vector<int> &parent) {
  cout << "Edge \tWeight\n";
  for (int i=1; i<V; i++) {
    cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << endl;
  }
}



int main() {
  graph = { { 0, 2, 0, 6, 0 },
            { 2, 0, 3, 8, 5 },
            { 0, 3, 0, 0, 7 },
            { 6, 8, 0, 0, 9 },
            { 0, 5, 7, 9, 0 } };
  prim();
}

Priority Queue

But the more efficient way is to go ahead and use priority queue!

#include<bits/stdc++.h>
using namespace std;

// Function to find sum of weights of edges of the Minimum Spanning Tree.
int spanningTree(int V, int E, vector<vector<int>> &edges) {
  
    // Create an adjacency list representation of the graph
    vector<vector<int>> adj[V];
    
    // Fill the adjacency list with edges and their weights
    for (int i = 0; i < E; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int wt = edges[i][2];
        adj[u].push_back({v, wt});
        adj[v].push_back({u, wt});
    }
    
    // Create a priority queue to store edges with their weights
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    
    // Create a visited array to keep track of visited vertices
    vector<bool> visited(V, false);
    
    // Variable to store the result (sum of edge weights)
    int res = 0;
    
    // Start with vertex 0
    pq.push({0, 0});
    
    // Perform Prim's algorithm to find the Minimum Spanning Tree
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        
        int wt = p.first;  // Weight of the edge
        int u = p.second;  // Vertex connected to the edge
        
        if(visited[u] == true){
            continue;  // Skip if the vertex is already visited
        }
        
        res += wt;  // Add the edge weight to the result
        visited[u] = true;  // Mark the vertex as visited
        
        // Explore the adjacent vertices
        for(auto v : adj[u]){
            // v[0] represents the vertex and v[1] represents the edge weight
            if(visited[v[0]] == false){
                pq.push({v[1], v[0]});  // Add the adjacent edge to the priority queue
            }
        }
    }
    
    return res;  // Return the sum of edge weights of the Minimum Spanning Tree
}

int main() {
    vector<vector<int>> graph = {{0, 1, 5},
                                  {1, 2, 3},
                                  {0, 2, 1}};

    cout << spanningTree(3, 3, graph) << endl;

    return 0;
}

Above code is directly taken from Geek for Geeks.

• https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/

Graph

layout: title: visible: true description: visible: true tableOfContents: visible: true outline: visible: true pagination: visible: true

🔸 Warshall's Algorithm

Warshall's Algorithm

To visualize this algorithm use this following site, you can check each steps of warshell algorithm from here,

{% embed url="https://sharafat.is-a.dev/GraphCraft/" %}

here's a test case, just use this input and click on analyze data.

0 0 0 1
1 0 1 1
1 0 0 1
0 0 1 0

Open source project, source code is available on GitHub.

Warshall's Algorithm is used to find the transitive closure of a graph. The transitive closure of a graph is a matrix that shows whether there is a path from vertex i to vertex j. The algorithm is based on the idea that if there is a path from vertex i to vertex j, and there is a path from vertex j to vertex k, then there is a path from vertex i to vertex k.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int mat[n][n];

  // taking input
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> mat[i][j];

      // comment these two following two lines for path matrix
      // (because we need 0 for logical operations -> binary AND, OR)
      if (mat[i][j] == 0)     // if the value is 0,
        mat[i][j] = (int)1e7; // we set it to a higher value
    }
  }

  // warshall's algorithm
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]); // for shortest path
        // mat[i][j] = mat[i][j] || (mat[i][k] && mat[k][j]); // for path matrix
      }
    }
  }

  // printing matrix
  cout << endl;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << mat[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}

Here's a simple test case for this code,

4
0 0 0 1
1 0 1 1
1 0 0 1
0 0 1 0

{% hint style="info" %} Above code can also work to find the path matrix. Follow the comments of the code. {% endhint %}

Linked Representation

We will solely focus on linked representation, where you can imagine in this way,

• we have 2 table
• first table has the nodes data alongside the edge list
• each node has a separate table for it's own edge list (also can be NULL!)

So our skeleton class will be like this,

class Node {
public:
    int data;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
    }
};

We will be using an another class to do operations on it! Here I am using one Node class for both node list and adjacency list, but feel free to divide it into two classes.

class Node2;

class Node1 {
public:
    int data;
    Node1* next_link;
    Node2* adjacent;

    Node1 (int data) {
        this->data = data;
        this->next_link = NULL;
        adjacent = NULL;
    }
};

class Node2 {
public:
    Node2* next_link;
    Node1* destination;

    Node2 (Node1* destination) {
        this->next_link = NULL;
        this->destination = destination;
    }
};

8.3 Finding Node

It's preety straightforward approach. A loop of course!

    Node* find(int data) {
        Node* temp = start;
        while (temp != NULL) {
            if (temp->data == data) return temp;
            temp = temp->next_link;
        }
        return NULL;
    }

{% hint style="info" %} If you are not sure, how to actually place this function, here's a quick peek!

Here, printAll() will help you to debug and print!

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
    }
};

class Graph {
    Node* start; 
public:
    Graph() : start(NULL) {}
    
    Node* find(int data) {
        Node* temp = start;
        while (temp != NULL) {
            if (temp->data == data) return temp;
            temp = temp->next_link;
        }
        return NULL;
    }
    
    void printAll() {
        Node* temp = start;
        while (temp != NULL) {
            cout << temp->data << " -> ";
            Node* temp2 = temp->adjacent;
            while (temp2 != NULL) {
                cout << temp2->destination->data << ", ";
                temp2 = temp2->next_link;
            }
            temp = temp->next_link;
            cout << endl;
        }
    }

    //
    // More functions here
    //
};

int main() {
    Graph g;

    //
    // Write yourself!
    // 

    return 0;
}

{% endhint %}

8.4 Delete Node Only

Just like searching, if we are dealing with only nodes (let's forget about edge table!), check this way,

    void deleteNodeOnly(int data) {
        Node* temp = start;
        if (temp->data == data) {
            start = temp->next_link;
            delete temp;
            return;
        }
        Node* save = temp;
        temp = temp->next_link;
        while (temp != NULL) {
            if (temp->data == data) {
                save->next_link = temp->next_link;
                delete temp;
                return;
            }
            save = temp;
            temp = temp->next_link;
        }
        cout << "Node not found" << endl;
    }

8.5 Finding Edge

For edge, we have to go through each nodes and then access it's edge list. So the journey begins from here,

    Node* findEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return NULL;
        }
        Node* temp = node1->adjacent;
        while (temp != NULL) {
            if (temp->destination == node2) return temp;
            temp = temp->next_link;
        }
        cout << "Edge not found" << endl;
        return NULL;
    }

8.6 Inserting Nodes

While inserting we can simply use our 8.3 function to ensure that function doesn't exist previously. That's it!

void insertNode(int data) {
        Node* new_node = new Node(data);
        if (find(data) != NULL) {
            cout << "Node already exists" << endl;
            return;
        }
        if (start == NULL) {
            start = new_node;
        } else {
            new_node->next_link = start;
            start = new_node;
        }
    }

8.7 Inserting Edges

Inserting edges is gonna be a bit more tricky. We gotta check if our 2 desired nodes are there or not. And then we can think about inserting the data into our edge list.

    void insertEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        
        Node* temp = node1->adjacent;
        while (temp != NULL)
        {
            if (temp->destination == node2) {
                cout << "Edge already exists" << endl;
                return;
            }
            temp = temp->next_link;
        }

        Node* new_node = new Node(node2);
        new_node->next_link = node1->adjacent;
        node1->adjacent = new_node;
    }

8.8 Deleting Edge

While deleting edges, we also have to go through the same trouble as 8.7. Figure our either it is possible or not, then iterate through the edge list of node1.

    void deleteEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        Node* temp = node1->adjacent;
        if (temp->destination == node2) {
            node1->adjacent = temp->next_link;
            delete temp;
            return;
        }
        Node* save = temp;
        temp = temp->next_link;
        while (temp != NULL) {
            if (temp->destination == node2) {
                save->next_link = temp->next_link;
                delete temp;
                return;
            }
            save = temp;
            temp = temp->next_link;
        }
        cout << "Edge not found" << endl;
    }

8.9 Delete Node

In 8.4, we simply deleted a node. But what if we have an edge list for that node?
It'll be a long job. We have to iterate through the edge list of each node and erase the trace of our sweet node that we don't want to eat :), and finally we can leave the rest to 8.4.

    void deleteNode(int data) {
        Node* node = find(data);
        if (node == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        Node* temp = start;
        while (temp != NULL) {
            Node* temp2 = temp->adjacent;
            if (temp2 != NULL) {
                if (temp2->destination == node) {
                    temp->adjacent = temp2->next_link;
                    delete temp2;
                } else if (temp2 != NULL) {
                    Node* save = temp2;
                    temp2 = temp2->next_link;
                    while (temp2 != NULL) {
                        if (temp2->destination == node) {
                            save->next_link = temp2->next_link;
                            delete temp2;
                            break;
                        }
                        save = temp2;
                        temp2 = temp2->next_link;
                    }
                }
            }
            temp = temp->next_link;
        }
        deleteNodeOnly(data);
    }

Wrapping up!

So by combining all those functions, we can write something like this,

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
    }
};

class Graph {
    Node* start; 
public:
    Graph() : start(NULL) {}
    
    Node* find(int data) {
        Node* temp = start;
        while (temp != NULL) {
            if (temp->data == data) return temp;
            temp = temp->next_link;
        }
        return NULL;
    }

    Node* findEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return NULL;
        }
        Node* temp = node1->adjacent;
        while (temp != NULL) {
            if (temp->destination == node2) return temp;
            temp = temp->next_link;
        }
        cout << "Edge not found" << endl;
        return NULL;
    }

    void insertNode(int data) {
        Node* new_node = new Node(data);
        if (find(data) != NULL) {
            cout << "Node already exists" << endl;
            return;
        }
        if (start == NULL) {
            start = new_node;
        } else {
            new_node->next_link = start;
            start = new_node;
        }
    }

    void insertEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        
        Node* temp = node1->adjacent;
        while (temp != NULL)
        {
            if (temp->destination == node2) {
                cout << "Edge already exists" << endl;
                return;
            }
            temp = temp->next_link;
        }

        Node* new_node = new Node(node2);
        new_node->next_link = node1->adjacent;
        node1->adjacent = new_node;
    }

    void deleteNodeOnly(int data) {
        Node* temp = start;
        if (temp->data == data) {
            start = temp->next_link;
            delete temp;
            return;
        }
        Node* save = temp;
        temp = temp->next_link;
        while (temp != NULL) {
            if (temp->data == data) {
                save->next_link = temp->next_link;
                delete temp;
                return;
            }
            save = temp;
            temp = temp->next_link;
        }
        cout << "Node not found" << endl;
    }

    void deleteNode(int data) {
        Node* node = find(data);
        if (node == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        Node* temp = start;
        while (temp != NULL) {
            Node* temp2 = temp->adjacent;
            if (temp2 != NULL) {
                if (temp2->destination == node) {
                    temp->adjacent = temp2->next_link;
                    delete temp2;
                } else if (temp2 != NULL) {
                    Node* save = temp2;
                    temp2 = temp2->next_link;
                    while (temp2 != NULL) {
                        if (temp2->destination == node) {
                            save->next_link = temp2->next_link;
                            delete temp2;
                            break;
                        }
                        save = temp2;
                        temp2 = temp2->next_link;
                    }
                }
            }
            temp = temp->next_link;
        }
        deleteNodeOnly(data);
    }

    void deleteEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        Node* temp = node1->adjacent;
        if (temp->destination == node2) {
            node1->adjacent = temp->next_link;
            delete temp;
            return;
        }
        Node* save = temp;
        temp = temp->next_link;
        while (temp != NULL) {
            if (temp->destination == node2) {
                save->next_link = temp->next_link;
                delete temp;
                return;
            }
            save = temp;
            temp = temp->next_link;
        }
        cout << "Edge not found" << endl;
    }

    void printAll() {
        Node* temp = start;
        while (temp != NULL) {
            cout << temp->data << " -> ";
            Node* temp2 = temp->adjacent;
            while (temp2 != NULL) {
                cout << temp2->destination->data << ", ";
                temp2 = temp2->next_link;
            }
            temp = temp->next_link;
            cout << endl;
        }
    }
};

int main() {
    Graph g;
    g.insertNode(2);
    g.insertNode(1);
    g.insertNode(3);

    g.insertEdge(1, 2);
    g.insertEdge(1, 2); // Edge already exists
    g.insertEdge(2, 3);
    g.insertEdge(3, 2);
    g.insertEdge(2, 1);

    g.deleteNode(1);
    g.deleteEdge(2, 3);

    g.printAll();
    
    // Node* n = g.find(2);
    // cout << "Found: " << n->data << endl;

    // Node* e = g.findEdge(2, 1);
    // cout << e->destination->data << endl;

    return 0;
}

Feel free to go through the commented lines, tweaking around!

Here print function is for your debugging friend!

And you can implement all these with STL library as well. Here's a sample,

#include <bits/stdc++.h>
using namespace std;

map<string, vector<string>> graph;

void addNode(string v) {
    if (graph[v].empty()) graph[v] = {};
}

void addEdge(string u, string v) {
    graph[u].push_back(v);
    if (graph[v].empty()) graph[v] = {};
}

void printAll() {
    for (auto it:graph) {
        cout << it.first << " -> ";
        for (auto it2: it.second) {
            cout <<it2 << " ";
        }
        cout << endl;
    }
}

void searchEdge(string u, string v) {
    for (auto it:graph) {
        if (it.first == u) {
            for (auto it2: it.second) {
                if (it2 == v) {
                    cout << it.first << " -> " << it2 << " ";
                }
            }
            cout << endl;
        }
    }
    cout << "Edge not found";
}

int main() {
    addEdge("A", "D");
    addEdge("A", "C");
    addEdge("A", "B");

    addEdge("B", "C");

    addEdge("D", "C");
    addEdge("D", "E");

    addEdge("E", "C");

    cout << "\nBefore: \n";
    printAll();

    cout << "\nAfter new node: \n";
    addNode("F");
    printAll();

    cout << "\nAfter new edge: \n";
    addEdge("F", "E");
    printAll();

    cout << "\nSearching an edge: \n";
    searchEdge("D", "C");
}

Traversing - BFS, DFS & More

Breadth-First Search

In the previous section, remember printAll() function?

We will be traversing just like that but a different approach. In breadth first, imagine you are a dragon and you are breathing fire in a wood, LOL. So which trees are gonna burn first?

Ovbiously the closer ones, right?

In the breadth first, we are gonna use queue to make a structure from a specific node, add it's adjacent nodes and process the front element one by one. Preety interesting right?

Instead of writing a brand new code, let' tweak our sweet little code from previous one, we can actually change the core structure and add a new variable named status, which will indicate we have visited that or not. In this way,

class Node {
public:
    int data;
    bool status;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
        this->status = false;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
        this->status = false;
    }
};

Here true means we have visited the node. Let's talk about it (code) after DFS.

Depth-First Search

In DFS, instead of queue, we are going to use stack. That's the difference. I think you can figure out the rest.

And if I complete the code with BFS, our whole code will be,

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

class Node {
public:
    int data;
    bool status;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
        this->status = false;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
        this->status = false;
    }
};

class Graph {
    Node* start; 
public:
    Graph() : start(NULL) {}
    
    Node* find(int data) {
        Node* temp = start;
        while (temp != NULL) {
            if (temp->data == data) return temp;
            temp = temp->next_link;
        }
        return NULL;
    }

    void insertNode(int data) {
        Node* new_node = new Node(data);
        if (find(data) != NULL) {
            cout << "Node already exists" << endl;
            return;
        }
        if (start == NULL) {
            start = new_node;
        } else {
            new_node->next_link = start;
            start = new_node;
        }
    }

    void insertEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        
        Node* temp = node1->adjacent;
        while (temp != NULL)
        {
            if (temp->destination == node2) {
                cout << "Edge already exists" << endl;
                return;
            }
            temp = temp->next_link;
        }

        Node* new_node = new Node(node2);
        new_node->next_link = node1->adjacent;
        node1->adjacent = new_node;
    }

    void printAll() {
        Node* temp = start;
        while (temp != NULL) {
            cout << temp->data << " -> ";
            Node* temp2 = temp->adjacent;
            while (temp2 != NULL) {
                cout << temp2->destination->data << ", ";
                temp2 = temp2->next_link;
            }
            temp = temp->next_link;
            cout << endl;
        }
    }

    void breadthFirst() {
        queue<Node*> q;
        q.push(start);
        start->status = true;

        while (!q.empty()) {
            Node* temp = q.front();
            cout << temp->data << " ";
            q.pop();
            temp = temp->adjacent;
            while (temp != NULL) {
                if (!temp->destination->status) {
                    q.push(temp->destination);
                    temp->destination->status = true;
                }
                temp = temp->next_link;
            }
        }
        cout << endl;
    }
    
    void depthFirst() {
        stack<Node*> s;
        s.push(start);
        start->status = true;

        while (!s.empty()) {
            Node* temp = s.top();
            cout << temp->data << " ";
            s.pop();
            temp = temp->adjacent;
            while (temp != NULL) {
                if (!temp->destination->status) {
                    s.push(temp->destination);
                    temp->destination->status = true;
                }
                temp = temp->next_link;
            }
        }
        cout << endl;
    }
};

int main() {
    Graph g;
    g.insertNode(1);
    g.insertNode(2);
    g.insertNode(3);

    g.insertEdge(1, 2);
    g.insertEdge(2, 3);
    g.insertEdge(3, 2);
    g.insertEdge(2, 1);

    g.printAll();

    g.breadthFirst();
    // g.depthFirst();

    return 0;
}

{% hint style="danger" %} In the above code, we are directly tweaking the memory of main class Node, and so our visited value will be changed after one BFS or DFS. So we can't use both BFS and DFS at the same time. So what to do? {% endhint %}

BFS + DFS

In this case, (above warning) we can actually go ahead and use separate map (STL lib) for both BFS and DFS. Let's check the code,

#include <iostream>
#include <queue>
#include <stack>
#include <map>

using namespace std;

class Node {
public:
    int data;
    Node* next_link; 
    Node* adjacent;
    Node* destination;

    Node (int data) {
        this->data = data;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = NULL;
    }
    Node (Node* destination) {
        this->data = 0;
        this->next_link = NULL;
        this->adjacent = NULL;
        this->destination = destination;
    }
};

class Graph {
    Node* start; 
public:
    Graph() : start(NULL) {}
    
    Node* find(int data) {
        Node* temp = start;
        while (temp != NULL) {
            if (temp->data == data) return temp;
            temp = temp->next_link;
        }
        return NULL;
    }

    void insertNode(int data) {
        Node* new_node = new Node(data);
        if (find(data) != NULL) {
            cout << "Node already exists" << endl;
            return;
        }
        if (start == NULL) {
            start = new_node;
        } else {
            new_node->next_link = start;
            start = new_node;
        }
    }

    void insertEdge(int data1, int data2) {
        Node* node1 = find(data1);
        Node* node2 = find(data2);
        if (node1 == NULL || node2 == NULL) {
            cout << "Node not found" << endl;
            return;
        }
        
        Node* temp = node1->adjacent;
        while (temp != NULL)
        {
            if (temp->destination == node2) {
                cout << "Edge already exists" << endl;
                return;
            }
            temp = temp->next_link;
        }

        Node* new_node = new Node(node2);
        new_node->next_link = node1->adjacent;
        node1->adjacent = new_node;
    }

    void printAll() {
        Node* temp = start;
        while (temp != NULL) {
            cout << temp->data << " -> ";
            Node* temp2 = temp->adjacent;
            while (temp2 != NULL) {
                cout << temp2->destination->data << ", ";
                temp2 = temp2->next_link;
            }
            temp = temp->next_link;
            cout << endl;
        }
    }

    void breadthFirst() {
        queue<Node*> q;
        q.push(start);
        map<Node*, bool> visited;
        visited[start] = true;

        while (!q.empty()) {
            Node* temp = q.front();
            cout << temp->data << " ";
            q.pop();
            temp = temp->adjacent;
            while (temp != NULL) {
                if (!visited[temp->destination]) {
                    q.push(temp->destination);
                    visited[temp->destination] = true;
                }
                temp = temp->next_link;
            }
        }
        cout << endl;
    }
    
    void depthFirst() {
        stack<Node*> s;
        s.push(start);
        map<Node*, bool> visited;
        visited[start] = true;

        while (!s.empty()) {
            Node* temp = s.top();
            cout << temp->data << " ";
            s.pop();
            temp = temp->adjacent;
            while (temp != NULL) {
                if (!visited[temp->destination]) {
                    s.push(temp->destination);
                    visited[temp->destination] = true;
                }
                temp = temp->next_link;
            }
        }
        cout << endl;
    }
};

int main() {
    Graph g;
    g.insertNode(1);
    g.insertNode(2);
    g.insertNode(3);

    g.insertEdge(1, 2);
    g.insertEdge(2, 3);
    g.insertEdge(3, 2);
    g.insertEdge(2, 1);

    g.printAll();

    g.breadthFirst();
    g.depthFirst();

    return 0;
}

And finally, with the support of STL, we can even write more beautiful codes like this, without worrying about implementing two tables separately. In the above cases, we started from the start point. But we can actually start the DFS and BFS algorithm from any point, and this is the most interesting thing about these two brothers.

#include<bits/stdc++.h>

using namespace std;

template<typename T> class Graph {
    map<T, list<T>> adjList;
public:
    Graph() {}
    void addEdge(T u, T v, bool bidir = false) {
        adjList[u].push_back(v);
        if(bidir) adjList[v].push_back(u);
    }

    void print() {
        for(auto i : adjList) {
            cout << i.first << " -> ";
            for(auto entry : i.second) {
                cout << entry << ", ";
            }
            cout << endl;
        }
    }

    void bfs(T src) {
        queue<T> q;
        map<T, bool> visited;
        q.push(src);
        visited[src] = true;
        while(!q.empty()) {
            T node = q.front();
            cout << node << " ";
            q.pop();
            for(auto neighbour : adjList[node]) {
                if(!visited[neighbour]) {
                    q.push(neighbour);
                    visited[neighbour] = true;
                }
            }
        }
    }

    void dfs(T src) {
        stack<T> s;
        map<T, bool> visited;
        s.push(src);
        visited[src] = true;
        while(!s.empty()) {
            T node = s.top();
            cout << node << " ";
            s.pop();
            for(auto neighbour : adjList[node]) {
                if(!visited[neighbour]) {
                    s.push(neighbour);
                    visited[neighbour] = true;
                }
            }
        }
    }
};

int main() {
    Graph<char> g;
    g.addEdge('A', 'F');
    g.addEdge('A', 'C');
    g.addEdge('A', 'B');
    g.addEdge('B', 'G');
    g.addEdge('B', 'C');
    g.addEdge('C', 'F');
    g.addEdge('D', 'C');
    g.addEdge('E', 'D');
    g.addEdge('E', 'C');
    g.addEdge('E', 'J');
    g.addEdge('F', 'D');
    g.addEdge('G', 'C');
    g.addEdge('G', 'E');
    g.addEdge('J', 'D');
    g.addEdge('J', 'K');
    g.addEdge('K', 'E');
    g.addEdge('K', 'G');

    g.print();
    g.bfs('A');

    cout << endl;
    g.dfs('J');

    return 0;
}

Topological Sorting

In this case we will work on a directed graph without cycles. In this scenario, we will print the value which comes first before an another node while going through the order. Imagine in this way, nodes with 0 in-order nodes will come at the very last position, because we can't go from them to anywhere else!

We will basically focus on this particular thing (inorder nodes) and store the data in a queue. And optionally we can reverse the print order for natural view!

#include<bits/stdc++.h>

using namespace std;

template<typename T> class Graph {
    map<T, list<T>> adjList;
public:
    Graph() {}
    void addEdge(T u, T v, bool bidir = false) {
        adjList[u].push_back(v);
        if (adjList.find(v) == adjList.end()) 
            adjList[v] = list<T>();
        if(bidir) adjList[v].push_back(u);
    }

    void print() {
        for(auto i : adjList) {
            cout << i.first << " -> ";
            for(auto entry : i.second) {
                cout << entry << ", ";
            }
            cout << endl;
        }
    }

    void topologicalSort() {
        map<T, int> indegree;
        queue<T> q;
        stack<T> s_q_reversed;
        for(auto i : adjList) {
            indegree[i.first] = i.second.size();
            if (indegree[i.first] == 0) 
                q.push(i.first);
        }
        while(!q.empty()) {
            T node = q.front();
            s_q_reversed.push(node);
            // cout << node << " ";
            q.pop();
            for (auto i: adjList) {
                for(auto neighbour : i.second) {
                    if(neighbour == node) {
                        indegree[i.first]--;
                        if(indegree[i.first] == 0) 
                            q.push(i.first);
                        continue;
                    }
                }
            }
        }
        // cout << endl;
        while(!s_q_reversed.empty()) {
            cout << s_q_reversed.top() << " ";
            s_q_reversed.pop();
        }
    }
};

int main() {
    Graph<char> g;
    g.addEdge('A', 'C');
    g.addEdge('B', 'D');
    g.addEdge('B', 'F');
    g.addEdge('D', 'C');
    g.addEdge('E', 'C');
    g.addEdge('G', 'A');
    g.addEdge('G', 'F');

    g.print();

    cout << endl;
    g.topologicalSort();


    return 0;
}

{% hint style="info" %} Remove the commented lines, to understand the stack part! I just reversed the output, that's all. {% endhint %}

Here's a bonus algorithm, that may come handy. It will display the distance between a node to the rest! Feel free to explore further.

Single Source Shortest Path (SSSP)

    void sssp(T src) {
        queue<T> q;
        map<T, int> dist;
        for(auto i : adjList) {
            dist[i.first] = INT_MAX;
        }
        q.push(src);
        dist[src] = 0;
        while(!q.empty()) {
            T node = q.front();
            q.pop();
            for(auto neighbour : adjList[node]) {
                if(dist[neighbour] == INT_MAX) {
                    q.push(neighbour);
                    dist[neighbour] = dist[node] + 1;
                }
            }
        }
        for(auto i : adjList) {
            T node = i.first;
            cout << "Distance of " << node << " from " << src << " is " << dist[node] << endl;
        }
    }

Dijkstra

Prerequisites

Some basic knowledge about priority queue is required for this implementation. Learn more here,

• https://www.geeksforgeeks.org/introduction-to-dijkstras-shortest-path-algorithm/
• https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/

Sample code

Here's a code with a bit of STL,

#include <bits/stdc++.h>

using namespace std;

int V = 7;
vector<vector<pair<int, int>>> graph(V);

void addEdge(int u, int v, int w) {
  graph[u].push_back({v, w});
  graph[v].push_back({u, w});
}

void dijkstra(int src) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.push({0, src});

  vector<int> distance(V, INT16_MAX);
  distance[src] = 0;

  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();

    int u = p.second;
    int w = p.first;

    for (auto i: graph[u]) {
      int v = i.first;
      int wt = i.second;
      if (distance[u] + wt < distance[v]) {
        distance[v] = distance[u] + wt;
        pq.push({distance[v], v});
      }
    }
  }

  for (int i = 0; i < V; i++) {
    cout << "Distance from " << src << " to " << i << " is " << distance[i] << endl;
  }
}

int main() {
  addEdge(0, 1, 2);
  addEdge(0, 2, 6);
  addEdge(1, 3, 5);
  addEdge(2, 3, 8);
  addEdge(3, 4, 10);
  addEdge(3, 5, 15);
  addEdge(4, 6, 2);
  addEdge(5, 6, 6);

  dijkstra(0);
  return 0;
}

Bellman-Ford

You can go ahead and learn from here,

{% embed url="https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/" %}

Sample

Here's a sample code,

#include <bits/stdc++.h>
using namespace std;

map<int, vector<pair<int, int>>> graph;

void insertIntoGraph(int u, int v, int w) {
    graph[u].push_back({v, w});
    if (graph[v].empty()) graph[v] = {};
}

void bellmanFord(int src) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    for (int i=0; i<V; i++) {
        for (auto u: graph) {
            for (auto v: u.second) {
                int from = u.first;
                int to = v.first;
                int weight = v.second;
                if (dist[from] != INT_MAX && dist[from] + weight < dist[to]) {
                    dist[to] = dist[from] + weight;
                }
            }
        }
    }

    for (auto u: graph) {
        for (auto v: u.second) {
            int from = u.first;
            int to = v.first;
            int weight = v.second;
            if (dist[from] != INT_MAX && dist[from] + weight < dist[to]) {
                cout << "Negative cycle found" << endl;
                return;
            }
        }
    }

    cout << "Vertex Distance from Source" << endl;
    for (int i=0; i<V; i++) {
        cout << i << "    " << dist[i] << endl;
    }
}

int main() {
    insertIntoGraph(0, 1, -1);
    insertIntoGraph(0, 2, 4);
    insertIntoGraph(1, 2, 3);
    insertIntoGraph(1, 3, 2);
    insertIntoGraph(1, 4, 2);
    insertIntoGraph(3, 2, 5);
    insertIntoGraph(3, 1, 1);
    insertIntoGraph(4, 3, -3);

    bellmanFord(0);
}

Sorting & Searching

Insertion Sort

Intro

Suppose you are supposed to sort some sorts. Obviously you will go through all of 'em, right?

Well, while iterating, you will turn backwards to find the right place for each book, think in this way.

Code

#include <iostream>

using namespace std;

void insertionSort(int* arr, int size) {
    for (int i = 1; i < size; i++) {
        int x = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > x) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = x;
    }
}

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

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    insertionSort(arr, sizeof(arr)/sizeof(arr[0]));
    print(arr, sizeof(arr)/sizeof(arr[0]));
}

Selection Sort

Intro

In selection, you will also iterate. But the difference is, you will hold each value and compare the rest alongside it! If you find a smaller value, you can swap.

Code

#include <iostream>

using namespace std;

void selectionSort(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[i]) {
                swap(arr[j], arr[i]);
            }
        }
    }
}

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

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    selectionSort(arr, sizeof(arr)/sizeof(arr[0]));
    print(arr, sizeof(arr)/sizeof(arr[0]));
}

Bubble Sort

Intro

In bubble, you will also compare two value per each iteration. But the difference from selection sort is that, you don't need to actually hold a value. Just go forward and scan a value with its next adjacent one!

Code

#include <iostream>

using namespace std;

void bubbleSort(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

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

int main() {
    int arr[] = {5, 2, 4, 6, -1, 3};
    bubbleSort(arr, sizeof(arr)/sizeof(arr[0]));
    print(arr, sizeof(arr)/sizeof(arr[0]));
}

Merge Sort

Intro

In merge sort, we are dividing our whole array by half as long as possible and then combining each pieces together.

It's kinda similar to quick sort, which we wrote in stack section, I guess!

Code

#include <iostream>

using namespace std;

void mergeSortProcess(int* arr, int low, int mid, int high) {
    int i, j, k;
    int temp[high - low + 1];
    for (i = low, j = mid + 1, k = 0; i <= mid && j <= high; k++) {
        if (arr[i] < arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
    }
    while (i <= mid) {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= high) {
        temp[k] = arr[j];
        j++;
        k++;
    }
    for (i = low, k = 0; i <= high; i++, k++) {
        arr[i] = temp[k];
    }
}

void mergeSort(int* arr, int low, int high) {
    if (low == high) return;
    int mid = (low + high) / 2;
    
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    mergeSortProcess(arr, low, mid, high);
}

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

int main() {
    int arr[] = {5, 2, 4, 6, -1, 3};
    mergeSort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
    print(arr, sizeof(arr)/sizeof(arr[0]));
}

Intro

Intro to math in competitive programming.

Number Theory

Prime Numbers

Two method to determine prime numbers. One is to check if a number is prime, and the other is to generate a list of prime numbers.

#include <bits/stdc++.h>
using namespace std;

bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n % 2 == 0) return false;

    int limit = sqrt(n+1);
    for (int i=3; i < limit; i += 2) {
        if (n%i==0) return false;
    }
    return true;
}

vector<bool> prime(1e5, true); // 1 = prime
void sieve(long long n) { // Sieve of Eratoshtehnes
    prime[1] = false;
    for (long long i = 2 ; i < n; i += 2) prime[i] = false;
    
    int limit = sqrt(n+1);
    for (int i=2; i < limit; i++) {
        if (prime[i]) {
            for (int j=i*i; j < limit;j += i) {
                prime[j] = false;
            }
        }
    }
}

int main() {
    sieve(1e4);
    
    cout << isPrime(35);
    cout << prime[35];
}

GCD and LCM

Euclid's method should do the trick efficiently,

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    if (a % b == 0) return b;
    return gcd(b, a%b);
}

int lcm(int a, int b) {
    return (int)((a * b) / gcd(a, b));
}

int main() {
    cout << lcm(2, 6);
}

Modular Arithmetic

Combinatorics

Probability

Big Integer

A big integer is an integer with arbitrary precision. It can store numbers with a large number of digits. It is useful when we need to store large numbers that cannot be stored in the standard data types like int or long long.

A problem to add two numbers,

#include <bits/stdc++.h>
using namespace std;

// Simple template by sharafat
typedef long long ll;
typedef vector<ll> vl;

#define endl '\n'

void print(vl a)
{
    for (auto i : a)
    {
        cout << i ;
    }
    cout << endl;
}

void add(vl a, vl b)
{
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    vl max_arr;
    if (a.size() > b.size()) max_arr = a; else max_arr = b;

    ll len = min(a.size(), b.size());
    ll max_len = max(a.size(), b.size());
    vl s;
    ll c = 0;
    for (ll i = 0; i < len; i++)
    {
        ll t = a[i]+b[i]+c;
        s.emplace_back(t % 10);
        c = t / 10;
    }
    for (ll i = len; i < max_len; i++)
    {
        ll t = max_arr[i]+c;
        s.emplace_back(t % 10);
        c = t / 10;
    }
    if (c) s.emplace_back(c);
    reverse(s.begin(), s.end());
    print(s);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Code starts here

    ll t;
    cin >> t;
    while (t--)
    {
        string a, b;
        cin >> a >> b;

        vl s, d;

        for (int i = 0; i < a.size(); i++)
        {
            s.emplace_back(a[i] - '0');
            // s[i] = a[i] - '0';
        }
        for (int i = 0; i < b.size(); i++)
        {
            d.emplace_back(b[i] - '0');
            // d[i] = b[i] - '0';
        }

        add(s, d);
    }

    // Code ends here
    return 0;
}