Algorithm 3 - Stack and Queue

Welcome to the world of algorithms! In this guide, we'll unravel the intricacies of Stack and Queue, essential data structures that empower efficient problem-solving. Let's dive into solving problems with stacks and queues, exploring solutions to challenges like Valid Parentheses, Min Stack, Daily Temperatures, and Car Fleet. 🚀

Valid Parentheses (Easy)

Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is valid.

Examples:

Example 1:
```
Input: s = '()'
Output: true
```
Example 2:
```
Input: s = '()[]{}'
Output: true
```
-Example 3:

Input: s = "(]"
  Output: false

Solutions:

We use a stack to keep track of the opening parentheses. When we encounter a closing parenthesis, we check if it matches the corresponding opening parenthesis at the top of the stack.

def isValid(s):
    # Initialize an empty stack to keep track of opening parentheses
    stack = []

    # Mapping of closing to opening parentheses
    mapping = {')': '(', '}': '{', ']': '['}

    # Iterate through each character in the input string
    for char in s:
        # If the character is a closing parenthesis
        if char in mapping:
            # Pop the top element from the stack if it's not empty, else use '#'
            top_element = stack.pop() if stack else '#'

            # Check if the mapping is correct for the current closing parenthesis
            if mapping[char] != top_element:
                return False
        else:
            # If the character is an opening parenthesis, push it onto the stack
            stack.append(char)

    # The string is valid if the stack is empty, indicating all parentheses are matched
    return not stack

Time Complexity (TC): O(N)
Space Complexity (SC): O(N)

Min Stack (Easy)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Examples

Example 1:

Input: ['MinStack', 'push', 'push', 'push', 'getMin', 'pop', 'top', 'getMin'][
  ([], [-2], [0], [-3], [], [], [], [])
]
Output: [null, null, null, null, -3, null, 0, -2]

Example 2:

Input: ['MinStack', 'push', 'pop', 'top', 'getMin'][([], [0], [], [], [])]
Output: [null, null, null, 0, 0]

Solutions

We use two stacks, one to store the elements and the other to keep track of the minimum element at each step.

class MinStack:
    def __init__(self):
        # Initialize two stacks, one for elements and one for minimum values
        self.stack = []
        self.min_stack = []

    def push(self, x):
        # Add the element to the main stack
        self.stack.append(x)

        # Check if the min_stack is empty or the new element is smaller than the current minimum
        if not self.min_stack or x <= self.min_stack[-1]:
            # If true, add the new element to the min_stack
            self.min_stack.append(x)

    def pop(self):
        # Check if the main stack is not empty
        if self.stack:
            # If the element being popped is the current minimum, also pop from the min_stack
            if self.stack.pop() == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self):
        # Return the top element of the main stack if it's not empty
        return self.stack[-1] if self.stack else None

    def getMin(self):
        # Return the top element of the min_stack if it's not empty
        return self.min_stack[-1] if self.min_stack else None

Time Complexity (TC): O(1) for all operations.
Space Complexity (SC): O(N)

Evaluate Reverse Polish Notation (Medium)

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

Examples

Example 1:

Input: ["evalRPN", "2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["evalRPN", "4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["evalRPN", "10", "6", "9", "3", "/", "-", "*"]
Output: 21
Explanation: ((10 * (6 / 9)) - 3) = 21

Solutions

We use a stack to keep track of operands and perform operations based on the encountered operators.

def evalRPN(tokens):
    stack = []

    for token in tokens:
        if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
            # If the token is a number, push it onto the stack
            stack.append(int(token))
        else:
            # If the token is an operator, pop two operands from the stack, perform the operation, and push the result back
            operand2 = stack.pop()
            operand1 = stack.pop()

            if token == '+':
                stack.append(operand1 + operand2)
            elif token == '-':
                stack.append(operand1 - operand2)
            elif token == '*':
                stack.append(operand1 * operand2)
            elif token == '/':
                # Handle division by checking for zero and truncate toward zero
                stack.append(int(operand1 / operand2))

    return stack[-1]

Time Complexity (TC): O(N), where N is the number of tokens.
Space Complexity (SC): O(N)

Largest Rectangle in Histogram (Hard)

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Examples

Example 1:

Input: [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is shown in the shaded area, which has an area = 2 * 5 = 10.

Example 2:

Input: [2, 4]
Output: 4

Example 3:

Input: [2]
Output: 2

Solutions

We use a stack to keep track of the indices of increasing bar heights and calculate the maximum area.

def largestRectangleArea(heights):
    stack = []
    max_area = 0

    for i, height in enumerate(heights):
        while stack and height < heights[stack[-1]]:
            # Pop the stack while the current height is smaller than the previous bar
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)

        stack.append(i)

    # Process the remaining bars in the stack
    while stack:
        h = heights[stack.pop()]
        w = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, h * w)

    return max_area

Time Complexity (TC): O(N), where N is the number of bars in the histogram.
Space Complexity (SC): O(N)

Wrap Up

🚀 Navigating the realms of Stack and Queue, we've uncovered the power of these fundamental data structures in algorithmic problem-solving. From validating parentheses to designing a Min Stack, these structures have proven to be versatile and efficient tools in our algorithmic toolkit.

💡 Stack, with its Last In, First Out (LIFO) structure, and Queue, with its First In, First Out (FIFO) structure, offer elegant solutions to a wide array of problems. Whether it's tracking parentheses validity or efficiently managing elements in a data structure, these concepts have demonstrated their applicability across various domains.

🌐 As we conclude our exploration of Stack and Queue, let's carry forward the insights gained and continue refining our problem-solving skills. These foundational concepts serve as pillars in algorithmic thinking, paving the way for tackling more complex challenges. Here's to the continuous journey of learning and mastering the intricacies of algorithms! 🧠✨