public int[] twoSum(int[] nums, int target) {
  for(int i=0; i<nums.length-1; i++) {
      for(int j=i+1; j<nums.length; j++) {
          if(nums[i] + nums[j] == target) {
              return new int[]{i, j};
          }
      }
  }
  return new int[]{};
}

def twoSum(self, nums, target):
  for i in range(len(nums)-1):
      for j in range(i+1, len(nums)):
          if nums[i] + nums[j] == target:
              return [i, j]
  return []

var twoSum = function(nums, target) {
    for(let i=0; i<nums.length-1; i++) {
        for(let j=i+1; j<nums.length; j++) {
            if(nums[i] + nums[j] == target) {
                    return [i, j];
            }
        }
    }
    return []
};

// Checking input is palindrome or not 
// Example: 121 is palindrome number

function isPalindrome(num) {
  const original = num;
  let reminder = 0;
  while(num != 0) {
    let lastDig = num % 10;
    reminder = (reminder * 10) + lastDig;
    num = Math.floor(num / 10);
  }
  return original === reminder;
};

const userInput = parseInt(prompt("Enter a number: "));

if(isPalindrome(userInput)) {
  console.log(`${userInput} is Palindrome.`);
} else {
  console.log(`${userInput} is not Palindrome.`)
}

// Problem: Next Greater Element.
// >> The next greater element of some element X in an array is first greater element that is to the right of X in the same array.

// Sample input:
//  -> arr = [4, 7, 3, 2, 9, 0, 1]
// Output:
//  -> next Greater = [7, 9, 9, 9, -1, 1, -1]

import java.util.*;
class Main {
    public static void main(String[] args) {
        int arr[] = {4, 7, 3, 2, 9, 0, 1};
        int nextGreater[] = new int[arr.length];
        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()) {
                nextGreater[i] = -1;
            } else {
                nextGreater[i] = arr[s.peek()];
            }

            s.push(i);
        }

        // print result
        for(int j=0; j<arr.length; j++) {
            System.out.print(nextGreater[j] + " ");
        }
        System.out.println();
    }
}

// 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));
    }
}