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.

Check Balanced Parenthesis in an Expression.

Given an expression containing various types of parentheses ((), {}, []), you need to determine if the parentheses are balanced. An expression is considered balanced if every opening parenthesis has a corresponding closing parenthesis and they occur in the correct order.

Example:

Input: ({[]})

Output: true

Explanation: All pairs of parenthesis are balanced.

Input: ())(

Output: false

Explanation: All pairs of parenthesis are not balanced.

Input: [(){}]

Output: true

There are different ways to solve this problem and here we are going to discuss two of them:

Check Valid Balanced Parenthesis Using Stack.

In this approach, we use a stack data structure to solve this problem of checking balance parenthesis. It is because by nature parenthesis must occur in pairs and in the correct order and the stack LIFO property is best to handle such patterns.

Algorithm Steps to Validate Parenthesis:

Step 1: Initialize an empty stack to hold the opening parenthesis.

Step 2: Iterate through each character of the expression:

• If the character is an opening parenthesis ('(', '{', '['), push it onto the stack.
• If the character is a closing parenthesis (')', '}', ']') then check if the stack is empty then return false (unbalanced) else pop the top element and check if it matches with the closing parenthesis.
• If the closing parenthesis does not match with the top element of the stack then return false.

Step 3: After iteration, check if the stack is empty (balanced) and return true, else return false (unbalanced).

Example Illustration.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code implementation to check balanced parenthesis
#include<iostream>
#include<stack>
using namespace std;

//function to check balance parenthesis
bool validParenthesis(string str){
    stack<char> st;

    for(int i = 0; i < str.size(); i++){
        //opening parenthesis, push into the stack
        if(str[i] == '{' || str[i] == '[' || str[i] == '(') {
            st.push(str[i]);    
        }else if(str[i] == '}' || str[i] == ']' || str[i] == ')') {
            
            //empty stack
            if(st.empty())
               return false;
            
            //check if stack top contain a matching opening bracket
            //pop the top element if matching is found
            if((st.top() == '{' && str[i] == '}') 
            || (st.top() == '[' && str[i] == ']') 
            || (st.top() == '(' && str[i] == ')')) {
                st.pop();
            }
            else{
                return false;
            } 
        }
    }
    //stack is empty after complete iteration
    if(st.empty()) 
       return true;
    
    return false;   
}
int main() {
    string str = "[{(){()}}]";

    if(validParenthesis(str)){
        cout<<"Balance Parenthesis"<<endl;
    }else{
        cout<<"Unbalance Parenthesis"<<endl;
    }
    return 0;
}

// Java Code Implementation to check balanced parenthesis
import java.util.Stack;

public class ParenthesisChecker {
    public static boolean isValidParenthesis(String str) {
        Stack<Character> stack = new Stack<>();
        //push the char in stack if they are opening brackets
        for (char ch : str.toCharArray()) {
            if (ch == '{' || ch == '[' || ch == '(') {
                stack.push(ch);
            } else if (ch == '}' || ch == ']' || ch == ')') {
                if (stack.isEmpty()) return false;
                
             
              //pop the top element if matching bracket is found
                char top = stack.pop();
                if ((top == '{' && ch == '}') || (top == '[' && ch == ']') 
                || (top == '(' && ch == ')')) {
                    continue;
                } else {
                    return false; // Mismatched brackets
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String str = "[{(){()}}]";

        if (isValidParenthesis(str)) {
            System.out.println("Balanced Parenthesis");
        } else {
            System.out.println("Unbalanced Parenthesis");
        }
    }
}

# Python code to check balanced parenthesis
def is_valid_parenthesis(s):
stack = []

for char in s:
    # checking for open brackets
    if char in '{[(':
        stack.append(char)
    # checking for closing brackets    
    elif char in '})]':
        if not stack:
            return False
        
        # pop the top char from stack if matching pair is found
        top = stack.pop()
        if (top == '{' and char == '}') or (top == '[' and char == ']') or (top == '(' and char == ')'):
            pass
        else:
            return False  # Mismatched brackets

return not stack


# Example usage
parenthesis_str = "[{(){()}}]"
if is_valid_parenthesis(parenthesis_str):
print("Balanced Parenthesis")
else:
print("Unbalanced Parenthesis")

// C# code to check balanced parenthesis
using System;
using System.Collections.Generic;

class ParenthesisChecker
{
    static bool IsValidParenthesis(string str)
    {
        Stack<char> stack = new Stack<char>();

        foreach (char ch in str)
        {   // push the char in stack if it is opening bracket
            if (ch == '{' || ch == '[' || ch == '(')
            {
                stack.Push(ch);
            }
            // pop the top char from stack if it is matching pair of closing bracket 
            else if (ch == '}' || ch == ']' || ch == ')')
            {
                if (stack.Count == 0) return false;

                char top = stack.Pop();
                if ((top == '{' && ch == '}') || (top == '[' && ch == ']') 
                  || (top == '(' && ch == ')'))
                {
                    continue;// Matching brackets, continue
                }
                else
                {
                    return false; // Mismatched brackets
                }
            }
        }

        return stack.Count == 0;
    }

    static void Main()
    {
        string str = "[{(){()}}]";

        if (IsValidParenthesis(str))
        {
            Console.WriteLine("Balanced Parenthesis");
        }
        else
        {
            Console.WriteLine("Unbalanced Parenthesis");
        }
    }
}

Output:

Balanced Parenthesis

• Time Complexity: The algorithm iterates through each character in the expression once, resulting in a time complexity of O(n), where n is the length of the expression.
• Space Complexity: The space complexity is O(n), where n is the length of the expression. This is due to the stack storing opening parentheses, and in the worst case, the stack may contain all opening parentheses before encountering the corresponding closing ones.

Check Balanced Parenthesis Without Using Stack.

While the stack is a convenient data structure for checking balanced parentheses, it's possible to achieve the same goal without using a stack. 

Algorithm Steps:

Step 1: Initialize an integer variable i to -1. This variable will be used to track the top of the stack.

Step 2: Iterate through the expression:

• If ch is an opening parenthesis ('(', '{', '[') then increase the value of i by 1 and replace the character at index i in the expression with the opening bracket.
• If ch is a closing parenthesis (')', '}', ']') check if i is greater than or equal to 0. Check if the current closing bracket matches the corresponding opening bracket at index i: If yes, decrement i by 1 else returns false.

Step 3: After completing the iteration check if i is equal to -1 return true else return false.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code to check balance parenthesis without stack
#include<iostream>
using namespace std;

//function to check parenthesis is balance or not
bool validParenthesis(string str) {
    // Initialize an index variable for tracking the top of the stack
    int i = -1;

    for(int j  = 0; j < str.size(); j++) {

        if(str[j] == '{' || str[j] == '[' || str[j] == '('){

           // Increment counter for opening parenthesis 
           i++;

           // Replace ith character with the opening bracket
           str[i] = str[j];
        }
        else{
          if(i >= 0 && ((str[i] == '(' && str[j] == ')') 
                     || (str[i] == '{' && str[j] == '}') 
                     || (str[i] == '[' && str[j] == ']'))) {
            // Decrement counter for matching closing parenthesis
            i--;
          }
          else {
            return false;
          }
        }
    }
    // -1 indicate that stack is empty (balanced parenthesis)
    if(i == -1) return true;
    
    return false;
}
int main() {
    string str = "({[][{]})";

    if(validParenthesis(str)){
        cout<<"Balance Parenthesis"<<endl;
    }else{
        cout<<"Unbalance Parenthesis"<<endl;
    }
    return 0;
}

// Java code implementation to check valid parenthesis
import java.util.Scanner;

public class Main {
    // Function to check if parentheses are balanced
    static boolean validParenthesis(String str) {
        StringBuilder sb = new StringBuilder();
        int i = -1;

        for (int j = 0; j < str.length(); j++) {
            char ch = str.charAt(j);

            if (ch == '{' || ch == '[' || ch == '(') {
                i++;
                sb.append(ch);
            } else {
                if (i >= 0 && ((sb.charAt(i) == '(' && ch == ')') || 

                   (sb.charAt(i) == '{' && ch == '}') || (sb.charAt(i) == '[' && ch == ']'))) {
                    i--;
                } else {
                    return false;
                }
            }
        }
        return i == -1;
    }

    public static void main(String[] args) {
        String str = "({[][{]})";

        if (validParenthesis(str)) {
            System.out.println("Balanced Parenthesis");
        } else {
            System.out.println("Unbalanced Parenthesis");
        }
    }
}

# Python program to validate parenthesis
def validParenthesis(s):
i = -1

for j in range(len(s)):
    if s[j] in ['{', '[', '(']:
        i += 1
        s = s[:i + 1] + s[j]
    else:
        if i >= 0 and ((s[i] == '(' and s[j] == ')') or (s[i] == '{' and s[j] == '}') or (s[i] == '[' and s[j] == ']')):
            i -= 1
        else:
            return False

return i == -1

str_value = "({[][{]})"
if validParenthesis(str_value):
print("Balanced Parenthesis")
else:
print("Unbalanced Parenthesis")

// C# code to check valid balanced parenthesis
using System;

class Program
{
    // Function to check if parentheses are balanced
    static bool ValidParenthesis(string str)
    {
        int i = -1;
        char[] sb = new char[str.Length];
        for (int j = 0; j < str.Length; j++)
        {
            char ch = str[j];

            if (ch == '{' || ch == '[' || ch == '(')
            {
                i++;
                sb[i] = ch;
            }
            else
            {
                if (i >= 0 && ((sb[i] == '(' && ch == ')') || (sb[i] == '{' && ch == '}') 

                   || (sb[i] == '[' && ch == ']')))
                {
                    i--;
                }
                else
                {
                    return false;
                }
            }
        }
        return i == -1;
    }

    static void Main()
    {
        string str = "({[][]})";

        if (ValidParenthesis(str))
        {
            Console.WriteLine("Balanced Parenthesis");
        }
        else
        {
            Console.WriteLine("Unbalanced Parenthesis");
        }
    }
}

Output:

Unbalanced Parenthesis

• Time Complexity: Time complexity of the above solution in O(n) where n is the length of the given expression.
• Space Complexity: Space complexity is O(1) if it is allowed to modify the existing string otherwise, it will be O(n).