Day 17: Stack & Queue Problems 🧑‍💻

Problem 1: Implement a Stack using a List

Problem Statement

Implement a Stack class that supports three basic operations: push, pop, and peek. The stack should be implemented using a list or a dynamic array and must follow the Last-In, First-Out (LIFO) principle.

• push(item): Adds an item to the top of the stack.
• pop(): Removes and returns the item at the top of the stack. If the stack is empty, it should raise an error or return a specific value like None.
• peek(): Returns the item at the top of the stack without removing it. If the stack is empty, it should handle the case gracefully.

Input/Output Examples

stack = Stack()
stack.push(10)
stack.push(20)
print(stack.peek())   # Output: 20
stack.push(30)
print(stack.pop())    # Output: 30
print(stack.pop())    # Output: 20

Constraints

• The elements pushed onto the stack can be of any data type.
• The underlying list/array should not have a fixed size.

Solution

Problem 2: Implement a Queue using Two Stacks

Problem Statement

Implement a Queue class using two stacks. Your queue should support the standard First-In, First-Out (FIFO) operations: enqueue (add an item to the back) and dequeue (remove an item from the front).

You can only use the standard stack operations: push, pop, peek, and isEmpty.

Input/Output Examples

queue = QueueWithStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.dequeue())  # Output: 2
queue.enqueue(4)
print(queue.dequeue())  # Output: 3
print(queue.dequeue())  # Output: 4

Constraints

• You must use two stacks to implement the queue.
• The amortized time complexity for each operation should be $O(1)$.

Solution

Problem 3: Check for Balanced Parentheses

Problem Statement

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Input/Output Examples

is_balanced("()[]{}")  # Output: True
is_balanced("([)]")   # Output: False
is_balanced("{[]}")    # Output: True
is_balanced("(")      # Output: False
is_balanced("())")     # Output: False

Constraints

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Solution

Problem 4: Implement a Circular Queue

Problem Statement

Design a circular queue (also known as a ring buffer). A circular queue is a fixed-size queue in which the last position is connected back to the first one to make a circle. The implementation should be based on an array and support the following operations:

• enqueue(value): Insert an element into the circular queue. Return True if the operation is successful, else False.
• dequeue(): Delete an element from the circular queue. Return the value if successful, else -1.
• is_full(): Checks whether the circular queue is full or not.
• is_empty(): Checks whether the circular queue is empty or not.

Input/Output Examples

cq = CircularQueue(3)  # Create a queue of size 3
cq.enqueue(1)          # Returns True
cq.enqueue(2)          # Returns True
cq.enqueue(3)          # Returns True
cq.enqueue(4)          # Returns False (Queue is full)
print(cq.is_full())    # Output: True
print(cq.dequeue())    # Output: 1
cq.enqueue(4)          # Returns True (space is now available)
print(cq.dequeue())    # Output: 2

Constraints

• The size of the queue k will be between 1 and 1000.
• All values will be in the range of [0, 1000].

Solution

Problem 5: Find the Next Greater Element

Problem Statement

Given an array of integers arr, find the Next Greater Element (NGE) for each element in the array. The NGE for an element x is the first element to its right that is greater than x. If no such element exists, the NGE is considered to be -1.

Your task is to return an array of the same size, where each index contains the NGE for the element at the corresponding index in the input array.

Input/Output Examples

Example 1:

Input: arr = [4, 5, 2, 25]
Output: [5, 25, 25, -1]

Explanation:

• The next greater element for 4 is 5.
• The next greater element for 5 is 25.
• The next greater element for 2 is 25.
• There is no greater element for 25, so it's -1.

Example 2:

Input: arr = [13, 7, 6, 12]
Output: [-1, 12, 12, -1]

Constraints

• 1 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^9

Solution