Heap Sort Algorithm in Python.

Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure to sort elements in an array. In this article, we will discuss the algorithm in detail with Python code implementation.

Heap Sort Algorithm Explanation.

Heap Sort is a sorting algorithm that utilizes the principles of a Binary Heap data structure to sort elements within an array. The process begins by constructing a Max Heap or Min Heap from the unsorted array, ensuring that the root node holds the maximum (or minimum) value compared to its children in the Max Heap (or vice versa in a Min Heap). 

In the next step, the algorithm performs heapify operations, involving reorganization of the heap after each element removal to maintain heap property. During the sorting phase, elements are sequentially removed from the heap, starting from the root node. After each removal, the remaining elements undergo heapify operations to preserve the heap structure. The removed elements are stored in the array, ultimately resulting in a sorted arrangement.

Heap Sort Algorithm Steps:

• Convert the unsorted array into a Max Heap or Min Heap.
• Perform heapify operations to maintain the heap property after each element removal.
• Sequentially remove elements from the heap, starting from the root node. After each removal, reorganize the heap to maintain the heap property.
• Store the removed elements in an array to obtain the sorted order. 

Python Program for Heap Sort Algorithm.

Below is the code implementation of the Heap Sort Algorithm using Python language.

Python Code:

# Python Code implementatin for Heap Sort Algorithm
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # Check if left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is greater than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root with last element
        heapify(arr, i, 0)  # Heapify root element

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr) 

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: The time complexity of Heap Sort in all cases is O(n log n). Building the heap takes O(n) time, and for each element, heapify takes O(log n) time. As there are n elements, the total time complexity is O(n log n).

Space Complexity: Heap Sort has a space complexity of O(1) as it performs sorting in place, utilizing the input array without requiring additional space.

Heap Sort Using Python Built-in Function.

In Python, the heapq module provides a heap sort functionality through the heapify() and heappop() functions. These functions enable Heap Sort by creating a min-heap and extracting elements one by one, resulting in a sorted list.

Main functions of heapq module:

• heapify(iterable): Converts a given iterable (such as a list) into a heap in place. The function rearranges the elements so that they satisfy the heap property.

• heappush(heap, item): Adds an element item to the heap while maintaining the heap property.

• heappop(heap): Removes and returns the smallest element (root) from the heap while maintaining the heap property.

Python Code:

# Heap Sort Algorithm using heapq module
import heapq

def heap_sort(arr):
    # Convert the input list into a min-heap
    heapq.heapify(arr)  

    sorted_list = []
    while arr:
    # Extract elements one by one 
       sorted_list.append(heapq.heappop(arr))  
    return sorted_list

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_array = heap_sort(arr)
print("Sorted array:", sorted_array)

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: O(n log n)

Space Complexity: O(1)

Merge Sort Algorithm in Python.

MergeSort is a popular sorting algorithm known for its efficiency and stability. It operates by dividing the unsorted list into smaller sub-lists and then merging them back together to produce a sorted list. It is very similar to the Quick Sort Algorithm. In this article, we are going to understand the Merge Sort algorithm in detail with Python code implementation.

Merge Sort Algorithm Explanation.

The merge sort algorithm is based on the divide and conquer approach in which we continuously divide the given list into smaller units to create sorted sub-lists and then merge them back to create a final sorted list.  

 

Algorithm Steps:

• Start with an unsorted list/array.
• Divide the list into smaller sub-lists recursively until each sub-list contains only one element. This process is achieved recursively.
• Combine the smaller sorted sub-lists back together by comparing and merging adjacent pairs of sub-lists.
• Merge these pairs in a sorted manner to create larger sorted sub-lists. 

Python Program for Merge Sort Algorithm.

Below is the code implementation of Merge Sort Algorithm in Python:

# Python code implementation of Merge Sort
def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the list
        mid = len(arr) // 2 
 
        # Divide the list into two halves
        left_half = arr[:mid]  
        right_half = arr[mid:]

        # Recursive call to sort the left half
        merge_sort(left_half)  
        
        # Recursive call to sort the right half
        merge_sort(right_half)  

        # Merge the sorted halves
        i = j = k = 0  # Initialize indices for merging
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for remaining elements in left and right halves

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [64, 34, 25, 12, 20, 10, 90]
merge_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [10, 12, 20, 25, 34, 64, 90]

Time Complexity: Merge Sort demonstrates a time complexity of O(n log n) across all cases. This efficiency makes Marge Sort highly desirable for sorting larger datasets. 

Space Complexity: O(n). Merge Sort's space complexity primarily involves auxiliary space for temporary arrays during the merging phase.

Quick Sort Algorithm in Python.

Quick Sort is a highly efficient sorting algorithm that arranges elements in ascending or descending order. It operates based on the divide and conquer strategy, dividing the array into smaller segments, and then sorting those segments recursively to achieve the final sorted array. It is very much similar to the Merge Sort Algorithm.

Quick Sort Algorithm Explanation.

In Quick Sort, we have to choose a pivot element, a chosen value from the array around which partitioning occurs. This pivotal choice significantly influences the algorithm's efficiency. Our goal is to select a pivot that helps create balanced partitions, ensuring the array gets divided into approximately equal halves during each recursive call.

Select the First and Last Element as Pivot:

• Selecting the first and last element as the pivot is simple and efficient in implementation. However, this approach might lead to unbalanced partitions if the array is already sorted or nearly sorted.

Select the Last Element as Pivot:

• Choosing the middle element of the array as the pivot. This method often provides a better pivot choice, especially for larger datasets.

Quick Sort Algorithm Steps:

• Step 1: Select an element from the array as the pivot (commonly the last element).

• Step 2: Rearrange the elements in the array so that elements smaller than the pivot are placed before it, while elements larger than the pivot are placed after it. 

• Step 3: After Step 2,  the pivot assumes its correct position in the sorted array.

• Step 4: Apply Quick Sort recursively to the subarrays formed by partitioning until the entire array is sorted.

Python Program for Quick Sort Algorithm.

Below is the code implementation of the Quick Sort Algorithm using Python programming.

# Python code implementation of Quick Sort Algorithm
def partition(arr, low, high):
    # Choose the last element as the pivot    
    pivot = arr[high]  
    i = low - 1  # Index of smaller element
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # Partitioning index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time Complexity: In the best and average cases, where the pivot consistently divides the array into roughly equal halves, Quick Sort achieves a time complexity of O(n log n). However, in the worst-case scenario, where the pivot selection leads to highly unbalanced partitions, Quick Sort's time complexity degrades to O(n^2).

Space Complexity: In the average case, the maximum space required for the recursive call stack is O(log n), as the array gets divided into smaller segments. 

Selection Sort Algorithm in Python.

Sorting algorithms offer a unique approach to arranging data efficiently in ascending or descending order. Among these techniques stands Selection Sort, a straightforward yet essential algorithm that systematically organizes elements by repeatedly selecting the minimum value and placing it at the beginning. In this article, we will explore the Selection Sort Algorithm in detail with Python implementation, and understand its strengths and limitations in sorting data.

Python Program for Selection Sort Algorithm.

Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. It divides the array into two parts: the sorted part and the unsorted part. The algorithm finds the smallest element from the unsorted part and swaps it with the first unsorted element, incrementing the sorted part’s size by one.

Algorithm Steps:

• Start from the beginning of the list.
• Find the minimum element in the unsorted part.
• Swap it with the first unsorted element.
• Increment the sorted part’s size by one.
• Repeat steps 2-4 until the entire list is sorted.

Python Code Implementation for Selection Sort.

Here is an example of Selection Sort in Python:

# Python code for Selection Sort Algorithm
def selection_sort(arr):
    n = len(arr)
    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time and Space Complexity.

• Time Complexity: O(n^2) as it involves nested loops iterating through the array, making it inefficient for larger datasets.

• Space Complexity: O(1) as Selection Sort operates in place, requiring only a constant amount of extra space for variables. 

Bubble Sort Algorithm in Python.

Sorting algorithms play an important role in organizing data efficiently. One such algorithm is the Bubble Sort Algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In this article, we will understand the algorithm in detail with implementation in Python code.

Bubble Sort Algorithm for Python.

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It proceeds until no more swaps are needed, indicating that the list is sorted.

Algorithm Steps:

• Start from the beginning of the list.
• Compare adjacent elements.
• Swap them if they are in the wrong order.
• Repeat steps 2 and 3 until the entire list is sorted.

Python Code Implementation of Bubble Sort.

Here is an example of Bubble Sort in Python:

# Python code for Bubble Sort Algorithm
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):

        # Flag to optimize when the list is already sorted
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no two elements were swapped, the list is sorted
        if not swapped:
            break

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time and Space Complexity.

• Time Complexity: O(n^2) in the worst-case scenario, as it involves nested loops iterating through the array. Best-case scenario (when the list is already sorted) can be O(n).

• Space Complexity: O(1) as Bubble Sort operates in place, requiring only a constant amount of extra space for variables. 

Explanation of Bubble Sort With Example.

Let's consider the example [64, 34, 25, 12, 22, 11, 90] and step through the Bubble Sort process:

Step 1: Comparing adjacent elements and swapping them if necessary.

• [34, 25, 12, 22, 11, 64, 90]
• [25, 12, 22, 11, 34, 64, 90]
• [12, 22, 11, 25, 34, 64, 90]
• [12, 11, 22, 25, 34, 64, 90]
• [11, 12, 22, 25, 34, 64, 90]

Step 2: Continuing comparisons and swaps.

• [11, 12, 22, 25, 34, 64, 90]

Step 3: The array is sorted in ascending order.

Bubble Sort is generally inefficient for larger datasets due to its quadratic time complexity. However, it can be suitable for small datasets or nearly sorted arrays. Other sorting algorithms like Merge Sort or Quick Sort offer better performance for larger datasets.

Insertion Sort Algorithm in Python.

Insertion Sort is a simple sorting algorithm that is used to sort the array/list elements in ascending or descending order. In this article, we will discuss the algorithm in detail with an example and Python code implementation.

Insertion Sort Algorithm.

Insertion Sort is a simple sorting algorithm that builds the final sorted array gradually by iterating through the elements. It divides the array into two parts: the sorted part and the unsorted part. It repeatedly takes an element from the unsorted part and places it in its correct position within the sorted part by shifting larger elements to the right. This process continues until all elements are in their correct positions, resulting in a fully sorted array. 

The insertion sort algorithm starts with the assumption that the first element is already sorted and then compares subsequent elements, inserting them into the correct position in the sorted part while shifting larger elements as needed. 

Algorithm steps:

• Step 1: Assume the first element is already sorted and consider the second element.

• Step 2: For each element in the unsorted part, compare it with elements in the sorted part.

• Step 3: If the element is smaller, shift larger elements in the sorted part to the right and insert the element at the correct position.

• Step 4: Continue the process until all elements are sorted.

Example:

Let's consider an array [5, 2, 4, 6, 1, 3] and apply Insertion Sort step by step:

1. Below is the condition of the Initial Array.

2. Iteration 1: The first element (5) is already sorted. Consider the second element (2) and compare it with the first. Since 2 < 5, swap them.

3. Iteration 2: Consider the third element (4). Compare it with elements in the sorted part (2, 5). Shift larger elements (5) to the right and insert 4 at the correct position.

4. Iteration 3: Consider the fourth element (6). It is larger than the sorted elements, so leave it as it is.

5. Iteration 4: Consider the fifth element (1). Compare it with elements in the sorted part. Shift larger elements (2, 4, 5, 6) to the right and insert 1 at the correct position.

6. Iteration 5: Consider the sixth element (3). Compare it with elements in the sorted part. Shift larger elements (4, 5, 6) to the right and insert 3 at the correct position.

7. Our Final Sorted Array is [1, 2, 3, 4, 5, 6].

Python Program for Insertion Sort Algorithm.

# Python code Implementation of Insertion Sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key

# Example
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [5, 6, 11, 12, 13]

• Time Complexity: O(n^2) where n is the size of the given array. 

• Space Complexity: O(1) because it uses a constant amount of extra space.

Dutch National Flag Algorithm | Explanation | Code.

The Dutch National Flag algorithm is a Computer Science problem proposed by Edsger W. Dijkstra, a Dutch computer scientist. It is used for sorting an array of 0s, 1s, and 2s (or any other two distinct elements). It partitions the array into three segments - the low segment containing 0s, the middle segment containing 1s, and the high segment containing 2s.

Dutch National Flag Problem.

Given an array containing elements that can take one of three distinct values (e.g., red, white, and blue), the task is to sort the array in place such that elements of the same value are grouped together and the array is partitioned into three sections:

• All elements less than a certain value (e.g., red).
• All elements equal to that value.
• All elements greater than a certain value (e.g., blue).

Example:

Suppose the array represents colors: [1, 0, 2, 1, 0, 2] (0 for red, 1 for white, 2 for blue).

Initial Array:
[1, 0, 2, 1, 0, 2]

Sorted Array:
[0, 0, 1, 1, 2, 2]

Dutch National Flag Algorithm Explain.

This algorithm is used for partitioning elements within an array containing multiple distinct values, grouping similar elements together efficiently in a single pass through the array.

Step 1: Initialize three-pointers low, mid, and high where low and mid-pointers point to the start of the array and high pointer points to the end of the array.

Step 2: Start iterating through the array while mid is less than or equal to high:

• If the element at mid is the lower value (0) then swap the element at low with the element at mid and increment both low and mid.
• If the element at mid is the middle value (1) then increment mid by 1.
• If the element at mid is the higher value (2) then swap the element at mid with the element at high and decrement high.

Step 3: Keep repeating step 2 until mid crosses high, ensuring all elements are appropriately sorted. 

Working Example of Dutch National Flag Algorithm.

This algorithm basically sorts an array containing only three different types of values. Below we are showing the operation it performs in each iteration.

Iteration	Array	Operation/Description
1.	[1, 0, 2, 1, 0, 2]	Initial array
2.	[0, 0, 2, 1, 1, 2]	Swap 1 at index 0 with 0 at index 1
3.	[0, 0, 2, 1, 1, 2]	Increment 'mid'
4.	[0, 0, 2, 1, 1, 2]	Increment 'mid'
5.	[0, 0, 2, 1, 1, 2]	Swap 2 at index 2 with 2 at index 5
6.	[0, 0, 1, 1, 2, 2]	Decrement 'high' and Increment 'mid'

I hope that now you have understood the workings of the Dutch National Flag Algorithm and we are going to implement this algorithm using different programming languages such as C, C++, Python, and Java.

C Code Implementation:

// C Code Implementation of Dutch National Flag Algorithm
#include <stdio.h>

// Function to swap two values
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// function definition
void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;

    while (mid <= high) {
        switch(nums[mid]) {
            case 0:
                swap(&nums[low++], &nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(&nums[mid], &nums[high--]);
                break;
        }
    }
}

int main() {
    int nums[] = {1, 0, 2, 1, 0, 2};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    sortColors(nums, numsSize);

    printf("Sorted Array: ");
    for (int i = 0; i < numsSize; ++i) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

Output:

Sorted Array: 0 0 1 1 2 2

C++ Code Implementation:

// C++ code implementation of Dutch National Flag Algorithm
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        switch(nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

int main() {
    vector<int> nums = {1, 0, 2, 1, 0, 2};

    sortColors(nums);

    cout << "Sorted Array: ";
    for (int i = 0; i < nums.size(); ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Sorted Array: 0 0 1 1 2 2

Java Code Implementation:

// Java Code Implementation for Dutch National Flag Algorithm
public class DutchNationalFlag {
    // Function
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            switch(nums[mid]) {
                case 0:
                    int tempLow = nums[low];
                    nums[low++] = nums[mid];
                    nums[mid++] = tempLow;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    int tempHigh = nums[high];
                    nums[high--] = nums[mid];
                    nums[mid] = tempHigh;
                    break;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 1, 0, 2};

        sortColors(nums);

        System.out.print("Sorted Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Output:

Sorted Array: 0 0 1 1 2 2

Python Code Implementation:

# Python Code Implementation of Dutch National Flag Algorithm
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

nums = [1, 0, 2, 1, 0, 2]

sortColors(nums)

print("Sorted Array:", nums)

Output:

Sorted Array: 0 0 1 1 2 2

Time and Space Complexity.

Time Complexity: The Dutch National Flag Algorithm processes each element in the array exactly once so the time complexity is O(n) where n is the number of elements in the array.

Space Complexity: The algorithm performs sorting in the same array without using additional data structures. It uses only a few variables (pointers) to manipulate the array elements, resulting in contact space usage O(1). 

Program to find third distinct maximum number in the array.

Given an integer array nums[] of size n, we need to find the third distinct maximum number in an integer array nums. If the third maximum number does not exist, we need to return the maximum number present in the array.

Note: If the array has less than three distinct maximum numbers, then we need to return the maximum number from the array.

Let's understand the problem with an example:

Example 1:
Input: nums[] = {3, 5, 1, 8, 5, 4, 2, 9}
Output: 5

Explanation: 

The distinct maximum numbers in the array are 9, 8, and 5. 
So, the third distinct maximum number is 5. 

Example 2:
Input: nums[] = {2, 8}
Output: 8

Explanation: 

No third element is present in the given array 
so return the maximum element that is 8

Example 3:
Input: nums[] = {2, 2, 3, 1}
Output: 1

Explanation: 

The distinct maximum numbers in the array are 3, 2, and 1. 

So, the third distinct maximum number is 1. 

There are multiple approaches by which we can solve this problem and here we are going to discuss each of them one by one.

Approach 1: Using Sorting.

The brute force approach to solve this problem is by arranging the given array in descending order which will make our task easier to find the third distinct element.

Steps-by-step algorithm:

Step 1: We can sort the array in descending order.

Step 2: Then, we can iterate through the sorted array and keep track of distinct maximum numbers.

Step 3: If we find the third distinct maximum number, we return it. Otherwise, we return the maximum number.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    //arrange the vector in descending order
    sort(nums.begin(), nums.end(), greater<int>());

    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            count++;
        }
        if (count == 3) {
            return nums[i];
        }
    }
    //return max if no third distinct max is found
    return nums[0];
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Time Complexity: The sorting operation using sort takes O(n * log n) time, where n is the number of elements in the input array. After sorting, we iterate through the sorted array once to find the third distinct maximum number. This step takes O(n) time. So, the overall time complexity is O(n * log n + n) = O(n * log n).

Space Complexity: The space complexity is O(1) as we are not using any additional data structure. 

Approach 2: Using Set.

As we know a set container is used to store unique elements in a specific order and allows for efficient insertion, deletion, and retrieval of elements based on their values. 

Step-by-step algorithm:

Step 1: We can use a set to keep track of distinct numbers while traversing the array.

Step 2: If the set size is less than 3 after traversing the array, it means we have less than three distinct maximum numbers, so we return the maximum number present in the array.

Step 3: If the set size is greater than or equal to 3, we return the third element from the set.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum using set
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    set<int> distinctNums;

    //traverse the array and atmost
    //store three elements in the set
    for (int num : nums) {
        distinctNums.insert(num);
        if (distinctNums.size() > 3) {
            distinctNums.erase(distinctNums.begin());
        }
    }
    //size of set is less than 3 
    //no third distinct element present
    if(distinctNums.size() < 3)
    //return max element present in set
       return *(--distinctNums.end());
    //size of set is equal to 3 
    //top most element of set is the third distinct
    else
       return *(distinctNums.begin());
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Note: The expression *(--distinctNums.end()) is used to access the last element in a set. 

Time Complexity: The set insertion and deletion operations have an average time complexity of O(log n) then we iterate through the entire input array once, performing set operations on each element, so the overall time complexity is O(n * log n).

Space Complexity: The space required for the set depends on the number of distinct elements in the array, which is at most 3 in this case. Therefore, the space complexity is O(1), as it remains constant regardless of the input size.

Approach 3: Using three variables. (Most Optimized).

The idea for this optimized approach comes from the requirement to find the third distinct maximum number in a single pass through the array with O(n) time complexity. To achieve this efficiently, we need to keep track of the first, second, and third distinct maximum numbers while traversing the array.

Step-by-step algorithm:

Step 1: We declare three variables (firstMax, secondMax, thirdMax) to keep track of the first, second, and third distinct maximum numbers, respectively.

Step 2: We initialize them with the minimum possible value (INT_MIN).

Step 3: We traverse the input array and update these variables as follows:

• If the current number is greater than firstMax, we update thirdMax with secondMax, secondMax with firstMax, and then update firstMax with the current number.
• If the current number is between firstMax and secondMax, we update thirdMax with secondMax and secondMax with the current number.
• If the current number is between secondMax and thirdMax, we update thirdMax with the current number.

Step 4: After the loop, if thirdMax remains equal to the initial value (INT_MIN), it means there are less than three distinct maximum numbers in the array, and we return firstMax (the maximum number). Otherwise, we return thirdMax.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <bits/stdc++.h>
using namespace std;

int thirdMax(vector<int>& nums) {
    int firstMax = INT_MIN;
    int secondMax = INT_MIN;
    int thirdMax = INT_MIN;

    for (int num : nums) {
        //current number is greater
        if (num > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = num;
        } 
        //current number is between first and second max
        else if (num < firstMax && num > secondMax) {
            thirdMax = secondMax;
            secondMax = num;
        } 
        //current number is between second and third max
        else if (num < secondMax && num > thirdMax) {
            thirdMax = num;
        }
    }

    return (thirdMax == INT_MIN) ? firstMax : thirdMax;
}


int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2};

    cout<< thirdMax(nums);

    return 0;
}

Output:

4

Time Complexity: The time complexity of this solution is O(n) as we are able to find the required answer just in a single traversal. 

Space Complexity: The space complexity is constant O(1) as we are only using three variables for solving this problem. 

I hope you are able to understand all three approaches to solving this problem. We have covered all three approaches in sequence order from brute force to optimized one.