Stack and Queue

class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); char ch [] = s.toCharArray(); for(char i : ch){ if(stack.size()==0) { stack.push(i); System.out.println("push happened "+stack.peek()); } else if(stack.peek()=='(' && i==')' || stack.peek()=='{' && i=='}' || stack.peek()=='[' && i ==']') { System.out.println("here"); stack.pop(); } else stack.push(i); } if(stack.size()==0) return true; else return false; } } 

//recusive : TLE class Solution { public boolean checkValidString(String s) { return possible(0,s,0); } public boolean possible(int index, String s, int count){ //base case if(count<0) return false; if(index == s.length()) return count ==0; char c = s.charAt(index); if(c =='('){ return possible(index+1,s,count+1); } else if(c ==')'){ return possible(index+1,s,count-1); } else{ return possible(index+1,s,count+1) || possible(index+1,s,count) || possible(index+1,s,count-1); } } } ////////////////////dp memorization:////////////// //note: in valid parathesis if only one type of brackets are involved like ( and ) or [ and ] or { and } the use count variable instead of using stack //this will save space, just increment count if character is ( and decrement count if the character is ), //one edge case is if at any point count < 0 then it is not a valid string //example : ()) => count -1, ()())( => at index 4 count will become -1, return false here only else count will be come 0 again at the last index which is still not valid //keep the above edge case in mind class Solution { public boolean checkValidString(String s) { int dp[][] = new int[s.length()][s.length()+1]; for(int d[] : dp) Arrays.fill(d,-1); return possible(0,s,0,dp); } public boolean possible(int index, String s, int count,int dp[][]){ //base case if(count<0) return false; if(index == s.length()) return count ==0; if(dp[index][count]!=-1) return dp[index][count]==1; char c = s.charAt(index); boolean result = false; if(c =='('){//increment count result = possible(index+1,s,count+1,dp); } else if(c ==')'){// decrement count result = possible(index+1,s,count-1,dp); } else{// it is * > assume it to be ( or assume it to be '' or assume it to be ) result = possible(index+1,s,count+1,dp) || possible(index+1,s,count,dp) || possible(index+1,s,count-1,dp); } dp[index][count] = result ? 1:0; return result; } } 

class Solution { //this problem can easily be converted into the longest consecutive 1's in the array, we just have to mark indexes of valid pairs () as 1 //Example: ((()) = [0,1,1,1,1], or (() = [0,1,1] //then simply count the number of consecutive ones public int longestValidParentheses(String s) { int arr[] = new int[s.length()]; Stack<Pair<Character,Integer>> stack = new Stack();// < Character,Integer> to keep track of index of character being pushed in the stack for(int i = 0;i<s.length();i++){ char c = s.charAt(i); if(c =='(') stack.push(new Pair(c,i)); else if(c ==')' && !stack.isEmpty() && stack.peek().getKey() =='('){ // if valid pair found , just mark their indexes as 1 Pair<Character,Integer> p = stack.pop(); arr[i]=1;// '')' index i.e current index marked as 1 arr[p.getValue()] = 1;// corresponding index of closing parathesis '(' marked as 1 } else stack.push(new Pair(c,i)); } int max = 0; int currentMax = 0; //finally count the number of 1's in the array for(int i =0;i<s.length();i++){ if(arr[i] ==0){ currentMax = 0; } else currentMax++; max = Integer.max(max,currentMax); } return max; } } 

class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { HashMap<Integer,Integer> map = new HashMap<>(); Stack<Integer> stack = new Stack<>(); //we will get next greater element of all the element in the nums2, // by that we will easily be able to get the next greater element of all the  //elements in nums1; for(int i = 0;i<nums2.length;i++){ if(stack.isEmpty() || stack.peek() > nums2[i]){ stack.push(nums2[i]); } else{ // below while condition means that we have found // greater value than stack top, now we will have to keep on removing  //stack top to make sure that we have got next greater value of stack top while(!stack.isEmpty() && nums2[i] > stack.peek()){ map.put(stack.pop(),nums2[i]); } stack.push(nums2[i]); } } //now we have got the next greater value of all the elements in the nums2 //we can easily get the next greater value of nums1 int result[] = new int[nums1.length]; for(int i =0;i<result.length;i++){ result[i]= map.getOrDefault(nums1[i],-1);// if next greater does not return then default value will be -1 } return result; } } 

// we can easily do it with two queue, // we will do it with one queue class MyStack { Queue<Integer> q ; public MyStack() { q = new LinkedList<>(); } public void push(int x) { q.add(x); if(q.size()>1){ int size = q.size(); int index =0; while(index!=size-1){//just re-push size-1 value again it will insure that the value  // that needs to be poped is at head; q.add(q.remove()); index++; } } } public int pop() { return q.remove(); } public int top() { return q.peek(); } public boolean empty() { return q.isEmpty(); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */ 

import java.util.*; public class Solution { public static void sortStack(Stack<Integer> stack) { // Write your code here.  Stack<Integer> stack2 = new Stack<>(); while(!stack.isEmpty()) { int top = stack.pop(); while(!stack2.isEmpty() && stack2.peek() < top){ stack.push(stack2.pop()); } stack2.push(top); } while(!stack2.isEmpty()) stack.push(stack2.pop()); } }