Stack and Queue

1. valid parenthesis string
2. valid parenthesis
3. Longest valid paranthesis
4. Next greater element than stack top
5. Implement stack using single queue (design question)
6. Sort stack in descending order

valid parenthesis

TC: O(N)

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

valid parenthesis string

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

Longest valid paranthesis

Tc : $O(n)$
Tc : $O(n)$

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

---

Next greater element than stack top

TC: in worst case O(n^2), as we will iterate over nums2, and if all the elements are in descending order except the last element in nums2 (example: 7,6,5,4,3,8), then at last index we will go to else part and while loop that will run for n-1 times hence TC will be n*(n-1)

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

Implement stack using single queue (design quetion)

You can easily guess the TC:

// 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();
 */

Sort stack in descending order

TC: o(N)

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