DSA IQ - Level 1 - Part 1

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
}

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return "Stack is empty";
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return "Stack is empty";
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // উপাদানটি পাওয়া গেছে, ইনডেক্স রিটার্ন করো
    } else if (arr[mid] < target) {
      left = mid + 1; // টার্গেট ডানদিকে আছে
    } else {
      right = mid - 1; // টার্গেট বামদিকে আছে
    }
  }

  return -1; // উপাদানটি পাওয়া যায়নি
}

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // সোয়াপ করুন
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  for (let element of arr) {
    if (element < pivot) {
      left.push(element);
    } else if (element > pivot) {
      right.push(element);
    } else {
      equal.push(element);
    }
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

// অবজেক্ট ব্যবহার করে হ্যাশ টেবিল
const hashTable = {};

// কী-ভ্যালু পেয়ার যোগ করা
hashTable["name"] = "John";
hashTable["age"] = 30;
hashTable["city"] = "New York";

// কী দিয়ে ভ্যালু অ্যাকসেস করা
console.log(hashTable["name"]); // "John"

// ম্যাপ ব্যবহার করে হ্যাশ টেবিল
const map = new Map();

// কী-ভ্যালু পেয়ার যোগ করা
map.set("name", "John");
map.set("age", 30);
map.set("city", "New York");

// কী দিয়ে ভ্যালু অ্যাকসেস করা
console.log(map.get("name")); // "John"

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1); // অনিয়মিত গ্রাফের জন্য
  }

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
  }

  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
}

function bfs(graph, startVertex) {
  const visited = {};
  const queue = [startVertex];
  const result = [];
  visited[startVertex] = true;

  while (queue.length) {
    const currentVertex = queue.shift();
    result.push(currentVertex);

    graph.adjacencyList[currentVertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }

  return result;
}

function dfs(graph, startVertex) {
  const result = [];
  const visited = {};

  function traverse(vertex) {
    if (!vertex) return null;
    visited[vertex] = true;
    result.push(vertex);

    graph.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        return traverse(neighbor);
      }
    });
  }

  traverse(startVertex);
  return result;
}

// টপ-ডাউন মেমোইজেশন
function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

// বটম-আপ টাবুলেশন
function fibonacciTabulation(n) {
  if (n <= 1) return n;

  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

function factorial(n) {
  // বেস কেস
  if (n <= 1) {
    return 1;
  }

  // রিকার্সিভ কেস
  return n * factorial(n - 1);
}

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;

  // এটি বাড়তি চেক: যদি 2 বা 3 দ্বারা বিভাজ্য হয়
  if (num % 2 === 0 || num % 3 === 0) return false;

  // 6k±1 পরীক্ষা: সব প্রাইম 6k±1 ফর্ম নেয় (k>0)
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) {
      return false;
    }
  }

  return true;
}

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return undefined; // ডুপ্লিকেট ভ্যালু বাদ দেয়া

      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  find(value) {
    if (!this.root) return false;

    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }

    return found ? current : false;
  }
}

// O(n) টাইম কমপ্লেক্সিটি
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) { // n টাইম
    if (arr[i] === target) return i;     // প্রতিবার 1 তুলনা
  }
  return -1;
}

// O(n²) টাইম কমপ্লেক্সিটি
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {         // n টাইম
    for (let j = 0; j < arr.length - i - 1; j++) { // (n-i) টাইম
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

function isPalindrome(str) {
  // কেস সেনসিটিভিটি এবং নন-আলফানিউমেরিক ক্যারেক্টার রিমুভ
  const cleanStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');

  // 1. টু পয়েন্টার অ্যাপ্রোচ
  let left = 0;
  let right = cleanStr.length - 1;

  while (left < right) {
    if (cleanStr[left] !== cleanStr[right]) {
      return false;
    }
    left++;
    right--;
  }

class MinHeap {
  constructor() {
    this.values = [];
  }

  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChild(index) {
    return (2 * index) + 1;
  }

  rightChild(index) {
    return (2 * index) + 2;
  }

  insert(value) {
    this.values.push(value);
    this.bubbleUp();
    return this;
  }

  bubbleUp() {
    let index = this.values.length - 1;
    const element = this.values[index];

    while (index > 0) {
      let parentIndex = this.parent(index);
      let parent = this.values[parentIndex];

      if (element >= parent) break;

      this.values[parentIndex] = element;
      this.values[index] = parent;
      index = parentIndex;
    }
  }

  extractMin() {
    const min = this.values[0];
    const end = this.values.pop();

    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }

    return min;
  }

  sinkDown() {
    let index = 0;
    const length = this.values.length;
    const element = this.values[0];

    while (true) {
      let leftChildIdx = this.leftChild(index);
      let rightChildIdx = this.rightChild(index);
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild < element) {
          swap = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild < element) || 
          (swap !== null && rightChild < leftChild)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;

      this.values[index] = this.values[swap];
      this.values[swap] = element;
      index = swap;
    }
  }
}

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let current = this.root;

    for (let char of word) {
      if (!current.children[char]) {
        current.children[char] = new TrieNode();
      }
      current = current.children[char];
    }

    current.isEndOfWord = true;
  }

  search(word) {
    let current = this.root;

    for (let char of word) {
      if (!current.children[char]) {
        return false;
      }
      current = current.children[char];
    }

    return current.isEndOfWord;
  }

  startsWith(prefix) {
    let current = this.root;

    for (let char of prefix) {
      if (!current.children[char]) {
        return false;
      }
      current = current.children[char];
    }

    return true;
  }
}

function dijkstra(graph, start) {
  const distances = {};
  const previous = {};
  const nodes = new PriorityQueue();

  // ইনিশিয়ালাইজেশন
  for (let vertex in graph) {
    if (vertex === start) {
      distances[vertex] = 0;
      nodes.enqueue(vertex, 0);
    } else {
      distances[vertex] = Infinity;
      nodes.enqueue(vertex, Infinity);
    }
    previous[vertex] = null;
  }

  while (!nodes.isEmpty()) {
    let smallest = nodes.dequeue().val;

    if (smallest || distances[smallest] !== Infinity) {
      for (let neighbor in graph[smallest]) {
        // নেইবারের ডিস্ট্যান্স ক্যালকুলেট
        let alt = distances[smallest] + graph[smallest][neighbor];

        // যদি ছোট হয় তাহলে আপডেট
        if (alt < distances[neighbor]) {
          distances[neighbor] = alt;
          previous[neighbor] = smallest;
          nodes.enqueue(neighbor, alt);
        }
      }
    }
  }

  return { distances, previous };
}

// সিম্পল প্রায়োরিটি কিউ বাস্তবায়ন
class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }

  isEmpty() {
    return this.values.length === 0;
  }
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  // ডিভাইড স্টেপ
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // কনকার স্টেপ (মার্জ)
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // মার্জ দুটি সর্টেড অ্যারে
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // অবশিষ্ট এলিমেন্ট যোগ করুন
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function maxSubarraySum(arr, k) {
  if (arr.length < k) return null;

  // প্রথম উইন্ডোর সাম
  let maxSum = 0;
  for (let i = 0; i < k; i++) {
    maxSum += arr[i];
  }

  let currentSum = maxSum;

  // উইন্ডো স্লাইড করুন
  for (let i = k; i < arr.length; i++) {
    currentSum = currentSum - arr[i - k] + arr[i]; // উইন্ডো শিফট
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

function topologicalSort(graph) {
  const result = [];
  const visited = {};
  const temp = {}; // সাইকেল ডিটেকট করার জন্য

  function dfs(node) {
    // সাইকেল চেক
    if (temp[node]) {
      throw new Error("Graph has a cycle, cannot perform topological sort");
    }

    if (!visited[node]) {
      temp[node] = true;

      // নেইবারদের ভিজিট
      const neighbors = graph[node] || [];
      for (let i = 0; i < neighbors.length; i++) {
        dfs(neighbors[i]);
      }

      visited[node] = true;
      temp[node] = false;

      // রেজাল্টের শুরুতে যোগ করুন
      result.unshift(node);
    }
  }

  // সব নোড প্রসেস
  for (let node in graph) {
    if (!visited[node]) {
      dfs(node);
    }
  }

  return result;
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // হ্যাশম্যাপ ফর O(1) অ্যাকসেস
    this.head = { key: 0, value: 0 };  // ডাবলি লিংকড লিস্ট হেড
    this.tail = { key: 0, value: 0 };  // ডাবলি লিংকড লিস্ট টেইল
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // নোড রিমুভ
  removeNode(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }

  // লিস্টের শুরুতে নোড যোগ করুন (MRU পজিশন)
  addToHead(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (this.cache.has(key)) {
      // কী পাওয়া গেছে, MRU হিসেবে মুভ করুন
      const node = this.cache.get(key);
      this.removeNode(node);
      this.addToHead(node);
      return node.value;
    }
    return -1; // কী পাওয়া যায়নি
  }

  put(key, value) {
    // আগে থেকেই আছে কিনা চেক করুন
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.removeNode(node);
      this.addToHead(node);
    } else {
      // LRU আইটেম রিমুভ করুন যদি ক্যাপাসিটি ফুল হয়
      if (this.cache.size === this.capacity) {
        // টেইলের আগের (LRU) নোড রিমুভ করুন
        const lru = this.tail.prev;
        this.removeNode(lru);
        this.cache.delete(lru.key);
      }

      // নতুন নোড তৈরি এবং হেডে যোগ করুন
      const newNode = { key, value, prev: null, next: null };
      this.cache.set(key, newNode);
      this.addToHead(newNode);
    }
  }
}

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill().map((_, i) => i); // প্রত্যেক নোড নিজের প্যারেন্ট
    this.rank = Array(size).fill(0); // ইউনিয়ন বাই র‍্যাঙ্ক অপ্টিমাইজেশন
  }

  // x-এর রুট নোড খুঁজে বের করুন
  find(x) {
    if (this.parent[x] !== x) {
      // পাথ কম্প্রেশন - সরাসরি রুটের সাথে লিঙ্ক করুন
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // x এবং y সম্বলিত সেট ইউনিয়ন করুন
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) return false; // ইতিমধ্যেই একই সেটে আছে

    // র‍্যাঙ্ক দ্বারা ইউনিয়ন
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    return true;
  }

  // x এবং y একই সেটে আছে কিনা
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

function countingSort(arr, min, max) {
  const count = {};

  // কাউন্ট ইনিশিয়ালাইজ
  for (let i = min; i <= max; i++) {
    count[i] = 0;
  }

  // কাউন্ট ফ্রিকোয়েন্সি
  for (let i = 0; i < arr.length; i++) {
    count[arr[i]]++;
  }

  // রিকনস্ট্রাক্ট অ্যারে
  let sortedIndex = 0;
  for (let i = min; i <= max; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }

  return arr;
}

// উদাহরণ
const array = [4, 2, 2, 8, 3, 3, 1];
const sorted = countingSort(array, 1, 8); // [1, 2, 2, 3, 3, 4, 8]

// Node class for a basic linked list
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

/**
 * Detects if a linked list has a cycle using Floyd's Cycle-Finding Algorithm
 * @param {Node} head - The head of the linked list
 * @return {boolean} - True if there is a cycle, false otherwise
 */
function hasCycle(head) {
    if (!head || !head.next) {
        return false; // Empty list or single node can't have a cycle
    }

    let slow = head; // Tortoise - moves one step at a time
    let fast = head; // Hare - moves two steps at a time

    while (fast && fast.next) {
        slow = slow.next;        // Move one step
        fast = fast.next.next;   // Move two steps

        // If there is a cycle, slow and fast will eventually meet
        if (slow === fast) {
            return true;
        }
    }

    // If fast reaches the end of the list, there's no cycle
    return false;
}

/**
 * Finds the intersection point of two linked lists, if they intersect
 * This can also detect if one or both lists have cycles
 * @param {Node} headA - Head of first linked list
 * @param {Node} headB - Head of second linked list
 * @return {Node|null} - The intersection node or null if no intersection
 */
function getIntersectionNode(headA, headB) {
    // First check if either list has a cycle
    const hasCycleA = hasCycle(headA);
    const hasCycleB = hasCycle(headB);

    // If only one list has a cycle, they cannot intersect
    if (hasCycleA !== hasCycleB) {
        return null;
    }

    // If both lists have cycles, it's more complex
    if (hasCycleA && hasCycleB) {
        return findIntersectionWithCycles(headA, headB);
    }

    // If neither has cycles, use the standard approach
    return findIntersectionNoCycles(headA, headB);
}

/**
 * Finds intersection of two acyclic linked lists
 * @param {Node} headA - Head of first linked list
 * @param {Node} headB - Head of second linked list
 * @return {Node|null} - The intersection node or null if no intersection
 */
function findIntersectionNoCycles(headA, headB) {
    if (!headA || !headB) return null;

    let pointerA = headA;
    let pointerB = headB;

    // If the lists are of different lengths, this approach will align the pointers
    while (pointerA !== pointerB) {
        pointerA = pointerA ? pointerA.next : headB;
        pointerB = pointerB ? pointerB.next : headA;
    }

    return pointerA; // Either the intersection point or null
}

/**
 * Finds the start of a cycle in a linked list
 * @param {Node} head - The head of the linked list
 * @return {Node|null} - The start node of the cycle or null if no cycle
 */
function detectCycleStart(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;
    let hasCycle = false;

    // Find meeting point inside the cycle
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null;

    // Reset slow to head and move both pointers at same speed
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow; // This is the start of the cycle
}

/**
 * Finds intersection of two linked lists that may have cycles
 * @param {Node} headA - Head of first linked list
 * @param {Node} headB - Head of second linked list
 * @return {Node|null} - The intersection node or null if no intersection
 */
function findIntersectionWithCycles(headA, headB) {
    // Find the start of cycles in both lists
    const cycleStartA = detectCycleStart(headA);
    const cycleStartB = detectCycleStart(headB);

    // Check if the cycles are the same by traversing one cycle
    let pointer = cycleStartA.next;
    while (pointer !== cycleStartA) {
        if (pointer === cycleStartB) {
            // The cycles are the same, return either cycle start
            return cycleStartA;
        }
        pointer = pointer.next;
    }

    // If we get here and cycles are different, check if cycleStartB is in cycleA
    if (cycleStartB === cycleStartA) {
        return cycleStartA; // Same cycle start point
    }

    // The lists don't intersect or have separate cycles
    return null;
}

// Example usage
function createTestLists() {
    // Create a list with a cycle
    const node1 = new Node(1);
    const node2 = new Node(2);
    const node3 = new Node(3);
    const node4 = new Node(4);
    const node5 = new Node(5);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node3; // Create cycle pointing to node3

    // Create a second list that joins the first list at node3
    const nodeA = new Node('A');
    const nodeB = new Node('B');
    nodeA.next = nodeB;
    nodeB.next = node3; // Connect to the cycle of the first list

    return { listA: node1, listB: nodeA };
}

// Test the functions
const { listA, listB } = createTestLists();
console.log("List A has cycle:", hasCycle(listA)); // Should be true
console.log("List B has cycle:", hasCycle(listB)); // Should be true

const intersection = getIntersectionNode(listA, listB);
console.log("Intersection exists:", !!intersection); // Should be true
if (intersection) {
    console.log("Intersection at node with value:", intersection.value); // Should be 3
}

function minCoins(coins, amount) {
  // dp অ্যারে ইনিশিয়ালাইজ করি
  // dp[i] = amount i তৈরি করতে সর্বনিম্ন কয়েন সংখ্যা
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 অ্যামাউন্ট এর জন্য 0 কয়েন লাগে

  for (let coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

// উদাহরণ
console.log(minCoins([1, 2, 5], 11)); // আউটপুট: 3 (5 + 5 + 1)

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// বাইনারি ট্রিতে LCA (রিকার্সিভ অ্যাপ্রোচ)
function lowestCommonAncestor(root, p, q) {
  // বেস কেসেস
  if (!root) return null;
  if (root === p || root === q) return root;

  // লেফট ও রাইট সাবট্রি সার্চ করি
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // যদি উভয় সাবট্রিতে ভ্যালু পাওয়া যায়, তাহলে বর্তমান নোড LCA
  if (left && right) return root;

  // অন্যথায় যে সাবট্রিতে একটি ভ্যালু পাওয়া গেছে তার রেজাল্ট রিটার্ন করি
  return left ? left : right;
}

// উদাহরণ ট্রি তৈরি
//       3
//     /   \
//    5     1
//   / \   / \
//  6   2 0   8
//     / \
//    7   4

const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const p = root.left; // 5
const q = root.right; // 1
console.log(lowestCommonAncestor(root, p, q).value); // আউটপুট: 3

const p2 = root.left; // 5
const q2 = root.left.right.right; // 4
console.log(lowestCommonAncestor(root, p2, q2).value); // আউটপুট: 5

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill().map((_, i) => i); // প্রতিটি নোড নিজের প্যারেন্ট
    this.rank = Array(size).fill(0); // র‍্যাঙ্ক/হাইট অপটিমাইজেশন
    this.count = size; // ডিসজয়েন্ট সেট সংখ্যা
  }

  // কোন এলিমেন্ট কোন সেটে আছে তা খুঁজে বের করে
  find(x) {
    // পাথ কম্প্রেশন অপ্টিমাইজেশন
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // দুটি সেট একত্রিত করে
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    // আগে থেকেই একই সেটে থাকলে
    if (rootX === rootY) {
      return false;
    }

    // র‍্যাঙ্ক বাই ইউনিয়ন অপ্টিমাইজেশন
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    this.count--; // সেট সংখ্যা কমে যায়
    return true;
  }

  // একই সেটে আছে কিনা চেক করে
  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  // মোট ডিসজয়েন্ট সেট সংখ্যা
  getCount() {
    return this.count;
  }
}

// উদাহরণ
const uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(3, 8);
uf.union(8, 9);

console.log(uf.connected(1, 5)); // আউটপুট: true
console.log(uf.connected(5, 9)); // আউটপুট: false
console.log(uf.getCount()); // আউটপুট: 5 (5টি ডিসজয়েন্ট সেট)

class SegmentTree {
  constructor(arr) {
    this.arr = arr;
    this.n = arr.length;
    // সেগমেন্ট ট্রি আকার প্রায় 4 * n
    this.tree = new Array(4 * this.n).fill(0);
    this.buildTree(0, 0, this.n - 1);
  }

  // রিকার্সিভলি ট্রি বিল্ড করি
  buildTree(node, start, end) {
    // লিফ নোড
    if (start === end) {
      this.tree[node] = this.arr[start];
      return;
    }

    const mid = Math.floor((start + end) / 2);
    const leftChild = 2 * node + 1;
    const rightChild = 2 * node + 2;

    // বাম ও ডান সাবট্রি বিল্ড করি
    this.buildTree(leftChild, start, mid);
    this.buildTree(rightChild, mid + 1, end);

    // পেয়ারেন্ট নোড আপডেট করি
    this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
  }

  // রেঞ্জ সাম কোয়েরি
  querySum(left, right) {
    return this._querySum(0, 0, this.n - 1, left, right);
  }

  _querySum(node, start, end, left, right) {
    // রেঞ্জের বাইরে
    if (start > right || end < left) {
      return 0;
    }

    // কমপ্লিট রেঞ্জ কভার করছে
    if (left <= start && end <= right) {
      return this.tree[node];
    }

    // পার্শিয়াল ওভারল্যাপ
    const mid = Math.floor((start + end) / 2);
    const leftChild = 2 * node + 1;
    const rightChild = 2 * node + 2;

    const leftSum = this._querySum(leftChild, start, mid, left, right);
    const rightSum = this._querySum(rightChild, mid + 1, end, left, right);

    return leftSum + rightSum;
  }

  // একক উপাদান আপডেট
  update(index, newValue) {
    const diff = newValue - this.arr[index];
    this.arr[index] = newValue;
    this._update(0, 0, this.n - 1, index, diff);
  }

  _update(node, start, end, index, diff) {
    // আপডেট প্রয়োজন নেই
    if (index < start || index > end) {
      return;
    }

    // নোড আপডেট করি
    this.tree[node] += diff;

    // লিফ নোড না হলে রিকার্সিভলি আপডেট করি
    if (start !== end) {
      const mid = Math.floor((start + end) / 2);
      const leftChild = 2 * node + 1;
      const rightChild = 2 * node + 2;

      this._update(leftChild, start, mid, index, diff);
      this._update(rightChild, mid + 1, end, index, diff);
    }
  }
}

// উদাহরণ
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);

console.log(segTree.querySum(1, 3)); // আউটপুট: 15 (3+5+7)
segTree.update(2, 10);
console.log(segTree.querySum(1, 3)); // আউটপুট: 20 (3+10+7)

// সাবওয়ে সাম ইকুয়ালস কে (k)
function subarraySum(nums, k) {
  const prefixSums = new Map();
  prefixSums.set(0, 1); // শূন্য সামের 1টি সাবওয়ে আছে (খালি সাবওয়ে)

  let count = 0;
  let currentSum = 0;

  for (let num of nums) {
    currentSum += num;

    // যদি currentSum - k আগে দেখা থাকে, তাহলে k সামের সাবওয়ে আছে
    if (prefixSums.has(currentSum - k)) {
      count += prefixSums.get(currentSum - k);
    }

    // প্রিফিক্স সাম অ্যাড করি
    prefixSums.set(currentSum, (prefixSums.get(currentSum) || 0) + 1);
  }

  return count;
}

// উদাহরণ
console.log(subarraySum([1, 1, 1], 2)); // আউটপুট: 2
console.log(subarraySum([1, 2, 3, 4, 5], 9)); // আউটপুট: 2

function dijkstra(graph, startNode, endNode) {
  // প্রায়োরিটি কিউ ব্যবহার করা ভালো, এখানে সিম্পল অ্যারে দিয়ে দেখাচ্ছি
  const distances = {};
  const previous = {};
  const nodes = new Set();

  // ইনিশিয়ালাইজেশন
  for (let vertex in graph) {
    if (vertex === startNode) {
      distances[vertex] = 0;
    } else {
      distances[vertex] = Infinity;
    }
    previous[vertex] = null;
    nodes.add(vertex);
  }

  // সবচেয়ে কম দূরত্বের নোড খুঁজে বের করা
  function extractMinimum() {
    let minVertex = null;

    for (let vertex of nodes) {
      if (minVertex === null || distances[vertex] < distances[minVertex]) {
        minVertex = vertex;
      }
    }

    return minVertex;
  }

  // যতক্ষণ নোড আছে
  while (nodes.size > 0) {
    const current = extractMinimum();

    // যদি ডেস্টিনেশন পৌঁছে যাই বা অসীম দূরত্ব পাই
    if (current === endNode || distances[current] === Infinity) {
      break;
    }

    nodes.delete(current);

    // প্রতিটি প্রতিবেশী নোড এর জন্য
    for (let neighbor in graph[current]) {
      // আমরা current থেকে neighbor এ যাওয়ার দূরত্ব
      const alt = distances[current] + graph[current][neighbor];

      // যদি নতুন পাথ ছোট হয়
      if (alt < distances[neighbor]) {
        distances[neighbor] = alt;
        previous[neighbor] = current;
      }
    }
  }

  // শর্টেস্ট পাথ রিকনস্ট্রাক্ট
  const path = [];
  let current = endNode;

  while (current !== null) {
    path.unshift(current);
    current = previous[current];
  }

  return {
    distance: distances[endNode],
    path: path
  };
}

// উদাহরণ
const graph = {
  A: { B: 4, C: 2 },
  B: { A: 4, C: 1, D: 5 },
  C: { A: 2, B: 1, D: 8, E: 10 },
  D: { B: 5, C: 8, E: 2 },
  E: { C: 10, D: 2 }
};

console.log(dijkstra(graph, 'A', 'E'));
// আউটপুট: { distance: 9, path: ['A', 'C', 'B', 'D', 'E'] }

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // শব্দ ইনসার্ট
  insert(word) {
    let current = this.root;

    for (let char of word) {
      if (!current.children[char]) {
        current.children[char] = new TrieNode();
      }
      current = current.children[char];
    }

    current.isEndOfWord = true;
  }

  // শব্দ সার্চ
  search(word) {
    let current = this.root;

    for (let char of word) {
      if (!current.children[char]) {
        return false;
      }
      current = current.children[char];
    }

    return current.isEndOfWord;
  }

  // প্রিফিক্স সার্চ
  startsWith(prefix) {
    let current = this.root;

    for (let char of prefix) {
      if (!current.children[char]) {
        return false;
      }
      current = current.children[char];
    }

    return true;
  }

  // প্রিফিক্স দিয়ে শব্দ সাজেশন
  findWordsWithPrefix(prefix) {
    const result = [];
    let current = this.root;

    // প্রিফিক্স নোড এ যাই
    for (let char of prefix) {
      if (!current.children[char]) {
        return result;
      }
      current = current.children[char];
    }

    // এই নোড থেকে DFS করে সব শব্দ খুঁজি
    this._collectWords(current, prefix, result);
    return result;
  }

  _collectWords(node, prefix, result) {
    if (node.isEndOfWord) {
      result.push(prefix);
    }

    for (let char in node.children) {
      this._collectWords(node.children[char], prefix + char, result);
    }
  }
}

// উদাহরণ
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
console.log(trie.search("app")); // true
console.log(trie.startsWith("ap")); // true
console.log(trie.findWordsWithPrefix("app")); // ["app", "apple", "application"]