STACKS

A stack is a linear data structure that operates based on the last-in, first-out (LIFO) principle, meaning that the last element added to the stack is the first element to be removed. Stacks can be thought of as a collection of elements, with two main operations: push, which adds an element to the top of the stack, and pop, which removes the top element from the stack. Additionally, some implementations may have other operations such as peek, which allows you to look at the top element without removing it, or isEmpty, which returns true if the stack is empty and false otherwise.

Stacks can be implemented using various data structures such as arrays, linked lists, or dynamic arrays. The implementation details can impact the time and space complexity of the operations on the stack. For example, some implementations may have a fixed size, limiting the number of elements that can be added to the stack. Others may be dynamic, allowing for more elements to be added as needed. Additionally, the choice of implementation can impact the performance of different operations, such as adding or removing elements from the stack.

ARRAY BASED STACKS

An array-based stack is a data structure that is used to implement a stack using an array. A stack is an abstract data type that allows operations at one end only (the top), and follows the Last-In-First-Out (LIFO) principle, which means that the most recently added element is the first one to be removed.

In an array-based stack, the elements are stored in an array, and a variable called top points to the top of the stack. The top variable is initially set to -1 to indicate that the stack is empty. When a new element is added to the stack, the top variable is incremented by 1 and the new element is stored at the index top. When an element is removed from the stack, the top variable is decremented by 1.

Here is an example implementation of an array-based stack in Java:


public class ArrayStack<T> {
    private int top;
    private T[] array;

    public ArrayStack(int capacity) {
        this.array = (T[]) new Object[capacity];
        this.top = -1;
    }

    public void push(T element) {
        if (isFull()) {
            throw new StackOverflowError();
        }

        top++;
        array[top] = element;
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        T element = array[top];
        top--;
        return element;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return array[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == array.length - 1;
    }
}

In this implementation, we use a generic type T to allow the stack to hold any type of element. The push method adds an element to the top of the stack, the pop method removes and returns the element at the top of the stack, and the peek method returns the element at the top of the stack without removing it.

The isEmpty and isFull methods are used to check whether the stack is empty or full, respectively.

Note that this implementation has a fixed capacity, which means that the size of the stack is limited by the size of the array. If we try to add more elements than the capacity of the array, a StackOverflowError is thrown. If we try to remove an element from an empty stack, an EmptyStackException is thrown.

LINKED LIST BASED STACKS

A linked list-based stack is a data structure that is used to implement a stack using a linked list. A stack is an abstract data type that allows operations at one end only (the top), and follows the Last-In-First-Out (LIFO) principle, which means that the most recently added element is the first one to be removed.

In a linked list-based stack, the elements are stored in a linked list, and a pointer called top points to the top of the stack. The top pointer points to the first node in the linked list, and each node contains an element and a pointer to the next node. When a new element is added to the stack, a new node is created and inserted at the beginning of the linked list. When an element is removed from the stack, the first node in the linked list is removed.

Here is an example implementation of a linked list-based stack in Java:


public class LinkedListStack<T> {
    private Node<T> top;

    public void push(T element) {
        Node<T> newNode = new Node<>(element);

        newNode.next = top;
        top = newNode;
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        T element = top.element;
        top = top.next;
        return element;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return top.element;
    }

    public boolean isEmpty() {
        return top == null;
    }

    private static class Node<T> {
        private T element;
        private Node<T> next;

        public Node(T element) {
            this.element = element;
        }
    }
}

In this implementation, we use a generic type T to allow the stack to hold any type of element. The push method adds an element to the top of the stack by creating a new node and inserting it at the beginning of the linked list. The pop method removes and returns the element at the top of the stack by removing the first node in the linked list. The peek method returns the element at the top of the stack without removing it.

The isEmpty method is used to check whether the stack is empty.

Note that this implementation does not have a fixed capacity, which means that the size of the stack can grow dynamically. If we try to remove an element from an empty stack, an EmptyStackException is thrown.

PATTERNS

BALANCED PARENTHESES

Balanced Parentheses is a common pattern in stack problems where you need to check if the parentheses in a given string are balanced or not. A string with balanced parentheses means that for every opening parenthesis, there is a corresponding closing parenthesis in the correct order.

For example, the string "(()())" has balanced parentheses because each opening parenthesis has a corresponding closing parenthesis in the correct order. On the other hand, the string "(()" is not balanced because there is an opening parenthesis without a corresponding closing parenthesis.

To solve the balanced parentheses problem, you can use a stack to keep track of the opening parentheses. Whenever you encounter an opening parenthesis, push it onto the stack. Whenever you encounter a closing parenthesis, pop an element from the stack and check if it matches the closing parenthesis. If it doesn't match, then the parentheses are not balanced. If you reach the end of the string and the stack is empty, then the parentheses are balanced.

Here is an example Java code to check if a string has balanced parentheses:


public static boolean isBalanced(String str) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (ch == '(' || ch == '{' || ch ==
        '[') {
            stack.push(ch);
        } else if (ch == ')' && !stack.isEmpty()
        && stack.peek() == '(') {
            stack.pop();
        } else if (ch == '}' && !stack.isEmpty()
        && stack.peek() == '{') {
            stack.pop();
        } else if (ch == ']' && !stack.isEmpty()
        && stack.peek() == '[') {
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.isEmpty();
}

In this code, we use a stack to keep track of the opening parentheses. We iterate over the characters in the string, and whenever we encounter an opening parenthesis, we push it onto the stack. Whenever we encounter a closing parenthesis, we pop an element from the stack and check if it matches the closing parenthesis. If it doesn't match, then the parentheses are not balanced and we return false. If we reach the end of the string and the stack is empty, then the parentheses are balanced and we return true.

EVALUATE EXPRESSION

Evaluate Expressions is a common pattern in stack problems where you need to evaluate an expression that is in postfix or infix notation.

Postfix notation is a way of writing expressions where the operator comes after the operands. For example, the postfix notation for the expression "3 + 4 * 5" is "3 4 5 * +". In postfix notation, the order of evaluation is from left to right.

Infix notation is the normal way of writing expressions, where the operator is between the operands. For example, the infix notation for the expression "3 + 4 * 5" is "3 + (4 * 5)". In infix notation, the order of evaluation is determined by the precedence of the operators and the use of parentheses.

To evaluate an expression in postfix notation, you can use a stack to keep track of the operands and operators. Whenever you encounter an operand, push it onto the stack. Whenever you encounter an operator, pop the two operands from the stack, apply the operator to the operands, and push the result back onto the stack.

To evaluate an expression in infix notation, you can use the shunting-yard algorithm, which is based on the use of two stacks: one for the operators and one for the operands. The algorithm reads the input tokens one by one, and if it is an operand, push it onto the operand stack. If it is an operator, pop the operators from the operator stack until a lower or equal precedence operator is found, or a left parenthesis is encountered. Push the operator onto the operator stack. If a right parenthesis is encountered, pop the operators from the operator stack and apply them to the operands until a left parenthesis is encountered.

Here is an example Java code to evaluate an expression in postfix notation:


public static int evaluatePostfix(String exp) {
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < exp.length(); i++) {
        char ch = exp.charAt(i);
        if (Character.isDigit(ch)) {
            stack.push(ch - '0');
        } else {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            switch (ch) {
                case '+':
                   
        stack.push(operand1 + operand2);
                    break;

                case '-':
                   
        stack.push(operand1 - operand2);
                    break;

                case '*':
                   
        stack.push(operand1 * operand2);
                    break;

                case '/':
                   
        stack.push(operand1 / operand2);
                    break;

            }
        }
    }
    return stack.pop();
}

In this code, we use a stack to keep track of the operands and operators. We iterate over the characters in the expression, and whenever we encounter an operand, we push it onto the stack. Whenever we encounter an operator, we pop the two operands from the stack, apply the operator to the operands, and push the result back onto the stack. When we reach the end of the expression, the stack should contain only one element, which is the result of the expression.

Here is an example Java code to evaluate an expression in infix notation using the shunting-yard algorithm:


public static int evaluateInfix(String expression) {
    Stack<Integer> operandStack = new Stack<>();
    Stack<Character> operatorStack = new Stack<>();
    for (int i = 0; i < expression.length(); i++) {
        char ch = expression.charAt(i);
        if (Character.isDigit(ch)) {
            int operand = ch - '0';
            while (i + 1 < expression.length()
        && Character.isDigit(expression.charAt(i + 1))) {
                operand = operand * 10 +
        (expression.charAt(i + 1) - '0');
                i++;
            }
            operandStack.push(operand);
        } else if (ch == '+' || ch == '-' || ch
        == '*' || ch == '/') {
            while (!operatorStack.isEmpty() &&
        getPrecedence(ch) <= getPrecedence(operatorStack.peek())) {
                char operator =
        operatorStack.pop();
                int operand2 =
        operandStack.pop();
                int operand1 =
        operandStack.pop();
                int result =
        applyOperator(operand1, operand2, operator);
               
        operandStack.push(result);
            }
            operatorStack.push(ch);
        } else if (ch == '(') {
            operatorStack.push(ch);
        } else if (ch == ')') {
            while (!operatorStack.isEmpty() &&
        operatorStack.peek() != '(') {
                char operator =
        operatorStack.pop();
                int operand2 =
        operandStack.pop();
                int operand1 =
        operandStack.pop();
                int result =
        applyOperator(operand1, operand2, operator);
               
        operandStack.push(result);
            }
            operatorStack.pop(); // Pop the left
        parenthesis
        }
    }
    while (!operatorStack.isEmpty()) {
        char operator = operatorStack.pop();
        int operand2 = operandStack.pop();
        int operand1 = operandStack.pop();
        int result = applyOperator(operand1, operand2,
        operator);
        operandStack.push(result);
    }
    return operandStack.pop();
}

private static int getPrecedence(char operator) {
    switch (operator) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

private static int applyOperator(int operand1, int operand2, char operator) {

    switch (operator) {
        case '+':
            return operand1 + operand2;
        case '-':
            return operand1 - operand2;
        case '*':
            return operand1 * operand2;
        case '/':
            return operand1 / operand2;
        default:
            return 0;
    }
}

In this code, we use two stacks: one for the operands and one for the operators. We iterate over the characters in the expression, and whenever we encounter an operand, we push it onto the operand stack. Whenever we encounter an operator, we pop operators from the operator stack until we find a lower or equal precedence operator, or a left parenthesis. We push the operator onto the operator stack. Whenever we encounter a left parenthesis, we push it onto the operator stack. Whenever we encounter a right parenthesis, we pop operators from the operator stack and apply them to the operands until we find the corresponding left parenthesis. When we reach the end of the expression, we pop the remaining operators from the operator stack and apply them to the operands. The result is the only element on the operand stack.

REVERSE A SEQUENCE

Reversing a sequence is a common operation in computer programming. The idea is to take a sequence of elements (e.g. an array, a linked list, a string, etc.) and reverse the order of its elements. For example, if we have an array [1, 2, 3, 4], reversing it would result in [4, 3, 2, 1].

To reverse a sequence, we can use a simple algorithm called the "two-pointer" technique. The algorithm works as follows:

Initialize two pointers, one at the beginning of the sequence and one at the end of the sequence.
Swap the elements at the two pointers.
Move the first pointer one step forward and the second pointer one step backward.
Repeat steps 2-3 until the two pointers meet in the middle of the sequence.

Here is an example implementation of the two-pointer algorithm to reverse an array in Java:


public static void reverseArray(int[] arr) {
    int left = 0;  // pointer to the leftmost element of the
        array
    int right = arr.length - 1;  // pointer to the rightmost element
        of the array

    while (left < right) {
        // swap the elements at the left and right
        pointers
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // move the left pointer one step forward
        left++;

        // move the right pointer one step backward
        right--;
    }
}

This code takes an integer array as input and reverses its elements in place using the two-pointer technique. The time complexity of this algorithm is O(n/2), which reduces to O(n) in big O notation.

NEXT GREATER/SMALLER ELEMENT

Next Greater/Smaller Element is a common pattern in which we need to find the next greater or smaller element for each element in an array. The idea is to find the element that appears after the current element and is greater or smaller than the current element.

For example, given an array [4, 5, 2, 25], the next greater element for each element would be [5, 25, 25, -1], since 5 is the next greater element for 4, 25 is the next greater element for 5 and 2, and there is no next greater element for 25. Similarly, the next smaller element for each element would be [2, 2, -1, -1], since 2 is the next smaller element for 4 and 5, and there is no next smaller element for 2 and 25.

There are different ways to solve the "Next Greater/Smaller Element" problem depending on the constraints and requirements of the problem. However, a common approach is to use a stack to keep track of the elements for which we haven't found the next greater or smaller element yet.

The algorithm works as follows:

Initialize an empty stack and a result array of the same size as the input array, initialized with the default value (e.g. -1 for the next greater element and Integer.MAX_VALUE for the next smaller element).
Iterate over the input array from left to right.
For each element, pop all the elements from the top of the stack that are smaller or greater than the current element (depending on whether we are looking for the next greater or smaller element).
For each popped element, set the corresponding result value to the current element.
Push the current element onto the stack.
After the iteration, the result array contains the next greater or smaller element for each element.

Here is an example implementation of the Next Greater Element algorithm in Java:


public static int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] >
        nums[stack.peek()]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }

    return res;
}

This code takes an integer array as input and returns an array containing the next greater element for each element in the input array. The time complexity of this algorithm is O(n), where n is the length of the input array.

MAXIMUM AREA IN HISTOGRAM

The Maximum Area in Histogram problem involves finding the largest rectangular area that can be formed by a given histogram. A histogram is a bar chart that represents the distribution of numerical data.

For example, consider the histogram represented by the following array:

[2, 1, 5, 6, 2, 3]

The corresponding histogram can be visualized as follows:

In this case, the largest rectangular area that can be formed by the histogram is 10, which corresponds to the rectangle formed by the bars with heights 5 and 6.

There are different algorithms to solve the "Maximum Area in Histogram" problem, but one of the most popular is based on the use of a stack. The idea is to process the histogram bars from left to right, keeping track of the indices of the bars in a stack. If the current bar is taller than the previous bar in the stack, we push its index onto the stack. Otherwise, we pop the indices from the stack until we find a bar that is shorter than the current bar, and we calculate the area of the rectangle formed by this bar and the previous bar in the stack (or the current bar if the stack is empty).

Here is an example implementation of the Maximum Area in Histogram algorithm in Java:


public static int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()]
        >= heights[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() ? 0 : stack.peek() + 1;

        stack.push(i);
    }

    stack.clear();

    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()]
        >= heights[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() ? n - 1 : stack.peek() -
        1;
        stack.push(i);
    }

    int maxArea = 0;

    for (int i = 0; i < n; i++) {
        int area = (right[i] - left[i] + 1) * heights[i];

        maxArea = Math.max(maxArea, area);
    }

    return maxArea;
}

This code takes an integer array representing the heights of the histogram bars as input, and returns the largest rectangular area that can be formed by the histogram. The time complexity of this algorithm is O(n), where n is the length of the input array.

TRAPPING RAIN WATER

The "Trapping Rain Water" problem involves finding the total amount of water that can be trapped between the bars of a given histogram, where each bar has a width of 1 unit. The trapped water can only be contained within the histogram, and cannot spill over the edges.

For example, consider the following histogram:

[0,1,0,2,1,0,1,3,2,1,2,1]

The corresponding histogram can be visualized as follows:

In this case, the total amount of trapped water is 6 units.

There are different algorithms to solve the "Trapping Rain Water" problem, but one of the most popular is based on the use of two pointers. The idea is to maintain two pointers, one starting from the left and the other starting from the right, and move them towards each other. At each step, we compare the heights of the bars pointed by the two pointers, and compute the amount of trapped water as the difference between the minimum of the two heights and the height of the current bar. We update the pointers accordingly, and repeat the process until they meet.

Here is an example implementation of the "Trapping Rain Water" algorithm in Java:


public static int trap(int[] height) {
    int n = height.length;
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int trapped = 0;

    while (left <= right) {
        if (height[left] <= height[right]) {
            if (height[left] >= leftMax) {

                leftMax =
        height[left];
            } else {
                trapped += leftMax -
        height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {

                rightMax =
        height[right];
            } else {
                trapped += rightMax -
        height[right];
            }
            right--;
        }
    }

    return trapped;
}

This code takes an integer array representing the heights of the histogram bars as input, and returns the total amount of trapped water between the bars. The time complexity of this algorithm is O(n), where n is the length of the input array.

INFIX TO POSTFIX CONVERSION

Infix notation is a common way of representing mathematical expressions, where the operators are placed between their operands. For example, the infix notation for the expression (3 + 4) * 5 is 3 + 4 * 5. However, this notation can be ambiguous and hard to evaluate using a computer algorithm.

Postfix notation, also known as Reverse Polish Notation (RPN), is an alternative way of representing mathematical expressions, where the operators come after their operands. For example, the postfix notation for the expression 3 + 4 * 5 is 3 4 5 * +. Postfix notation is unambiguous, and can be easily evaluated using a stack.

The process of converting an infix expression to postfix notation is called infix to postfix conversion. This process involves scanning the infix expression from left to right, and using a stack to keep track of the operators. The rules for converting infix to postfix are as follows:

If the scanned character is an operand, add it to the output.
If the scanned character is an operator, push it onto the stack if the stack is empty, or if the operator has higher precedence than the top operator on the stack. If the operator has lower precedence than the top operator on the stack, pop the operators from the stack and add them to the output, until an operator with lower precedence or an opening parenthesis is encountered. Push the scanned operator onto the stack.
If the scanned character is an opening parenthesis, push it onto the stack.
If the scanned character is a closing parenthesis, pop the operators from the stack and add them to the output, until an opening parenthesis is encountered. Pop and discard the opening parenthesis.
After scanning the entire infix expression, pop any remaining operators from the stack and add them to the output.

Here is an example implementation of the infix to postfix conversion algorithm in Java:


public static String infixToPostfix(String infix) {
    StringBuilder postfix = new StringBuilder();
    Deque<Character> stack = new ArrayDeque<>();

    for (int i = 0; i < infix.length(); i++) {
        char c = infix.charAt(i);

        if (Character.isDigit(c)) {
            postfix.append(c);
        } else if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            while (!stack.isEmpty() &&
        stack.peek() != '(') {
               
        postfix.append(stack.pop());
            }
            if (!stack.isEmpty() &&
        stack.peek() == '(') {
                stack.pop();
            }
        } else {
            while (!stack.isEmpty() &&
        precedence(c) <= precedence(stack.peek())) {
               
        postfix.append(stack.pop());
            }
            stack.push(c);
        }
    }

    while (!stack.isEmpty()) {
        postfix.append(stack.pop());
    }

    return postfix.toString();
}

private static int precedence(char c) {
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return 0;
    }
}

This code takes an infix expression as input, and returns its equivalent postfix expression. The time complexity of this algorithm is O(n), where n is the length of the input expression.

PROBLEMS

Easy

Medium

Hard