Tuesday, September 30, 2025

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");

}

Monday, September 29, 2025

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

Friday, September 26, 2025

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(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.

Wednesday, September 24, 2025

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]+" ");

}

Tuesday, September 23, 2025

Reverse a Stack (Revision)

import java.util.Stack;

class StackB {

static public void pushAtBottom(Stack<Integer> s, int data) {

if(s.isEmpty()) {

s.push(data);

return;

}

int top = s.pop();

pushAtBottom(s, data);

s.push(top);

}

public static void reverseStack(Stack<Integer> s) {

if(s.isEmpty()) {

return;

}

int top = s.pop(); // remove each element from top

reverseStack(s);

pushAtBottom(s, top);

}

public static void main(String[] args) {

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

s.push(1);

s.push(2);

s.push(3);

System.out.println(s);

reverseStack(s);

System.out.println(s);

}

Friday, September 19, 2025

Reverse a string using Stack

import java.util.*;

// Push element at the bottom of stack

class StackB {

public static String reverseString(String str) {

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

int idx = 0;

while(idx < str.length()) {

s.push(str.charAt(idx));

idx++;

}

StringBuilder result = new StringBuilder("");

while(!s.isEmpty()) {

char curr = s.pop();

result.append(curr); // append adds to the last

}

return result.toString();

}

public static void main(String[] args) {

String str = "abc";

String result = reverseString(str);

System.out.println(result);

}

Push element at the bottom of the Stack

import java.util.*;

// Push element at the bottom of stack

class StackB {

public static void pushAtBottom(Stack<Integer> s, int data) {

if (s.isEmpty()) { // ✅ base case

s.push(data);

return;

}

int top = s.pop(); // store top

pushAtBottom(s, data); // recurse until empty

s.push(top); // push top back

}

public static void main(String[] args) {

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

s.push(1);

s.push(2);

s.push(3);

pushAtBottom(s, 4); // insert at bottom

while(!s.isEmpty()) {

System.out.println(s.pop()); // we do popping To demonstrate the result of inserting at the bottom.

}

Java Collection Framework - Stack in Java

import java.util.*;

// Java Collection Framework of Stack

class StackB {

public static void main(String[] args) {

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

s.push(1);

s.push(2);

s.push(3);

System.out.println(s); // Before pop

while(!s.isEmpty()) {

System.out.println(s.peek());

s.pop();

}

System.out.println(s); // After pop

}

Thursday, September 18, 2025

Stack using LinkedList

import java.util.ArrayList;

// LL implementation of stack

public class StackB {

static class Node {

int data;

Node next;

Node(int data) {

this.data = data;

this.next = null;

}

static class Stack {

static Node head = null;

public static boolean isEmpty() {

return head == null;

}

// push - add elements on top - O(1)

public static void push(int data) {

Node newNode = new Node(data);

if(isEmpty()) {

head = newNode;

return;

}

newNode.next = head;

head = newNode;

}

// pop - delete from top - O(1)

public static int pop(){

if(isEmpty()) {

return -1;

}

int top = head.data;

head = head.next;

return top;

}

// peek - view the element from the top - O(1)

public static int peek() {

if(isEmpty()) {

return -1;

}

return head.data;

}

public static void main(String[] args) {

Stack s = new Stack();

s.push(1);

s.push(2);

s.push(3);

while(!s.isEmpty()) {

System.out.println(s.peek());

s.pop();

}

Stack - Operations (Push, pop and peek) using ArrayList

import java.util.ArrayList;

public class StackB {

static class Stack {

static ArrayList<Integer> list = new ArrayList<>();

public static boolean isEmpty() {

return list.size() == 0; // no elements in the stack (my Mistake: without list.size() it wont work, i wrote "list.size" only which let to private access errors)

}

// push - add the data in the stack

public static void push(int data) {

list.add(data);

}

// pop - delete the data from stack

public static int pop() {

int top = list.get(list.size()-1); // gets the last index

list.remove(list.size()-1); // removes it

return top;

}

// peek - view the data from top

public static int peek() {

return list.get(list.size()-1);

}

public static void main(String[] args) {

Stack s = new Stack();

s.push(1);

s.push(2);

s.push(3);

while(!s.isEmpty()) {

System.out.println(s.peek());

s.pop();

}

Leetcode 23. Merge K-sorted lists

class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;

        }

        if(l2 == null) {
            return l1;
        }

        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }

    public ListNode partitionAndMerge(int si, int ei, ListNode[] lists) {
        // 1. base case
        if(si > ei) {
            return null;
        }
        
        if(si == ei) {
            return lists[si];
        }

        int mid = si+(ei-si)/2;
        // break and merge
        ListNode l1 = partitionAndMerge(si, mid, lists);
        ListNode l2 = partitionAndMerge(mid+1, ei, lists);
        
        return mergeTwoLists(l1, l2);

    }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }

        int k = lists.length;


        return partitionAndMerge(0, k-1, lists);
        
    }
}

OUTPUT:
All test cases were true.

Leetcode 21. Merge two lists using Linked list in Java (with mistakes noted)

MY MISTAKE:
if(list1 == null) {

return list1; // ❌ This should return list2, not list1

}

if(list2 == null) {

return list2; // ❌ This should return list1, not list2

}

👉 Reason:

If list1 is null, that means no nodes are left in list1, so you should just return the other list (list2).
Similarly, if list2 is null, you should return list1.

CODE:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }

        if(list2 == null) {
            return list1;
        }

        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

Monday, September 15, 2025

Leetcode 1721. Swapping Nodes in a Linked List

/**

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {    
        // Step 1: Find length of the list 
        ListNode curr = head;
        int n = 0;
        while(curr != null) {
            n++;
            curr = curr.next;
        }

        // Step 2: Find kth node from the start and kth node from the end
        ListNode first = head;
    
        for(int i=1; i<k; i++) {
            first = first.next;
        }

        ListNode second = head;
        for(int j=1; j<n-k+1; j++) {
            second = second.next;
        }

        int temp = first.val;
        first.val = second.val;
        second.val = temp;
        
        return head;
    }
}

Sunday, September 14, 2025