Delete Middle Element of Stack.

Given a stack of integers. The task is to delete the middle element from the stack without using extra space. The middle element is defined as the element at position (size of stack / 2 +1). Write a function/method that takes the stack as input and modifies it to delete the middle element.

Example:

Input:  [1, 2, 3, 4, 5]

Output: [1, 2, 4, 5]

Explanation: The middle element is 3, and after deletion, the stack becomes [1, 2, 4, 5].

Input:  [10, 20, 30, 40, 50, 60]

Output: [10, 20, 30, 50, 60]

Explanation: The middle element is 40, and after deletion, the stack becomes [10, 20, 30, 50, 60].

It is very easy to delete the middle element of the given stack by using any extra data structure. Still, the main challenge of this problem is to solve this without using any additional space. Actually, that is also quite simple if our powerful programming tool known as recursion. Before moving to the recursive solution to delete the middle element of the stack. Let's check a simple brute-force solution for this.

Brute Force Approach to Delete Middle Element of Stack.

In this approach, we will use another auxiliary stack or a list to store the given stack element until we reach the middle element and then we will remove (pop) the middle element from the stack and then push back all the elements of the auxiliary stack back to the main stack.

Algorithm Steps:

• Create a stack auxStack to temporarily store elements.
• Calculate the position of the middle element (middle = size / 2 +1).
• Iterate over the first half of the original stack (up to the element just before the middle) and Push each element to the auxStack and pop it from the original stack.
• Skip the middle element of the stack and pop it from the original stack.
• Pop elements from the auxStack and push them back to the original stack.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code implementation to delete middle element of stack
// Brute force approach using extra space
#include <iostream>
#include <stack>
using namespace std;

// Function to delete the middle element of a stack without recursion
void deleteMiddle(stack<int>& s) {
    int size = s.size();
    int middle = size / 2 + 1;

    stack<int> auxStack;

    // Push the first half of elements to the auxiliary stack
    for (int i = 0; i < middle - 1; i++) {
        auxStack.push(s.top());
        s.pop();
    }

    // Skip the middle element
    s.pop();

    // Push the elements back to the original stack
    while (!auxStack.empty()) {
        s.push(auxStack.top());
        auxStack.pop();
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    // Example usage
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    // Delete the middle element without recursion
    deleteMiddle(myStack);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

// Java code implementation to delete middle element of stack
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> myStack = new Stack<>();

        // Push elements onto the stack
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);

        System.out.println("Original Stack: " + myStack);

        // Delete the middle element without recursion
        deleteMiddle(myStack);

        System.out.println("Stack after deleting middle element: " + myStack);
    }

    // Function to delete the middle element of a stack without recursion
    public static void deleteMiddle(Stack<Integer> s) {
        int size = s.size();
        int middle = size / 2 + 1;

        Stack<Integer> auxStack = new Stack<>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.push(s.pop());
        }

        // Skip the middle element
        s.pop();

        // Push the elements back to the original stack
        while (!auxStack.isEmpty()) {
            s.push(auxStack.pop());
        }
    }
}

# Python code to delete middle element of stack
def delete_middle(s):
size = len(s)
middle = size // 2 + 1

aux_stack = []

# Push the first half of elements to the auxiliary stack
for i in range(middle - 1):
    aux_stack.append(s.pop())

# Skip the middle element
s.pop()

# Push the elements back to the original stack
while aux_stack:
    s.append(aux_stack.pop())

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)

# Delete the middle element without recursion
delete_middle(my_stack)

print("Stack after deleting middle element:", my_stack)

// C# code implementation to delete middle element of stack
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        // Delete the middle element without recursion
        DeleteMiddle(myStack);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack without recursion
    public static void DeleteMiddle(Stack<int> s) {
        int size = s.Count;
        int middle = size / 2 + 1;

        Stack<int> auxStack = new Stack<int>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.Push(s.Pop());
        }

        // Skip the middle element
        s.Pop();

        // Push the elements back to the original stack
        while (auxStack.Count > 0) {
            s.Push(auxStack.Pop());
        }
    }
}

Output:

Original Stack: 5 4 3 2 1
Stack after deleting middle element: 5 4 2 1

• Time Complexity: O(n) where n is the number of elements present in the given stack.
• Space Complexity: O(n) as we are using an extra stack to delete the middle element of the stack.

Delete Middle Element of the Stack Using Recursion.

We can delete the middle element of the stack using recursion without using any extra space. In this approach, we will recursively pop the stack element, and while unwinding we will push back all the elements except the middle element.

Algorithm Steps:

• The base case of our recursive call is when our stack gets empty.
• Pop an element from the stack and recursively call the function.
• While unwinding from the recursive calls, increment a counter to keep track of the number of elements.
• If the counter indicates the middle element, skip pushing it back onto the stack.
• While unwinding, push the elements back onto the stack.

Below is the code implementation of the above recursive approach:

C++ Java Python C#

// C++ code for recurisvely delete middle element of stack
#include <iostream>
#include <stack>

using namespace std;

// Function to delete the middle element of a stack using recursion
void deleteMiddle(stack<int>& s, int current, int middle) {
    // Base case: stack is empty
    if (s.empty()) {
        return;
    }

    // Recursive call: pop an element and make a recursive call
    int temp = s.top();
    s.pop();
    deleteMiddle(s, current + 1, middle);

    // Count elements and skip pushing the middle element
    if (current != middle) {
        s.push(temp);
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    int middle = myStack.size() / 2;
    
    // Delete the middle element using recursion
    deleteMiddle(myStack, 0, middle);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

import java.util.Stack;

public class Main {
  public static void main(String[] args) {
      Stack<Integer> myStack = new Stack<>();

      // Push elements onto the stack
      myStack.push(1);
      myStack.push(2);
      myStack.push(3);
      myStack.push(4);
      myStack.push(5);

      System.out.println("Original Stack: " + myStack);

      int middle = myStack.size() / 2;

      // Delete the middle element using recursion
      deleteMiddle(myStack, 0, middle);

      System.out.println("Stack after deleting middle element: " + myStack);
  }

  // Function to delete the middle element of a stack using recursion
  public static void deleteMiddle(Stack<Integer> s, int current, int middle) {
      if (s.isEmpty()) {
          return;
      }

      int temp = s.pop();
      deleteMiddle(s, current + 1, middle);

      if (current != middle) {
          s.push(temp);
      }
  }
}

# Python program to delete middle element of stack using Recursive

def delete_middle(s, current, middle):
# Base case: stack is empty
if not s:
    return

# Recursive call: pop an element and make a recursive call
temp = s.pop()
delete_middle(s, current + 1, middle)

# Count elements and skip pushing the middle element
if current != middle:
    s.append(temp)

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)
middle = len(my_stack) // 2

# Delete the middle element using recursion
delete_middle(my_stack, 0, middle)

print("Stack after deleting middle element:", my_stack)

//C# code to delete middle element of stack using Recursion
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        int middle = myStack.Count / 2;

        // Delete the middle element using recursion
        DeleteMiddle(myStack, 0, middle);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack using recursion
    public static void DeleteMiddle(Stack<int> s, int current, int middle) {
        if (s.Count == 0) {
            return;
        }

        int temp = s.Pop();
        DeleteMiddle(s, current + 1, middle);

        if (current != middle) {
            s.Push(temp);
        }
    }
}

Output:

Original Stack: 5 4 3 2 1 
Stack after deleting middle element: 5 4 2 1 

• Time Complexity: O(n) where n is the number of elements in the stack.
• Space Complexity: O(n) using auxiliary space for Recursion.

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.

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.