CodeWithClarity

 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.   Example 1: Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top();    // return 0 minStack.getMin(); // return -2   Best Solution Idea: Use Two Stacks Maintain two stacks : stack : for all values. ...

 Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.   Example 1: Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0] Example 2: Input: temperatures = [30,40,50,60] Output: [1,1,1,0] Example 3: Input: temperatures = [30,60,90] Output: [1,1,0]   BruteForce :  class Solution {     public int [] dailyTemperatures ( int [] temperatures ) {                 int n = temperatures . length ;         int []   result = new int [n];         for ( int i = 0 ;i<n- 1 ;i++)         {             int count = 0 ;             for ( int j =i+ 1 ;j...

 You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input represents a valid arithmetic expression in a reverse polish notation. The answer and all the intermediate calculations can be represented in a 32-bit integer.   Example 1: Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: tokens = ["10","6","9","3","+...

 Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.   Example 1: Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2;  The number 2 can't find next greater number.  The second 1's next greater number needs to search circularly, which is also 2. Example 2: Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]   import java.util.*; class Solution {     public int [] nextGreaterElements ( int [] nums ) {         int n = nums . length ;         int [] result = new int [n];         Arrays . fill (result, - 1 ); // default to -1 ...

 Given an array arr[] of integers, for each element in the array, find the nearest smaller element on its left. If there is no such smaller element, return -1 for that position. Input: arr[] = [1, 6, 2] Output: [-1, 1, 1] Explaination:  There is no number to the left of 1, so we return -1.  After that, the number is 6, and the nearest smaller number on its left is 1.  Next, the number is 2, and the nearest smaller number on the left is also 1. Input: arr[] = [1, 5, 0, 3, 4, 5] Output: [-1, 1, -1, 0, 3, 4] Explaination:  There is no number to the left of 1,  so we return -1.  After that, the number is 5,  and the nearest smaller number on its left is 1.   Next, the number is 0, and there is no smaller number on the left, so we return -1. Then comes 3, and the nearest smaller number on its left is 0. After that, the number is 4, and the nearest smaller number on the left is 3.  Finally, the number is 5, and the nearest smaller number ...

 ven an array, print the Next Smaller Element (NSE) for every element. The NSE for an element x is the first smaller element on the right side of x in the array. For elements for which no smaller element exists (on the right side), then consider NSE as -1.  Examples: Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1] Explanation:  The first element smaller than 4 having index > 0 is 2. The first element smaller than 8 having index > 1 is 5. The first element smaller than 5 having index > 2 is 2. There are no elements smaller than 4 having index > 3. There are no elements smaller than 4 having index > 4. Input: [13, 7, 6, 12] Output: [7, 6, -1, -1] Explanation:  The first element smaller than 13 having index > 0 is 7. The first element smaller than 7 having index > 1 is 6. There are no elements smaller than 6 having index > 2. There are no elements smaller than 12 having index > 3.  [Expected Approach] using Stack - O(n) Time O(n) Space ...

 Given an array arr[ ] of integers, the task is to find the next greater element for each element of the array in order of their appearance in the array. Next greater element of an element in the array is the nearest element on the right which is greater than the current element. If there does not exist next greater of current element, then next greater element for current element is -1. For example, next greater of the last element is always -1. Examples Input: arr[] = [1, 3, 2, 4] Output: [3, 4, 4, -1] Explanation: The next larger element to 1 is 3, 3 is 4, 2 is 4 and for 4, since it doesn't exist, it is -1. Input: arr[] = [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1] Explanation: The next larger element to 6 is 8, for 8 there is no larger elements hence it is -1, for 0 it is 1 , for 1 it is 3 and then for 3 there is no larger element on right and hence -1. Input: arr[] = [10, 20, 30, 50] Output: [20, 30, 50, -1] Explanation: For a sorted array, the next element is next greater eleme...

 Given a string str, the task is to find the bracket numbers, i.e., for each bracket in str, return i if the bracket is the ith opening or closing bracket to appear in the string.   Examples: Input:  str = "(aa(bdc))p(dee)" Output: 1 2 2 1 3 3 Explanation: The highlighted brackets in the given string (aa(bdc))p(dee) are assigned the numbers as: 1 2 2 1 3 3. Input:  str = "(((()(" Output: 1 2 3 4 4 5 Explanation: The highlighted brackets in the given string (((()( are assigned the numbers as: 1 2 3 4 4 5 Expected Time Complexity: O(|str|) Expected Auxiliary Space: O(|str|) import java . util .*; public class BracketNumbersStack {     public static void main ( String [] args ) {         String str = "(aa(bdc))p(dee)" ;         List < Integer > result = getBracketNumbers ( str );         for ( int num : result ) {             System . out . print...

 Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. Note that after backspacing an empty text, the text will continue empty.   Example 1: Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac". Example 2: Input: s = "ab##", t = "c#d#" Output: true Explanation: Both s and t become "". Example 3: Input: s = "a#c", t = "b" Output: false Explanation: s becomes "c" while t becomes "b".   Constraints: 1 <= s.length, t.length <= 200 s and t only contain lowercase letters and '#' characters.   Follow up: Can you solve it in O(n) time and O(1) space? class Solution {     public boolean backspaceCompare ( String s , String t ) {         return build (s). equals ( build (t));     }     public static   String build ( String str )     {         Stack < Char...

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.   Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false Example 4: Input: s = "([])" Output: true   Stack-Based Logic: Traverse each character in the string. If it's an opening bracket ( '(' , '{' , '[' ), push it onto the stack. If it's a closing bracket ( ')' , '}' , ']' ): If the stack is empty , return false (nothing to match). If the top of the stack is the corresponding opening bracket , pop it. Otherwise, return false . ...

 A parentheses string is valid if and only if: It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid.   Example 1: Input: s = "())" Output: 1 Example 2: Input: s = "(((" Output: 3  Logic in Words: If the character is '(' , push it. If the character is ')' , then: If the stack is empty , that means there's no '(' to match → count++ (you need to insert an '(' ). If the top is '(' , pop it (they match). Otherwise (top is also ')' ), it’s unmatched → count++ . class Solution { ...

 Tom is a string freak. He has got sequences of words arr[] to manipulate. If in a sequence, two same words come together then Tom destroys each other. Find the number of words left in the sequence after this pairwise destruction.  Examples: Input: arr[] = ["ab", "aa", "aa", "bcd", "ab"] Output: 3 Explanation: After the first iteration, we'll have: ab bcd ab. We can't further destroy more strings and hence we stop and the result is 3.  Input: arr[] = ["tom", "jerry", "jerry", "tom"] Output: 0 Explanation: After the first iteration, we'll have: tom tom. After the second iteration: 'empty-array' .Hence, the result is 0. Expected Time Complexity: O(n) Expected Auxiliary Space: O(n) static int removeConsecutiveSame ( String [] arr) {     Stack < String > st = new Stack <>();     for ( int i = 0 ; i < arr . length ; i++) {         if ( st . empty ()) {        ...

 Given an array of negative and non-negative integers. You have to make the array beautiful. An array is beautiful if two adjacent integers, arr[i] and arr[i+1] are either negative or non-negative. And you can do the following operation any number of times until the array becomes beautiful. If two adjacent integers are different i.e. one of them is negative and other is non-negative, remove them. Return the beautiful array after performing the above operation. Note:An empty array is also a beautiful array. There can be many adjacent integers which are different as stated above. So remove different adjacent integers as described above from left to right. Example 1: Input: 4 2 -2 1 Output: 4 1 Explanation: As at indices 1 and 2 , 2 and -2 have different sign, they are removed. And the  the final array is: 4 1. Example 2: Input: 2 -2 1 -1 Output: [] Explanation: As at indices 0 and 1, 2 and -2 have different sign, so they are removed. Now the array is 1 -1.Now 1 and -1 are also r...

 You are given a stack st of n integers and an element x. You have to insert x at the bottom of the given stack.  Note: Everywhere in this problem, the bottommost element of the stack is shown first while priniting the stack. Example 1: Input: n = 5 x = 2 st = {4,3,2,1,8} Output: {2,4,3,2,1,8} Explanation: After insertion of 2, the final stack will be {2,4,3,2,1,8}. Example 2: Input: n = 3 x = 4 st = {5,3,1} Output: {4,5,3,1} Explanation: After insertion of 4, the final stack will be {4,5,3,1}. Your Task: You don't need to read input or print anything. Your task is to complete the function insertAtBottom() which takes a stack st and an integer x as inputs and returns the modified stack after insertion. Expected Time Complexity: O(n) Expected Auxiliary Space: O(n)   public Stack <Integer> insertAtBottom ( Stack <Integer> st, int x) {                         Stack < Integer > temp = new Stack ...

 Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.   Example 1: Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2: Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] class Solution {     public void reverseString ( char [] s ) {                   Stack < Character > st = new Stack <>();           for ( char c : s)          {             st . push (c);          }           int i = 0 ;           while (! st . empty ())          {             s[i++]= st . pop ();          }     } }

 Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. LeetCode:- import java.util.*; class Solution {     public String minWindow ( String s , String t ) {         if ( s . length () < t . length ()) return "" ;         Map < Character , Integer > need = new HashMap <>();         Map < Character , Integer > window = new HashMap <>();         // Count charac...