stscat

// array input
import java.util.*;

public class ArrayInputExample {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the array elements (space-separated): ");
        String input = scanner.nextLine();

        // Split the input string by space and convert it into an array of integers
        String[] numStrings = input.split(" ");
        int[] arr = new int[numStrings.length];
        for (int i = 0; i < numStrings.length; i++) {
            arr[i] = Integer.parseInt(numStrings[i]);
        }

        // Print the array elements
        System.out.print("Array elements: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        scanner.close();
    }
}


// stack permutation
public class Main {
  public static boolean isStackPermutation(int[] original, int[] target) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    for (int element : original) {
      stack.push(element);
      while (!stack.isEmpty() && stack.peek() == target[i]) {
        stack.pop();
        i++;
      }
    }
    return stack.isEmpty();
  }
  public static void main(String[] args) {
    int[] original = {1, 2, 3};
    int[] target = {2, 1, 3};
    boolean result = isStackPermutation(original, target);
 System.out.println("Is it a 
stack permutation? " + result);
  }
}


// celebrity problem
import java.io.*;
import java.util.*;
public class Main {
  public int[] calculateSpan(int[] stockPrices) {
    int n = stockPrices.length;
    int[] span = new int[n];
    span[0] = 1; // The span of the first
    day is always 1. for (int i = 1; i < n; i++) {
      span[i] = 1; // Initialize the
span for the current day.
 int j = i - 1;
while (j >= 0 && stockPrices[i] >= stockPrices[j]) {
  span[i]++;
  j--;
}
    }
    return span;
  }
  public static void main(String[] args) {
    Main calculator = new Main();
    int[] stockPrices = {100, 80, 60, 70, 60, 75, 85};
    int[] spans = calculator.calculateSpan(stockPrices);
    System.out.println("Stock Prices: " + Arrays.toString(stockPrices));
    System.out.println("Stock Spans: " + Arrays.toString(spans));
  }
}


// segeregate evn odd ll
class Node {
  int data;
  Node next;
  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}
class LinkedList {
  Node head;
  public void append(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = newNode;
  }
  public void segregateEvenOdd() {
    if (head == null) {
 System.out.println("The list is empty.");
 return;
    }
    Node evenHead = null, evenTail = null;
    Node oddHead = null, oddTail = null;
    Node current = head;
    while (current != null) {
      int data = current.data;
      if (data % 2 == 0) { // even node
        if (evenHead == null) {
          evenHead = evenTail = current;
        } else {
          evenTail.next = current;
          evenTail = current;
        }
      } else { // odd node
        if (oddHead == null) {
          oddHead = oddTail = current;
        } else {
          oddTail.next = current;
          oddTail = current;
        }
      }
      current = current.next;
    }
    // Join even and odd lists
    if (evenHead != null) {
      evenTail.next = oddHead;
    }
    if (oddHead != null) {
      oddTail.next = null;
    }
    head = evenHead != null ? evenHead : oddHead;
  }
  public void printList() {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
    System.out.println();
  }
}
public class Main {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.append(5);
    System.out.println("Original list:");
    list.printList();
    list.segregateEvenOdd();
    System.out.println("Segregated list (even before odd):");
    list.printList();
  }
}


// merge sort using dll
import java.util.*;
class Main {
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[][] relationshipMatrix = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        relationshipMatrix[i][j] = sc.nextInt();
      }
    }
    int celebrityId = new Solution().findCelebrity(relationshipMatrix, N);
    if (celebrityId != -1) {
      System.out.println("Celebrity id: " + celebrityId);
    } else {
 System.out.println("No 
Celebrity");
    }
  }
}
class Solution {
  int findCelebrity(int M[][], int n) {
    int candidate = 0;
    for (int i = 1; i < n; i++) {
      if (M[candidate][i] == 1) {
        candidate = i;
      }
    }
    for (int i = 0; i < n; i++) {
      if (i != candidate && (M[candidate][i] == 1 || M[i][candidate] == 0)) {
        return -1;
      }
    }
    return candidate;
  }
}


// iterative toh
public class Main {
  public static void main(String[] args) {
    int n = 3; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B');
  }
  public static void towerOfHanoi(
      int n, char source, char destination, char auxiliary) {
    if (n == 1) {
      System.out.println("Move disk 1 from " + source + " to " + destination);
      return;
    }
    towerOfHanoi(n - 1, source, auxiliary, destination);
    System.out.println(
        "Move disk " + n + " from " + source + " to " + destination);
    towerOfHanoi(n - 1, auxiliary, destination, source);
  }
}


// stock span
import java.util.Arrays;
import java.util.Stack;
class MinStack {
  private Stack<Integer> stack;
  private Stack<Integer> minStack;
  public MinStack() {
    stack = new Stack<>();
    minStack = new Stack<>();
  }
  public void push(int val) {
    stack.push(val);
    if (minStack.isEmpty() || val <= minStack.peek()) {
      // or opreration for check any one is true
      minStack.push(val);
    }
  }
  public void pop() {
    if (!stack.isEmpty()) {
      if (stack.peek().equals(minStack.peek())) {
        minStack.pop();
      }
      stack.pop();
    }
  }
  public int top() {
    return stack.peek();
  }
  public int getMin() {
    return minStack.peek();
  }
}
public class Main {
  public static void main(String[] args) {
    MinStack minStack = new MinStack();
    minStack.push(2);
    minStack.push(3);
    minStack.pop();
    minStack.push(4);
    minStack.push(-1);
    minStack.top();
    minStack.push(6);
    minStack.getMin();
    minStack.pop();
    minStack.getMin();
    System.out.println("Current Min: " + minStack.getMin());
  }
}


// sort bitonic dll
class Main {
  // 1.node explanation
  static class Node {
    int data;
    Node next;
    Node prev;
  }
  // 2.reverse function
  // input 1,2,3---3,2,1
  static Node reverse(Node head_ref) {
    Node temp = null;
    Node current = head_ref;
    while (current != null) {
      temp = current.prev;
      current.prev = current.next;
      current.next = temp;
      current = current.prev;
    }
    if (temp != null)
      head_ref = temp.prev;
    return head_ref;
  }
  // 3.Merge operation
  // list 1---2,5,8
  // list 2---1,3,6
  static Node merge(Node first, Node second) {
    if (first == null)
      return second;
    if (second == null)
      return first;
    if (first.data < second.data) {
      first.next = merge(first.next, second);
      if (first.next != null)
        first.next.prev = first;
      first.prev = null;
      return first;
    } else {
      second.next = merge(first, second.next);
      if (second.next != null)
        second.next.prev = second;
      second.prev = null;
      return second;
    }
  }
  // 4.sorted list----call reverse and merge
  function static Node sort(Node head) {
    if (head == null || head.next == null)
      return head;
    Node current = head.next;
    while (current != null) {
      if (current.data < current.prev.data)
        break;
      current = current.next;
    }
    if (current == null)
      return head;
    current.prev.next = null;
    current.prev = null;
    current = reverse(current);
    return merge(head, current);
  }
  // 5.push
  static Node push(Node head_ref, int new_data) {
    Node new_node = new Node();
    new_node.data = new_data;
    new_node.prev = null;
    new_node.next = (head_ref);
    if ((head_ref) != null)
      (head_ref).prev = new_node;
    (head_ref) = new_node;
    return head_ref;
  }
  // 6.print the list
  static void printList(Node head) {
    if (head == null)
 System.out.println("Doubly Linked 
list empty");
 while (head != null) {
        System.out.print(head.data + " ");
        head = head.next;
 }
  }
  // 7.Main function
  public static void main(String args[]) {
    Node head = null;
    // Create the doubly linked list:
    head = push(head, 1);
    head = push(head, 4);

    head = push(head, 6);
    head = push(head, 10);
    head = push(head, 12);
    head = push(head, 7);
    head = push(head, 5);
    head = push(head, 2);
    System.out.println("Original List:");
    printList(head);
    head = sort(head);
    System.out.println("\nSorted List:");
    printList(head);
  }
}

// loop detection
public class LinkedList {
  // 1.Node structure
  static class Node {
    int data;
    Node next;
    Node(int d) {
      data = d;
      next = null;
    }
  }
  // 2.push operation
  Node head;
  void push(int newData) {
    Node newNode = new Node(newData);
    newNode.next = head;
    head = newNode;
  }
  // 3.detect loop
  void detectLoopAndPrint() {
    Node slow = head, fast = head;
    while (slow != null && fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
 System.out.println("Loop 
found");
 return;
      }
    }
 System.out.println("Loop not 
found");
  }
  // 4.main method
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.push(20);
    list.push(41);
    list.push(5);
    list.push(10);
    // 5.Creating a loop for testing
    list.head.next.next.next.next = list.head;
    list.detectLoopAndPrint();
  }
}

// max sliding window
public class Main {
  public static int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0)
      return new int[0];
    int n = nums.length;
    int[] result = new int[n - k + 1];
    for (int i = 0; i <= n - k; i++) {
      int max = Integer.MIN_VALUE;
      for (int j = i; j < i + k; j++) {
        max = Math.max(max, nums[j]);
      }
      result[i] = max;
    }
    return result;
  }
  public static void main(String[] args) {
    int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    int[] result = maxSlidingWindow(nums, k);
    for (int num : result) {
      System.out.print(num + " ");
    }
  }
}

// sort without extra space

import java.util.LinkedList;
import java.util.Queue;
public class SortingAQueueWithoutExtraSpace {
  private static void sortQueue(Queue<Integer> queue) {
    int n = queue.size();
    for (int i = 0; i < n; i++) {
      // Find the index of smallest element from
      the unsorted queue int minIndex = -1;
      int minValue = Integer.MAX_VALUE;
      for (int j = 0; j < n; j++) {
        int currValue = queue.poll();
        // Find the minimum value index only
        from unsorted queue if (currValue < minValue && j < (n - i)) {
          minValue = currValue;
          minIndex = j;
        }
        queue.add(currValue);
      }
      // Remove min value from queue
      for (int j = 0; j < n; j++) {
        int currValue = queue.poll();
        if (j != minIndex) {
          queue.add(currValue);
        }
      }
      // Add min value to the end of the queue
      queue.add(minValue);
    }
    // Print the sorted queue
    for (Integer i : queue) {
      System.out.print(i + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    Queue<Integer> q1 = new LinkedList<>();
    q1.add(10);
    q1.add(7);
    q1.add(2);
    q1.add(8);
    q1.add(6);
    sortQueue(q1);
  }
}

// priority queue using dll
class PriorityQueueNode<T> {
  T data;
  int priority;
  PriorityQueueNode<T> prev;
  PriorityQueueNode<T> next;
  public PriorityQueueNode(T data, int priority) {
    this.data = data;
    this.priority = priority;
  }
}
class PriorityQueue<T> {
  private PriorityQueueNode<T> head;
  private PriorityQueueNode<T> tail;
  public PriorityQueue() {
    head = null;
    tail = null;
  }
  public void insert(T data, int priority) {
    PriorityQueueNode<T> newNode = new PriorityQueueNode<>(data, priority);
    if (head == null) {
      head = newNode;
      tail = newNode;
    } else if (priority < head.priority) {
      newNode.next = head;
      head.prev = newNode;
      head = newNode;
    } else {
      PriorityQueueNode<T> current = head;
      while (current.next != null && current.next.priority <= priority) {
        current = current.next;
      }
      newNode.prev = current;
      newNode.next = current.next;
      if (current.next != null) {
        current.next.prev = newNode;
      } else {
        tail = newNode;
      }
      current.next = newNode;
    }
  }
  public T delete() {
    if (head == null) {
      return null;
    }
    T data = head.data;
    head = head.next;
    if (head != null) {
      head.prev = null;
    } else {
      tail = null;
    }
    return data;
  }
  public T peek() {
    if (head == null) {
      return null;
    }
    return head.data;
  }
  public boolean isEmpty() {
    return head == null;
  }
  // Other utility methods can be added asneeded.
}
public class Main {
  public static void main(String[] args) {
    PriorityQueue<String> priorityQueue = new PriorityQueue<>();

    priorityQueue.insert("Task A", 3);
    priorityQueue.insert("Task B", 1);
    priorityQueue.insert("Task C", 2);
    System.out.println("Highest-priority task: " + priorityQueue.peek());
    while (!priorityQueue.isEmpty()) {
      System.out.println("Executing: " + priorityQueue.delete());
    }
  }
}