// Problem 2: Valid Parantheses
// 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.
// 3. Every close bracket has a corresponding open bracket of the same type.

// Sample input 1:
//  -> str = "({})[]{}"
// Output:
//  -> true

// Sample input 2:
//  -> str = "({)[]{"
// Output:
//  -> false

import java.util.*;
public class Main {
    public static boolean isValid(String str) {
        Stack<Character> s = new Stack<>();

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

            if(ch == '(' || ch == '{' || ch == '[') {
                s.push(ch);
            } else {
                if(s.isEmpty()) {
                    return false;
                } else if((s.peek() == '(' && ch == ')')
                || (s.peek() == '{' && ch == '}')
                || (s.peek() == '[' && ch == ']')) {
                    s.pop();
                } else {
                    return false;
                }
            }
        }
        if(s.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
    public static void main(String[] args) {
        String str = "({})[]";
        String str1 = ")";
        System.out.println(isValid(str));
        System.out.println(isValid(str1));
    }
}

// Problem 3: Duplicate Parentheses
// -> Given a balanced expression, find if it contains duplicate parentheses or not. A set of parentheses are duplicate if the same subexpression is surrounded by multiple parentheses.

// Return a true if it contains duplicates else return false.

// Sample Input 1:
//  -> "(a-b)"
// Output:
//  -> false

// Sample Input 2:
//  -> "((a+b))"
// Output:
//  -> true

import java.util.*;
public class Main {
    public static boolean isDuplicate(String str) {
        Stack<Character> s = new Stack<>();

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

            if(ch == ')') {
                int count = 0;
                while(!s.isEmpty() && s.peek() != '(') {
                    s.pop();
                    count++;
                }

                if(count < 1) {
                    return true;
                } else {
                    s.pop();
                }
            } else {
                s.push(ch);
            }
        }
        return false;
    }
    public static void main(String[] args) {
        String str = "((a+b))";
        String str1 = "(a-b)";

        System.out.println(isDuplicate(str));
        System.out.println(isDuplicate(str1));
    }
}

// Problem 4: Max Area in Histogram
// -> 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.

// Sample Input:
//  -> heights = [2, 1, 5, 6, 2, 3]
// Output:
//  -> 10

import java.util.*;
public class Main {
    public static int maxArea(int[] arr) {
        int maxArea = 0;
        int[] nextRight = new int[arr.length];
        int[] nextLeft = new int[arr.length];

        // next smaller right width
        Stack<Integer> s = new Stack<>();
        for(int i=arr.length-1; i>=0; i--) {
            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) {
                s.pop();
            }
            if(s.isEmpty()) {
                nextRight[i] = arr.length;
            } else {
                nextRight[i] = s.peek();
            }

            s.push(i);
        }

        // next smaller left width
        s = new Stack<>();
        for(int i=0; i<arr.length; i++) {
            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) {
                s.pop();
            }
            if(s.isEmpty()) {
                nextLeft[i] = -1;
            } else {
                nextLeft[i] = s.peek();
            }

            s.push(i);
        }

        // area
        for(int i=0; i<arr.length; i++) {
            int height = arr[i];
            int width = nextRight[i] - nextLeft[i] - 1;
            int area = height * width;

            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 2, 3};
        System.out.println(maxArea(arr));
    }
}