Palindrome Linked List using Stacks

 import java.util.Stack;

public class Main {

    // singly linked list

    static class Node {

        char data;

        Node next;

        Node(char data) {

            this.data = data;

            this.next = null;

        }

    } 

        

        // palindrome checker using Stack

        public static boolean isPalindrome(Node head) { 

            Stack<Character> stack = new Stack<>();

            Node temp = head;

            

            

            // Push elements to the stack

            while(temp != null){

                stack.push(temp.data);

                temp = temp.next;

            }

            

            // Pop while comparing

            temp = head;

            while(temp != null){

                if(temp.data != stack.pop()) { // if not matched

                    return false;

                }

                

                temp = temp.next;

            }

            return true; // all matched

        }  

        

        

        

    

    public static void main(String[] args) {

        Node head = new Node('A');

        head.next = new Node('B');

        head.next.next = new Node('C');

        head.next.next.next = new Node('B');

        head.next.next.next.next = new Node('A');

        

        if(isPalindrome(head)) {

            System.out.println("yes, it is a palindrome");

        } else {

            System.out.println("not a palindrome");

        }

        

    }

}

Max Area in a Histogram using Stack

import java.util.*;

class maxArea  {

    public static void maxArea(int arr[]) { //O(n) - TC (most optimized code)

        int maxArea = 0;

        int nsr[] = new int[arr.length];

        int nsl[] = new int[arr.length];

       

        // Next Smaller Right

        Stack<Integer> s = new Stack<>();

        // modified nextGreater code for NSR

        for(int i=arr.length-1; i>=0; i--) { // O(n)

            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) { // just change from <= to >= to find nextSmaller right

                s.pop();

            }

            if(s.isEmpty()) {

                //-1

                nsr[i] = arr.length;

               

            } else {

                //top

                nsr[i] = s.peek();

               

            }

            s.push(i);

        }

        // Next Smaller Left

        s = new Stack<>();

        for(int i=0; i<arr.length; i++) { // O(n)

            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) { // just change from <= to >= to find nextSmaller right

                s.pop();

            }

            if(s.isEmpty()) {

                //-1

                nsl[i] = -1;

               

            } else {

                //top

                nsl[i] = s.peek();

               

            }

            s.push(i);

        }

        // Current Area : width = j-i-1 = nsr[i]-nsl[i]-1 // O(n)

        for(int i=0; i<arr.length; i++) {

            int height = arr[i];

            int width = nsr[i] - nsl[i] - 1;

            int currArea = height * width;

            maxArea = Math.max(currArea, maxArea);

        }

        System.out.println("Max area in a histogram is: " + maxArea);

    }

    public static void main(String[] args) {

        int arr[] = {2, 1, 5, 6, 2, 3}; // heights in histogram

        maxArea(arr);

    }

} OUTPUT: Max area in a histogram is: 10

Question 1 :Monotonic ArrayList(EASY) - Java

 import java.util.*;

public class Main

{

    public static boolean checkMonotic(ArrayList<Integer> nums, int store) {

        int i = 0;

        int j = nums.size()-1;

        

        while(i <= j) {

            // case 1: increasing order Monotonic

            if(nums.get(i) >= nums.get(j)) {

                return true;

            } 

            

            // case 2: decreasing order Monotonic

            if(nums.get(i) <= nums.get(j)) {

                return true;

            }

        }

        

        return false;

        

        

    }

    

    

public static void main(String[] args) {

    ArrayList<Integer> nums = new ArrayList<>();

     

    // 1, 2, 2, 3 - Monotonic

    nums.add(1);

    nums.add(2);

    nums.add(2);

    nums.add(3);

   

    

    int target = 16;

    

    

    System.out.println(checkMonotic(nums, target));

}

}



CODE:

Duplicate Parentheses - (V.V.imp) asked in Microsoft, Google! Stack question

 

import java.util.*;

public class Duplicate_parentheses {

    public static boolean isDuplicate(String str) {

        Stack<Character> s = new Stack<>();

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

            char ch = str.charAt(i);

           

           

            // closing

            if(ch == ')') {

                int count = 0;

                while(s.pop() != '(') {

                    count++;

                }

               

                if(count < 1) {

                    return true; // duplicate exists

                }

            } else {

                // opening

                s.push(ch);

            }

        }

        return false;

    }

    public static void main(String[] args) {

        String str = "((a+b))"; // true

        String str2 = "(a-b)"; // false

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

        System.out.println(isDuplicate(str2));

    }

   

}

OUTPUT: true false

Valid parentheses - Stack

 import java.util.*;

class Solution {

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for(int i=0; i<s.length(); i++) {

            char ch = s.charAt(i);

            if(ch == '(' || ch == '{' || ch == '[') {

                stack.push(ch);

            } else {

               

                if(stack.isEmpty()) {

                    return false;

                }

                char top = stack.pop();

                if((top == '(' && ch != ')') || (top == '{' && ch != '}') || (top == '[' && ch != ']')) {

                    return false;

                }

            }

        }

        return true;

    }

} OUTPUT: True for all cases.

next Greater element - Stack problem (V.V.imp)

 import java.util.*;

public class Classroom {

    public static void main(String[] args) {

        int arr[] = {6, 8, 0, 1, 3};

        Stack<Integer> s = new Stack<>();

        int nextGreater[] = new int[arr.length];

        

        for(int i = arr.length - 1; i >= 0; i--) {

            // 1 while

            while(!s.isEmpty() && arr[s.peek()] <= arr[i]) {

                s.pop();

            }

            // 2 if-else

            if(s.isEmpty()) {

                nextGreater[i] = -1;

            } else {

                nextGreater[i] = arr[s.peek()];

            }

            // 3 push in s

            s.push(i);

        }

        // Print result

        for(int i = 0; i < nextGreater.length; i++) {

            System.out.println(nextGreater[i] + " ");

        }

        System.out.println();

        

        // nextGreater Right

        // nextGreater Left

        // next Smaller right

        // next Smaller left

    }

}

OUTPUT:

8 

-1 

1 

3 

-1 

Stock-Span problem in Stack-1(java)

 import java.util.*;

public class StackB {

    public static void stockSpan(int stocks[], int span[]) {

        Stack<Integer> s = new Stack<>();

        span[0] = 1;

        s.push(0);

        

        

        for(int i=1; i<stocks.length; i++) {

            int currPrice = stocks[i];

            while(!s.isEmpty() && currPrice > stocks[s.peek()]) {

                s.pop();

            } 

            if(s.isEmpty()) {

                span[i] = i+1;

            } else {

                int prevHigh = s.peek();

                span[i] = i - prevHigh;

            }

            

            s.push(i);

        }

    }

    

    

    

    public static void main(String[] args) {

        int stocks[] = {

            100, 80, 60, 70, 60, 85, 100

        };

        int span[] = new int[stocks.length];

        stockSpan(stocks, span);

        

        for(int i=0; i<span.length; i++) {

            System.out.println(span[i]+" ");

        }

    }

}