FBDS

/* 314 binary-tree-vertical-order-traversal M
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

      3
     / \
    9   20
       /  \
      15   7

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

      3
     / \
    9   8
   / \  / \
  4   0 1  7

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

        1
       / \
      2   3
     / \  / \
    4  10 9  11
     \
      5
       \
        6

Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
Output: [[4],[2,5],[1,10,9,6],[3],[11]]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Approach
Use BFS (Breadth-First Search) with a queue to traverse level by level.

Maintain a map (or object) to store node values grouped by their vertical column index.

Use a queue that stores (node, column, row), where:

column tracks vertical alignment (left is -1, right is +1).

row tracks depth (for sorting when needed).

After traversal:

Sort nodes by column first.

If multiple nodes share the same column, sort by row.

If row values are the same, sort by left-to-right order.

Construct the final result by collecting values column-wise.

Time Complexity
O(N log N) in the worst case due to sorting inside each column.

O(N) for traversal of the tree.

Space Complexity
O(N) for storing nodes in the hash map and queue.

This solution efficiently organizes and sorts nodes based on column and row values while maintaining left-to-right order. 🚀
*/


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

function verticalOrderTraversal(root) {
    if (!root) return [];

    let columnMap = new Map();
    let queue = [[root, 0, 0]]; // [node, column, row]
    let minCol = 0, maxCol = 0;

    while (queue.length) {
        let [node, col, row] = queue.shift();

        if (!columnMap.has(col)) columnMap.set(col, []);
        columnMap.get(col).push([row, node.val]);

        minCol = Math.min(minCol, col);
        maxCol = Math.max(maxCol, col);

        if (node.left) queue.push([node.left, col - 1, row + 1]);
        if (node.right) queue.push([node.right, col + 1, row + 1]);
    }

    let result = [];
    for (let i = minCol; i <= maxCol; i++) {
        let sortedNodes = columnMap.get(i).sort((a, b) => {
            if (a[0] !== b[0]) return a[0] - b[0]; // Sort by row
            return a[1] - b[1]; // Sort by value for same row
        }).map(x => x[1]);
        result.push(sortedNodes);
    }

    return result;
}

// Example Usage
let root1 = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(verticalOrderTraversal(root1)); // [[9], [3, 15], [20], [7]]

let root2 = new TreeNode(3,
    new TreeNode(9, new TreeNode(4), new TreeNode(0)),
    new TreeNode(8, new TreeNode(1), new TreeNode(7))
);
console.log(verticalOrderTraversal(root2)); // [[4], [9], [3, 0, 1], [8], [7]]


/*
Let's walk through an example step by step for the input:

Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
Step 1: Construct the Binary Tree
The given input represents a binary tree:


           1
         /   \
        2     3
       / \   /  \
      4  10 9   11
       \
        5
         \
          6
Each node has an associated column index:

Root (1) is at column 0

Left children move to column -1, right children move to column +1

Step 2: Assign Column & Row Indices
We traverse the tree using BFS, maintaining (node, column, row):

Node    Column  Row
1   0   0
2   -1  1
3   +1  1
4   -2  2
10  0   2
9   0   2
11  +2  2
5   -1  3
6   0   4
Step 3: Group by Column
Sorting nodes first by column and then by row:

Column. Nodes Sorted by Row.    Values
-2  [(2,4)] [4]
-1  [(1,2), (3,5)]  [2,5]
0   [(0,1), (2,10), (2,9), (4,6)]   [1,10,9,6]
+1  [(1,3)] [3]
+2  [(2,11)]    [11]
Step 4: Construct the Output

Output: [[4], [2,5], [1,10,9,6], [3], [11]]


Explanation of Code:
Define TreeNode Class:

Each node stores val, left, and right pointers.

Vertical Order Traversal Algorithm:

Use BFS (Level Order Traversal) with a queue ([node, column, row]).

Store values in a Map, where column is the key, and the value is an array [row, val].

Sort the columns (left to right) and within each column, sort by row and value.

Tree Construction:

Builds the given binary tree structure.

Print the Output:

Expected Output: [[4], [2,5], [1,10,9,6], [3], [11]]

Time and Space Complexity:
Time Complexity: O(N log N)

O(N) for BFS traversal.

O(N log N) sorting columns and rows.

Space Complexity: O(N)

O(N) for storing nodes in the columnMap.

O(N) queue storage.

This solution is efficient for N ≤ 100 nodes. 🚀
*/


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

function verticalOrderTraversal(root) {
    if (!root) return [];

    let columnMap = new Map();
    let queue = [[root, 0, 0]]; // [node, column, row]

    while (queue.length > 0) {
        let [node, col, row] = queue.shift();

        if (!columnMap.has(col)) columnMap.set(col, []);
        columnMap.get(col).push([row, node.val]);

        if (node.left) queue.push([node.left, col - 1, row + 1]);
        if (node.right) queue.push([node.right, col + 1, row + 1]);
    }

    return [...columnMap.entries()]
        .sort((a, b) => a[0] - b[0]) // Sort by column index
        .map(([_, values]) =>
            values.sort((a, b) => a[0] - b[0] || a[1] - b[1]) // Sort by row, then value
                  .map(v => v[1])
        );
}

// Constructing the tree: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
let root = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4, null, new TreeNode(5, null, new TreeNode(6))),
        new TreeNode(10)
    ),
    new TreeNode(3,
        new TreeNode(9),
        new TreeNode(11)
    )
);

console.log(verticalOrderTraversal(root));
// Expected Output: [[4], [2,5], [1,10,9,6], [3], [11]]

/* 408. Valid Word Abbreviation Easy

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)
The following are not valid abbreviations:

"s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
"s010n" (has leading zeros)
"s0ubstitution" (replaces an empty substring)
Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.



Example 1:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").
Example 2:

Input: word = "apple", abbr = "a2e"
Output: false
Explanation: The word "apple" cannot be abbreviated as "a2e".


Constraints:

1 <= word.length <= 20
word consists of only lowercase English letters.
1 <= abbr.length <= 10
abbr consists of lowercase English letters and digits.
All the integers in abbr will fit in a 32-bit integer.

Explanation
Two Pointers Approach:

i tracks the position in word

j tracks the position in abbr

Handling Digits in abbr:

If abbr[j] is a digit:

Ensure it’s not '0' (leading zeros not allowed).

Convert consecutive digits into a number.

Move i forward by this number.

Handling Characters in abbr:

If abbr[j] is a letter, check if word[i] matches abbr[j].

If not, return false.

Final Check:

i should reach word.length and j should reach abbr.length exactly.

Time and Space Complexity
Time Complexity: O(N + M), where:

N = length of word

M = length of abbr

Each character in abbr is processed once.

Space Complexity: O(1)

We use only a few integer variables (i, j, num), which take constant space.

🚀 Optimized and efficient for small input sizes (word ≤ 20, abbr ≤ 10).
*/

function validWordAbbreviation(word, abbr) {
    let i = 0, j = 0;

    while (i < word.length && j < abbr.length) {
        if (!isNaN(abbr[j]) && abbr[j] !== '0') {  // If `abbr[j]` is a number and not '0'
            let num = 0;
            while (j < abbr.length && !isNaN(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            i += num;  // Skip `num` characters in `word`
        } else {
            if (word[i] !== abbr[j]) return false; // Mismatched character
            i++;
            j++;
        }
    }

    return i === word.length && j === abbr.length;
}

// Example Test Cases
console.log(validWordAbbreviation("internationalization", "i12iz4n")); // true
console.log(validWordAbbreviation("apple", "a2e")); // false
console.log(validWordAbbreviation("substitution", "s10n")); // true
console.log(validWordAbbreviation("substitution", "s55n")); // false (adjacent numbers not allowed)
console.log(validWordAbbreviation("substitution", "s010n")); // false (leading zero not allowed)
console.log(validWordAbbreviation("substitution", "s0ubstitution")); // false (empty substring replacement)

/* 339. Nested List Weight Sum Medium

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.
Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.
Example 3:

Input: nestedList = [0]
Output: 0

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list is in the range [-100, 100].
The maximum depth of any integer is less than or equal to 50.

Explanation
Recursive Depth-First Search (DFS):

We define a helper function dfs(list, depth) to traverse the nested structure.

Initialize sum = 0 at each level.

Iterate through each element:

If it’s an integer, multiply it by the current depth and add it to sum.

If it’s a list, call dfs recursively with an incremented depth.

Base Case:

If the list is empty, return 0.

Starting Condition:

We call dfs(nestedList, 1) since the top level starts at depth 1.

Time and Space Complexity
Time Complexity: O(N)

N is the total number of integers and lists in nestedList.

Each element is visited once.

Space Complexity: O(D) (Depth of recursion)

D is the maximum depth of nesting (≤ 50).

In the worst case, recursion goes as deep as D.

🚀 This solution efficiently handles nested structures and computes the weighted sum.
*/

function depthSum(nestedList) {
    function dfs(list, depth) {
        let sum = 0;
        for (let element of list) {
            if (Array.isArray(element)) {
                sum += dfs(element, depth + 1);
            } else {
                sum += element * depth;
            }
        }
        return sum;
    }
    return dfs(nestedList, 1);
}

// Example Test Cases
console.log(depthSum([[1,1],2,[1,1]])); // Output: 10
console.log(depthSum([1,[4,[6]]])); // Output: 27
console.log(depthSum([0])); // Output: 0

/* 1249. Minimum Remove to Make Valid Parentheses Medium

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.


Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.


Constraints:

1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.

Explanation
Convert String to Array: Since strings are immutable in JavaScript, converting it to an array allows us to modify characters efficiently.

First Pass (Left to Right):

Use a stack to track indices of unmatched '('.

If ')' is found and there's no unmatched '(', mark it for removal.

Second Pass (Right to Left):

Remove all unmatched '(' left in the stack.

Reconstruct the String:

Join the array back into a valid string.

Time and Space Complexity
Time Complexity: O(N)

We traverse the string twice, once to process parentheses and once to reconstruct the string.

Space Complexity: O(N)

We use an array (arr) of size N and a stack storing unmatched parentheses indices (at most N/2).

🚀 This approach efficiently removes the minimum number of parentheses to make the string valid.
*/

function minRemoveToMakeValid(s) {
    let stack = [];
    let arr = s.split(""); // Convert string to array for easy modification

    // First pass: Mark invalid closing brackets ')'
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '(') {
            stack.push(i);
        } else if (arr[i] === ')') {
            if (stack.length > 0) {
                stack.pop(); // Valid match found
            } else {
                arr[i] = ''; // Mark invalid ')' for removal
            }
        }
    }

    // Second pass: Remove unmatched opening brackets '('
    while (stack.length > 0) {
        arr[stack.pop()] = '';
    }

    return arr.join(""); // Reconstruct the valid string
}

// Example Test Cases
console.log(minRemoveToMakeValid("lee(t(c)o)de)")); // Output: "lee(t(c)o)de"
console.log(minRemoveToMakeValid("a)b(c)d"));       // Output: "ab(c)d"
console.log(minRemoveToMakeValid("))(("));         // Output: ""



/* 1650. Lowest Common Ancestor of a Binary Tree III Medium

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}
According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example 1:

        3
       / \
      5   1
     / \  / \
    6   2 0  8
       / \
      7   4

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

        3
       / \
      5   1
     / \  / \
    6   2 0  8
       / \
      7   4

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Example 3:

    1
   /
  2

Input: root = [1,2], p = 1, q = 2
Output: 1


Constraints:

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q exist in the tree.


JavaScript Solution: Lowest Common Ancestor (LCA) of Two Nodes in a Binary Tree
Since each node has a reference to its parent, we can find the Lowest Common Ancestor (LCA) efficiently by moving up the tree.

Approach
Use Two Pointers (p and q)

Start from p and q, moving their parents upward.

If one pointer reaches the root (null), reset it to the other node.

When p === q, we have found the LCA.

Why This Works?

This approach ensures that both pointers traverse the same distance.

If p and q have different depths, switching the pointer after reaching null balances the paths.

When they meet, it's guaranteed to be the LCA.

Time and Space Complexity
Time Complexity: O(H)

H is the height of the tree.

Each node is visited at most twice.

Space Complexity: O(1)

Uses only constant extra space since we are not using recursion or additional data structures.

🚀 This is an efficient approach using parent pointers, ensuring an optimal O(H) complexity!

*/

class Node {
    constructor(val, parent = null, left = null, right = null) {
        this.val = val;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(p, q) {
    let a = p, b = q;

    while (a !== b) {
        a = a ? a.parent : q;
        b = b ? b.parent : p;
    }

    return a; // or return b, both are the same
}

// Example Test Case
let root = new Node(3);
let node5 = new Node(5, root);
let node1 = new Node(1, root);
let node6 = new Node(6, node5);
let node2 = new Node(2, node5);
let node0 = new Node(0, node1);
let node8 = new Node(8, node1);
let node7 = new Node(7, node2);
let node4 = new Node(4, node2);

root.left = node5;
root.right = node1;
node5.left = node6;
node5.right = node2;
node1.left = node0;
node1.right = node8;
node2.left = node7;
node2.right = node4;

console.log(lowestCommonAncestor(node5, node1).val); // Output: 3
console.log(lowestCommonAncestor(node5, node4).val); // Output: 5
console.log(lowestCommonAncestor(root, node2).val);  // Output: 3


/*
Changes & Improvements
Function Signature Matches Your Request 🎯

Now accepts array representation of the tree and two integer values for p and q.

Internally Builds the Tree 🌳

Uses buildTree(arr) to create a binary tree with parent pointers.

Finds Nodes in the Tree 🔎

Uses findNode(root, val) to locate p and q.

Computes LCA Using Two-Pointer Approach 🚀

Efficiently finds LCA in O(H) time with O(1) extra space.

Time & Space Complexity
Operation   Time Complexity Space Complexity
Building Tree   O(N)    O(N)
Finding Node    O(N)    O(H) (Recursion)
Finding LCA O(H)    O(1)
Overall Complexity  O(N)    O(N)
✅  🚀
*/


class Node {
    constructor(val, parent = null) {
        this.val = val;
        this.parent = parent;
        this.left = null;
        this.right = null;
    }
}

// Function to build a binary tree from an array representation
function buildTree(arr) {
    if (!arr.length) return null;

    let nodes = arr.map(val => (val !== null ? new Node(val) : null));

    for (let i = 0; i < arr.length; i++) {
        if (nodes[i] !== null) {
            let leftIndex = 2 * i + 1;
            let rightIndex = 2 * i + 2;

            if (leftIndex < arr.length && nodes[leftIndex] !== null) {
                nodes[i].left = nodes[leftIndex];
                nodes[leftIndex].parent = nodes[i]; // Set parent reference
            }
            if (rightIndex < arr.length && nodes[rightIndex] !== null) {
                nodes[i].right = nodes[rightIndex];
                nodes[rightIndex].parent = nodes[i]; // Set parent reference
            }
        }
    }
    return nodes[0]; // Return root
}

// Function to find a node in the tree by value
function findNode(root, val) {
    if (!root) return null;
    if (root.val === val) return root;
    return findNode(root.left, val) || findNode(root.right, val);
}

// Modified lowestCommonAncestor function
function lowestCommonAncestor(arr, val1, val2) {
    let root = buildTree(arr);
    let p = findNode(root, val1);
    let q = findNode(root, val2);

    if (!p || !q) return null; // Edge case if nodes are not found

    let a = p, b = q;

    while (a !== b) {
        a = a ? a.parent : q;
        b = b ? b.parent : p;
    }

    return a.val; // Return LCA value
}

// Example Test Cases

// Example 1
console.log(lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4], 5, 1)); // Output: 3

// Example 2
console.log(lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4], 5, 4)); // Output: 5

// Example 3
console.log(lowestCommonAncestor([1,2], 1, 2)); // Output: 1


/* =================================
227. Basic Calculator II M

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7
Example 2:

Input: s = " 3/2 "
Output: 1
Example 3:

Input: s = " 3+5 / 2 "
Output: 5


Constraints:

1 <= s.length <= 3 * 105
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.

*/

function calculate(s) {
    let stack = [];
    let num = 0;
    let sign = '+';
    s = s.replace(/\s+/g, ''); // Remove spaces for easier parsing

    for (let i = 0; i < s.length; i++) {
        let char = s[i];

        if (!isNaN(char)) {
            num = num * 10 + (char - '0'); // Build multi-digit numbers
        }

        if (isNaN(char) || i === s.length - 1) {
            if (sign === '+') {
                stack.push(num);
            } else if (sign === '-') {
                stack.push(-num);
            } else if (sign === '*') {
                stack.push(stack.pop() * num);
            } else if (sign === '/') {
                stack.push(Math.trunc(stack.pop() / num)); // Truncate towards zero
            }

            sign = char; // Update sign to the new operator
            num = 0; // Reset number for next iteration
        }
    }

    return stack.reduce((acc, val) => acc + val, 0);
}

// **Example Test Cases**
console.log(calculate("3+2*2"));    // Output: 7
console.log(calculate(" 3/2 "));    // Output: 1
console.log(calculate(" 3+5 / 2 ")); // Output: 5
/*
The approach utilizes a stack-based method to handle multiplication and division before addition and subtraction.

Approach
Use a stack to store numbers while processing the expression.

Iterate through the string character by character:

If the character is a digit, extract the full number.

If the character is an operator (+, -, *, /), process the last number accordingly:

Push addition (+) and subtraction (-) directly into the stack.

Apply multiplication (*) and division (/) immediately with the last number in the stack.

Sum all values in the stack to get the final result.

Time & Space Complexity
Time Complexity: O(n) → Each character is processed once.

Space Complexity: O(n) in the worst case (if all numbers are stored in the stack).
*/

function calculate(s) {
    let stack = [];
    let num = 0;
    let sign = '+'; // Default operator
    let n = s.length;

    for (let i = 0; i < n; i++) {
        let char = s[i];

        // Build full number
        if (char >= '0' && char <= '9') {
            num = num * 10 + (char - '0');
        }

        // If current char is an operator or we are at the last character
        if ((char < '0' || char > '9') && char !== ' ' || i === n - 1) {
            if (sign === '+') {
                stack.push(num);
            } else if (sign === '-') {
                stack.push(-num);
            } else if (sign === '*') {
                let last = stack.pop();
                stack.push(last * num);
            } else if (sign === '/') {
                let last = stack.pop();
                let result = last / num;

                // stack.push(Math.trunc(stack.pop() / num)); // Truncate towards zero
                // stack.push(last > 0 ? Math.floor(result) : Math.ceil(result)); // Manual truncation

                // **Manual truncation towards zero**
                if (result < 0) {
                    stack.push(result | 0); // Bitwise OR with zero truncates decimal part
                } else {
                    stack.push(result - (result % 1)); // Remove decimal part manually
                }
            }

            sign = char; // Update operator
            num = 0; // Reset number
        }
    }

    // Manually sum the stack values
    let result = 0;
    for (let val of stack) {
        result += val;
    }

    return result;
}

// **Example Test Cases**
console.log(calculate("3+2*2"));    // Output: 7
console.log(calculate(" 3/2 "));    // Output: 1
console.log(calculate(" 3+5 / 2 ")); // Output: 5
console.log(calculate("14-3/2"));  // Output: 13
console.log(calculate("10/3"));    // Output: 3
console.log(calculate("-10/3"));   // Output: -3


/* =================================

680. Valid Palindrome II Easy
Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true
Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Example 3:

Input: s = "abc"
Output: false


Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

Approach
Use a two-pointer approach to check for palindrome.

If a mismatch is found, try removing either the left or right character and check if the remaining substring is a palindrome.

This ensures we only delete at most one character.

Time & Space Complexity
Time Complexity: O(n) (single pass for checking + one more pass in case of a mismatch)

Space Complexity: O(1) (no extra space used, only pointers)

*/

function validPalindrome(s) {
    function isPalindrome(l, r) {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    }

    let left = 0, right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) {
            // Try removing either left or right character and check palindrome
            return isPalindrome(left + 1, right) || isPalindrome(left, right - 1);
        }
        left++;
        right--;
    }

    return true;
}

// **Example Test Cases**
console.log(validPalindrome("aba"));   // Output: true
console.log(validPalindrome("abca"));  // Output: true
console.log(validPalindrome("abc"));   // Output: false
console.log(validPalindrome("racecar")); // Output: true
console.log(validPalindrome("deeee"));  // Output: true
console.log(validPalindrome("abcddcba"));  // Output: true
console.log(validPalindrome("abcdedcba")); // Output: true

/* =================================

1762. Buildings With an Ocean View Medium

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.
Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.
Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

Constraints:

1 <= heights.length <= 105
1 <= heights[i] <= 109

*/

function findBuildings(heights) {
    let result = [];
    let maxSoFar = -Infinity;

    for (let i = heights.length - 1; i >= 0; i--) {
        if (heights[i] > maxSoFar) {
            result.push(i);
            maxSoFar = heights[i];
        }
    }

    return result.reverse(); // Sorting in increasing order of indices

    /* Manually reversing the array
    let left = 0, right = result.length - 1;
    while (left < right) {
        [result[left], result[right]] = [result[right], result[left]];
        left++;
        right--;
    }

    return result;
    */
}

// **Example Test Cases**
console.log(findBuildings([4, 2, 3, 1])); // Output: [0, 2, 3]
console.log(findBuildings([4, 3, 2, 1])); // Output: [0, 1, 2, 3]
console.log(findBuildings([1, 3, 2, 4])); // Output: [3]
console.log(findBuildings([10, 8, 6, 4, 2])); // Output: [0, 1, 2, 3, 4]
console.log(findBuildings([2, 3, 4, 5, 1])); // Output: [3, 4]

/*
Time & Space Complexity
Time Complexity: O(n) (single pass from right to left)

Space Complexity: O(n) (to store the indices of valid buildings)

This approach ensures efficient traversal while keeping the logic simple and easy to follow! 🚀
*/


/* =================================

1570. Dot Product of Two Sparse Vectors Medium

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6


Constraints:

n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100

Approach
Since the vectors are sparse (mostly zeros), storing all elements wastes space. Instead, we use a dictionary (object) or a map to store only non-zero elements with their indices. This reduces space complexity significantly.

For computing the dot product, we:

Iterate over the smaller sparse representation to minimize operations.

Multiply values where indices match.

Sum the results.

Time & Space Complexity
Initialization: O(n) (storing only non-zero elements)

Dot Product: O(min(N1, N2)) where N1, N2 are the non-zero elements count.

Space Complexity: O(N1 + N2) (storing only non-zero elements)

This approach efficiently handles large vectors while minimizing operations! 🚀

*/

class SparseVector {
    constructor(nums) {
        this.sparseMap = new Map();
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] !== 0) {
                this.sparseMap.set(i, nums[i]);
            }
        }
    }

    dotProduct(vec) {
        let result = 0;
        // Iterate over the smaller sparse vector for efficiency
        let smaller = this.sparseMap.size <= vec.sparseMap.size ? this.sparseMap : vec.sparseMap;
        let larger = this.sparseMap.size > vec.sparseMap.size ? this.sparseMap : vec.sparseMap;

        for (let [index, value] of smaller) {
            if (larger.has(index)) {
                result += value * larger.get(index);
            }
        }
        return result;
    }
}

// **Example Test Cases**
let v1 = new SparseVector([1, 0, 0, 2, 3]);
let v2 = new SparseVector([0, 3, 0, 4, 0]);
console.log(v1.dotProduct(v2)); // Output: 8

let v3 = new SparseVector([0, 1, 0, 0, 0]);
let v4 = new SparseVector([0, 0, 0, 0, 2]);
console.log(v3.dotProduct(v4)); // Output: 0

let v5 = new SparseVector([0, 1, 0, 0, 2, 0, 0]);
let v6 = new SparseVector([1, 0, 0, 0, 3, 0, 4]);
console.log(v5.dotProduct(v6)); // Output: 6


/* =================================
528. Random Pick with Weight Medium

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).


Example 1:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.


Constraints:

1 <= w.length <= 104
1 <= w[i] <= 105
pickIndex will be called at most 104 times.


Approach
We need to pick an index randomly based on the given weights, ensuring that index i is picked with probability w[i] / sum(w). The best way to achieve this efficiently is by using the prefix sum + binary search approach.

Steps
Precompute prefix sums:

Convert w into a prefix sum array:
prefix[i] = w[0] + w[1] + ... + w[i]

This allows us to map ranges of numbers to indices.

Pick a random number:

Generate a random number rand in the range [1, sum(w)].

Find the corresponding index using binary search:

Use binary search (lower_bound) to find the smallest prefix sum that is greater than or equal to rand.

The index where it appears is the selected index.

This method ensures O(log n) lookup time for pickIndex(), making it efficient even for large inputs.

Time & Space Complexity
Constructor (Solution(w)):

Time Complexity: O(n) (building prefix sum)

Space Complexity: O(n) (storing prefix sums)

pickIndex():

Time Complexity: O(log n) (binary search)

Space Complexity: O(1) (constant extra space)

This approach is efficient and scales well for large inputs. 🚀

*/
class Solution {
    constructor(w) {
        this.prefixSums = [];
        this.totalSum = 0;

        for (let weight of w) {
            this.totalSum += weight;
            this.prefixSums.push(this.totalSum);
        }
    }

    pickIndex() {
        let rand = Math.random() * this.totalSum;
        let left = 0, right = this.prefixSums.length - 1;

        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (this.prefixSums[mid] > rand) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// **Example Test Cases**
let solution1 = new Solution([1]);
console.log(solution1.pickIndex()); // Always 0

let solution2 = new Solution([1, 3]);
console.log(solution2.pickIndex()); // Should return 0 ~25% of the time, 1 ~75% of the time


class Solution {
    constructor(w) {
        this.prefixSums = [];
        this.totalSum = 0;
        this.seed = 123456789; // Initial seed for randomness

        for (let weight of w) {
            this.totalSum += weight;
            this.prefixSums.push(this.totalSum);
        }
    }

    // Custom random number generator (LCG)
    randomLCG() {
        this.seed = (this.seed * 1664525 + 1013904223) % (2 ** 32);
        return this.seed / (2 ** 32); // Normalize to [0,1)
    }

    // Integer division without Math.floor()
    intDiv(a, b) {
        return (a - (a % b)) / b;
    }

    pickIndex() {
        let rand = this.randomLCG() * this.totalSum;
        let left = 0, right = this.prefixSums.length - 1;

        while (left < right) {
            let mid = this.intDiv(left + right, 2); // Using custom integer division
            if (this.prefixSums[mid] > rand) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// **Example Test Cases**
let solution1 = new Solution([1]);
console.log(solution1.pickIndex()); // Always 0

let solution2 = new Solution([1, 3]);
console.log(solution2.pickIndex()); // Should return 0 ~25% of the time, 1 ~75% of the time


/* =========================
938. Range Sum of BST Easy

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].



Example 1:

       10
      /  \
     5    15
    / \     \
   3   7     18

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

        10
       /  \
      5    15
     / \   /  \
    3   7 13  18
   /   /
  1   6

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.


Constraints:

The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.


Here is an efficient JavaScript implementation for summing all the nodes in a Binary Search Tree (BST) that fall within the given range [low, high].

Approach
Since it is a BST, we can avoid unnecessary recursion:

If node.val < low: Only explore the right subtree.

If node.val > high: Only explore the left subtree.

Otherwise, include node.val and explore both subtrees.

This reduces the number of recursive calls, making it more efficient than a brute-force traversal.


Time & Space Complexity
Time Complexity:

O(n) in the worst case (if the tree is a linked list).

O(log n) in the average case (if the tree is balanced).

Space Complexity:

O(h) due to recursion stack, where h is the tree height (O(log n) for balanced, O(n) for skewed).

This implementation efficiently finds the sum of node values within the range [low, high] in a BST. 🚀

*/

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

function rangeSumBST(root, low, high) {
    if (!root) return 0;

    if (root.val < low) {
        return rangeSumBST(root.right, low, high);
    }
    if (root.val > high) {
        return rangeSumBST(root.left, low, high);
    }

    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}

// **Example 1**
let root1 = new TreeNode(10,
    new TreeNode(5, new TreeNode(3), new TreeNode(7)),
    new TreeNode(15, null, new TreeNode(18))
);
console.log(rangeSumBST(root1, 7, 15)); // Output: 32

// **Example 2**
let root2 = new TreeNode(10,
    new TreeNode(5, new TreeNode(3, new TreeNode(1)), new TreeNode(7, new TreeNode(6))),
    new TreeNode(15, new TreeNode(13), new TreeNode(18))
);
console.log(rangeSumBST(root2, 6, 10)); // Output: 23


/* ===============================

215. Kth Largest Element in an Array Medium

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104



You can solve this efficiently without sorting the entire array by using a Min Heap of size k. This ensures the kth largest element is always at the top of the heap.

✅ Approach: Min Heap (Priority Queue)
Keep a min-heap of the top k elements seen so far.

If the size exceeds k, pop the smallest.

The top of the heap will be the kth largest.

🧠 Why this works:
The heap always contains the k largest elements from the array.

The smallest among them (heap top) is the kth largest overall.



🕒 Time Complexity:
O(n log k) where n is nums.length, because each insert/pop operation in the heap of size k takes log k.

📦 Space Complexity:
O(k) for the heap.
*/

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

    push(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    pop() {
        if (this.size() <= 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return top;
    }

    peek() {
        return this.heap[0];
    }

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

    _heapifyUp() {
        let i = this.heap.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.heap[i] >= this.heap[parent]) break;
            [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
            i = parent;
        }
    }

    _heapifyDown() {
        let i = 0;
        const n = this.heap.length;
        while (true) {
            let left = 2 * i + 1, right = 2 * i + 2;
            let smallest = i;

            if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
            if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;

            if (smallest === i) break;

            [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
            i = smallest;
        }
    }
}

function findKthLargest(nums, k) {
    const heap = new MinHeap();

    for (let num of nums) {
        heap.push(num);
        if (heap.size() > k) heap.pop();
    }

    return heap.peek();
}

console.log(findKthLargest([3,2,1,5,6,4], 2)); // Output: 5
console.log(findKthLargest([3,2,3,1,2,4,5,5,6], 4)); // Output: 4


*/
✅ Approach: Quickselect (Average O(n), Worst O(n²))
Quickselect is an efficient algorithm based on QuickSort partitioning. Instead of sorting the whole array, it partitions the array and recursively narrows down the search space until we find the kth largest element.

🛠 How Quickselect Works:
Pick a pivot (we use the last element for simplicity).

Partition the array so that:

Elements greater than the pivot are on the left.

Elements smaller than the pivot are on the right.

Check the position of the pivot:

If it’s the kth largest index, return it.

If it’s greater, recurse on the left half.

If it’s smaller, recurse on the right half.

🕒 Time Complexity Analysis
Best & Average Case: O(n)

Worst Case (Unbalanced Partitions): O(n²), but rare (can be optimized with random pivots).

📦 Space Complexity:
O(1) (in-place partitioning, no extra memory used)

🚀 Why Quickselect?
Faster than sorting (O(n log n)) for large datasets.

Less memory usage than a heap (O(k) space).

Let me know if you need further optimizations! 🚀

*/

function quickSelect(nums, left, right, k) {
    let pivotIndex = partition(nums, left, right);

    if (pivotIndex === k) return nums[pivotIndex]; // Found the kth largest
    if (pivotIndex > k) return quickSelect(nums, left, pivotIndex - 1, k); // Search left
    return quickSelect(nums, pivotIndex + 1, right, k); // Search right
}

function partition(nums, left, right) {
    let pivot = nums[right]; // Choosing last element as pivot
    let i = left; // Pointer for greater elements

    for (let j = left; j < right; j++) {
        if (nums[j] >= pivot) { // Move larger elements to the left
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }

    // Swap pivot into its correct position
    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i; // Pivot index
}

function findKthLargest(nums, k) {
    let n = nums.length;
    return quickSelect(nums, 0, n - 1, k - 1); // k-1 because array is 0-indexed
}

console.log(findKthLargest([3,2,1,5,6,4], 2)); // Output: 5
console.log(findKthLargest([3,2,3,1,2,4,5,5,6], 4)); // Output: 4
console.log(findKthLargest([1,2,3,4,5,6,7,8,9,10], 3)); // Output: 8
console.log(findKthLargest([10,9,8,7,6,5,4,3,2,1], 3)); // Output: 8

/* ===============================

691. Stickers to Spell Word Hard

We are given n different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.



Example 1:

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation:
We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.
Example 2:

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation:
We cannot form the target "basicbasic" from cutting letters from the given stickers.


Constraints:

n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] and target consist of lowercase English letters.



Approach:
The problem asks for the minimum number of stickers needed to form a target string by cutting individual letters. We can use each sticker multiple times. This problem has optimal substructure and overlapping subproblems, suggesting a dynamic programming or memoization approach.

Preprocessing:

Count the frequency of each character in the target string. This will be our goal state.
Filter the stickers array to keep only those stickers that contain at least one character present in the target. Stickers with no relevant characters won't help us form the target. For each valid sticker, pre-calculate the frequency of its characters.
Memoization (Top-Down Dynamic Programming):

We will use a recursive function solve(currentFreq) that takes the current frequency of characters we have collected so far as input.
The base case for the recursion is when the currentFreq has at least the required frequency for every character in the target. In this case, we have formed the target, and the number of stickers used to reach this state is 0.
We use a memo (a Map in JavaScript) to store the results of subproblems (states represented by character frequencies). The key for the memo will be a string representation of the currentFreq array. If we have already computed the result for a given currentFreq, we can directly return it from the memo.
Recursive Step:

Inside the solve function, if the target is not yet formed (i.e., there's at least one character whose current frequency is less than the target frequency), we iterate through each validStickers.
For each validSticker, we simulate using one instance of that sticker. We update the currentFreq by adding the character counts from the sticker.
We then recursively call solve with this new nextFreq. If the recursive call returns a value other than Infinity (meaning a solution was found from that state), we update our minStickerCount by taking the minimum of the current minStickerCount and 1 + count (where count is the result of the recursive call, and 1 represents the sticker we just used).
After trying all validStickers, we store the minStickerCount in the memo for the current freqKey and return it.
Initial Call:

We start the process by calling solve with an initial frequency array of all zeros (representing that we haven't used any stickers yet).
Result Handling:

The final result of the solve function will be the minimum number of stickers needed. If the solve function returns Infinity, it means it's impossible to form the target, so we return -1.
Time Complexity:
Let T be the length of the target string, and S be the number of unique characters in the alphabet (26 in this case).
The state of our DP is represented by the frequency of each character we have collected so far. In the worst case, the frequency of each character can go up to the frequency in the target. The number of possible states could be roughly proportional to the product of (target frequency of each character + 1). However, a tighter bound is harder to determine precisely due to the dependencies.
For each state, we iterate through all the validStickers (at most n). For each sticker, we do a constant amount of work (updating the frequency array).
The number of reachable states can be large, but memoization helps us avoid recomputing them. In the worst case, the number of unique character frequency profiles we might encounter can be significant, potentially exponential in the length of the target.
However, given the constraints (target length <= 15), the number of reachable states might be manageable with memoization.
A rough upper bound on the number of states could be something like (T+1) ^ S
 , where T is the maximum length of the target and S is the alphabet size (26). For each state, we iterate through at most n stickers.
Therefore, the time complexity is roughly O(n⋅(number of states)). The exact number of states is hard to pin down precisely but is bounded by something related to the combinations of character counts up to the target frequencies. In the worst case, this could be exponential in the length of the target.
Space Complexity:
targetFreq: O(S), where S is the size of the alphabet (26).
validStickers: In the worst case, it can contain all n stickers, and each sticker's frequency array is of size S, so O(n⋅S).
memo: The size of the memo is equal to the number of unique states we encounter. In the worst case, this could also be related to the combinations of character counts up to the target frequencies, potentially exponential in the length of the target. The value stored for each state is a constant.
Recursion call stack: In the worst case, the depth of the recursion could be related to the length of the target.
Overall, the space complexity is dominated by the memo and validStickers, which can be significant but is crucial for the efficiency gained through memoization. A rough upper bound on the space complexity could also be related to the number of states, potentially exponential in the length of the target in the worst case. However, in practice, with memoization, we only store the results for the states we actually reach.
*/

function minStickers(stickers, target) {
  const n = stickers.length;
  const targetFreq = new Array(26).fill(0);
  for (const char of target) {
    targetFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }

  const validStickers = [];
  for (const sticker of stickers) {
    const stickerFreq = new Array(26).fill(0);
    for (const char of sticker) {
      stickerFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    // Check if the sticker has any letter that is present in the target
    if (stickerFreq.some((count, i) => count > 0 && targetFreq[i] > 0)) {
      validStickers.push(stickerFreq);
    }
  }

  if (validStickers.length === 0) {
    return -1; // No sticker can contribute to the target
  }

  const memo = new Map();

  function solve(currentFreq) {
    const freqKey = currentFreq.join(',');
    if (memo.has(freqKey)) {
      return memo.get(freqKey);
    }

    let remaining = false;
    for (let i = 0; i < 26; i++) {
      if (currentFreq[i] < targetFreq[i]) {
        remaining = true;
        break;
      }
    }

    if (!remaining) {
      return 0; // Target is formed
    }

    let minStickerCount = Infinity;

    for (const stickerFreq of validStickers) {
      const nextFreq = [...currentFreq];
      let canUse = false;
      for (let i = 0; i < 26; i++) {
        if (stickerFreq[i] > 0 && currentFreq[i] < targetFreq[i]) {
          nextFreq[i] += stickerFreq[i];
          canUse = true;
        }
      }

      if (canUse) {
        const count = solve(nextFreq);
        if (count !== Infinity) {
          minStickerCount = Math.min(minStickerCount, 1 + count);
        }
      }
    }

    memo.set(freqKey, minStickerCount);
    return minStickerCount;
  }

  const initialFreq = new Array(26).fill(0);
  const result = solve(initialFreq);

  return result === Infinity ? -1 : result;
}

console.log(minStickers(["with","example","science"], "thehat")); // Output: 3
console.log(minStickers(["notice","possible"], "basicbasic")); // Output: -1
console.log(minStickers(["these","guess","about","garden","him"], "atom")); // Output: 2


/* =================================

346. Moving Average from Data Stream Easy

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.


Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3


Constraints:

1 <= size <= 1000
-10^5 <= val <= 10^5
At most 104 calls will be made to next.

Here's a clean JavaScript implementation of the MovingAverage class using a queue to maintain the window and an ongoing sum to keep track of the average efficiently

Time Complexity:
constructor(size): The constructor performs constant time operations (initialization of variables). Therefore, its time complexity is O(1).

next(val): O(1) – Constant time operations (push, shift, add, subtract)

push(val) takes O(1) on average (amortized).
The if condition checks the window size, which is a constant time operation.
shift() operation on an array takes O(k) time in the worst case, where k is the current size of the window. However, since the window size is at most size, this is bounded by O(size).
The remaining operations (addition, subtraction, division) are constant time O(1).
Considering the constraints where at most 10<sup>4</sup> calls to next will be made, and in each call, shift() might take up to O(size), the overall complexity over multiple calls could be a concern if shift() was frequently called on a large window. However, the problem asks for the complexity of a single next operation. In that context, the dominant operation, in the worst case when the window is full and we need to remove an element, is shift(), which is O(size).
However, if we consider using a data structure that allows O(1) removal from the front (like a doubly linked list or a circular buffer with indices), the next operation could be optimized to O(1). Given the array implementation, the worst-case time complexity of a single next operation is O(size) due to the potential shift() operation.

Amortized Analysis: If we consider the total cost over m calls to next, where m can be up to 10<sup>4</sup>, each element is added and removed from the array at most once. Therefore, the total cost of shift() operations over all calls would be O(m), leading to an amortized time complexity of O(1) per next operation.

Space Complexity: O(size)
The window array stores at most size elements. Therefore, the space complexity is O(size), as the memory used by the window grows linearly with the window size.
The sum and size variables take constant space, O(1).
Thus, the overall space complexity of the MovingAverage class is O(size).
*/

class MovingAverage {
  constructor(size) {
    this.size = size;
    this.queue = [];
    this.sum = 0;
  }

  next(val) {
    this.queue.push(val);
    this.sum += val;

    if (this.queue.length > this.size) {
      this.sum -= this.queue.shift();
    }

    return this.sum / this.queue.length;
  }
}


const movingAverage = new MovingAverage(3);
console.log(movingAverage.next(1));   // 1.0
console.log(movingAverage.next(10));  // (1 + 10) / 2 = 5.5
console.log(movingAverage.next(3));   // (1 + 10 + 3) / 3 = 4.66667
console.log(movingAverage.next(5));   // (10 + 3 + 5) / 3 = 6.0

/*
Let's rewrite the MovingAverage class using a circular queue implementation with pointers to avoid using shift() (which is O(n)). This keeps everything at O(1) time and space.
*/
class MovingAverage {
  constructor(size) {
    this.size = size;
    this.buffer = new Array(size);
    this.start = 0;
    this.count = 0;
    this.sum = 0;
  }

  next(val) {
    if (this.count < this.size) {
      this.count++;
    } else {
      this.sum -= this.buffer[this.start];
      this.start = (this.start + 1) % this.size;
    }

    const idx = (this.start + this.count - 1) % this.size;
    this.buffer[idx] = val;
    this.sum += val;

    return this.sum / this.count;
  }
}

const movingAverage = new MovingAverage(3);
console.log(movingAverage.next(1));   // 1.0
console.log(movingAverage.next(10));  // 5.5
console.log(movingAverage.next(3));   // 4.66667
console.log(movingAverage.next(5));   // 6.0

/* ============================

71. Simplify Path Medium

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

A single period '.' represents the current directory.
A double period '..' represents the previous/parent directory.
Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.
The simplified canonical path should follow these rules:

The path must start with a single slash '/'.
Directories within the path must be separated by exactly one slash '/'.
The path must not end with a slash '/', unless it is the root directory.
The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.
Return the simplified canonical path.



Example 1:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

Example 2:

Input: path = "/home//foo/"

Output: "/home/foo"

Explanation:

Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = "/home/user/Documents/../Pictures"

Output: "/home/user/Pictures"

Explanation:

A double period ".." refers to the directory up a level (the parent directory).

Example 4:

Input: path = "/../"

Output: "/"

Explanation:

Going one level up from the root directory is not possible.

Example 5:

Input: path = "/.../a/../b/c/../d/./"

Output: "/.../b/d"

Explanation:

"..." is a valid name for a directory in this problem.



Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.



To simplify a Unix-style path, we simulate navigation through directories using a stack:

🔧 Approach:
Split the path by '/'.

Traverse each part:

If it's '' or '.': skip it.

If it's '..': pop the top of the stack if it's not empty.

Otherwise: push the part to the stack (it's a valid directory name).

Join the stack with '/' and prepend a '/' to form the canonical path.

📊 Complexity Analysis:
Time Complexity: O(n) — where n is the length of the path string (we split and traverse once).

Space Complexity: O(m) — for the stack, where m is the number of valid path components.

*/

function simplifyPath(path) {
  const parts = path.split('/');
  const stack = [];

  for (const part of parts) {
    if (part === '' || part === '.') {
      continue;
    } else if (part === '..') {
      if (stack.length > 0) {
        stack.pop();
      }
    } else {
      stack.push(part);
    }
  }

  return '/' + stack.join('/');
}

console.log(simplifyPath("/home/"));                       // "/home"
console.log(simplifyPath("/home//foo/"));                  // "/home/foo"
console.log(simplifyPath("/home/user/Documents/../Pictures")); // "/home/user/Pictures"
console.log(simplifyPath("/../"));                         // "/"
console.log(simplifyPath("/.../a/../b/c/../d/./"));        // "/.../b/d"


/* ===========================
791 Custom Sort String Medium

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = "cba", s = "abcd"

Output: "cbad"

Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Example 2:

Input: order = "bcafg", s = "abcd"

Output: "bcad"

Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.

Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

Constraints:

1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.


To solve this problem, the goal is to reorder the characters of s such that any character that appears in order respects the ordering defined by order. Characters not in order can appear anywhere in the result.

✅ Approach:
Count the frequency of each character in s.

Go through order, and for each character, if it's in s, append it as many times as it appears.

Append the remaining characters (those not in order) to the end.

📊 Complexity:
Time: O(n + m), where n = s.length and m = order.length

Space: O(n) for the frequency map



*/

function customSortString(order, s) {
  const count = {}; // Count characters in s

  // Count frequency of each character in s
  for (let ch of s) {
    count[ch] = (count[ch] || 0) + 1;
  }

  let result = "";

  // Append characters in the order specified by 'order'
  for (let ch of order) {
    if (count[ch]) {
      for (let i = 0; i < count[ch]; i++) {
        result += ch;
      }
      delete count[ch]; // remove to avoid reprocessing
    }
  }

  // Append remaining characters not in 'order'
  for (let ch in count) {
    for (let i = 0; i < count[ch]; i++) {
      result += ch;
    }
  }

  return result;
}




function customSortString(order, s) {
  const sFreq = new Map();
  for (const char of s) {
    sFreq.set(char, (sFreq.get(char) || 0) + 1);
  }

  let result = '';

  for (const char of order) {
    if (sFreq.has(char)) {
      const count = sFreq.get(char);
      for (let i = 0; i < count; i++) {
        result += char;
      }
      sFreq.delete(char);
    }
  }

  for (const [char, freq] of sFreq) {
    for (let i = 0; i < freq; i++) {
      result += char;
    }
  }

  return result;
}

console.log(customSortString("cba", "abcd"));   // "cbad", "cbda", "dcba", etc.
console.log(customSortString("bcafg", "abcd")); // "bcad", "cbad", "bcda", etc.



/* ===========================

426 Convert Binary Search Tree to Sorted Doubly Linked List Medium

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.



Example 1:



Input: root = [4,2,5,1,3]
      4
     / \
    2   5
   / \
  1   3


Output: [1,2,3,4,5]

        _______________________
       ^                       |
HEAD-> 1 <-> 2 <-> 3 <-> 4 <-> 5
       ^                       |
       |_______________________|


Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

    2
   / \
  1   3


Input: root = [2,1,3]

Output: [1,2,3]
        ____________
       ↑           ↓
HEAD-> 1 <-> 2 <-> 3
        ↖_________↙

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
All the values of the tree are unique.


Approach:
The key idea is to perform an Inorder Traversal of the Binary Search Tree (BST). In an Inorder Traversal, we visit the left subtree, then the current node, and finally the right subtree. For a BST, an Inorder Traversal visits the nodes in ascending order of their values. This ordered sequence of nodes is exactly what we need for our sorted doubly-linked list.

We will maintain two pointers during the traversal: head and prev.

head: This pointer will store the first node encountered in the Inorder Traversal, which will be the smallest element in the BST and hence the head of our sorted circular doubly-linked list. It is initialized to null.

prev: This pointer will keep track of the previously visited node during the traversal. This allows us to establish the right (successor) and left (predecessor) connections between consecutive nodes in the sorted order. It is also initialized to null.

The inorderTraversal function works as follows:

Base Case: If the current node is null, we return.

Recursive Left Subtree: We recursively call inorderTraversal on the node.left to process the left subtree first.

Process Current Node:

If prev is null, it means we are visiting the very first node in the Inorder Traversal. This node is the smallest element, so we set head = node.
If prev is not null, it means we have already visited a node. We need to establish the doubly-linked list connections:
Set the right pointer of the prev node to the current node (prev.right = node).
Set the left pointer of the current node to the prev node (node.left = prev).
After establishing the connections (or setting the head), we update prev to the current node so that in the next step, this current node will be the prev node for the next visited node.
Recursive Right Subtree: We recursively call inorderTraversal on the node.right to process the right subtree.

After the inorderTraversal is complete, the head pointer will be pointing to the smallest element of the BST, and all the nodes will be connected in a sorted doubly-linked list using their left and right pointers.

Finally, to make the list circular, we need to connect the last node (which prev will be pointing to after the traversal) with the first node (head):

Set the left pointer of the head to the prev node (head.left = prev).
Set the right pointer of the prev node to the head node (prev.right = head).
We then return the head pointer, which points to the smallest element of the sorted circular doubly-linked list.

Time Complexity:
The inorderTraversal function visits each node in the BST exactly once. Therefore, the time complexity is O(N), where N is the number of nodes in the BST. The operations performed at each node (comparisons, pointer assignments) take constant time. The final step of making the list circular also takes constant time.

Space Complexity:
The space complexity is determined by the recursion stack used during the Inorder Traversal. In the worst case (a skewed tree), the depth of the recursion can be equal to the number of nodes, leading to a space complexity of O(N). In the best case (a balanced tree), the depth of the recursion would be O(log N), so the space complexity would be O(log N). Since the problem statement doesn't guarantee a balanced tree, we should consider the worst-case scenario. The space used for the head and prev pointers is constant, O(1). Therefore, the overall space complexity is O(N).

The transformation is done in place because we are reusing the existing left and right pointers of the tree nodes to form the predecessor and successor pointers of the doubly-linked list without allocating any significant extra space for new nodes.

*/


/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
function treeToDoublyList(root) {
  if (!root) {
    return null;
  }

  let head = null;
  let prev = null;

  function inorderTraversal(node) {
    if (!node) {
      return;
    }

    inorderTraversal(node.left);

    if (!prev) {
      // First node encountered in inorder traversal is the head of the list
      head = node;
    } else {
      // Set up the doubly linked list connections
      prev.right = node;
      node.left = prev;
    }
    prev = node;

    inorderTraversal(node.right);
  }

  inorderTraversal(root);

  // Make the list circular
  if (head && prev) {
    head.left = prev;
    prev.right = head;
  }

  return head;
}

// Helper function to create a TreeNode (for testing)
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

// Example 1:
const root1 = new TreeNode(4);
root1.left = new TreeNode(2);
root1.right = new TreeNode(5);
root1.left.left = new TreeNode(1);
root1.left.right = new TreeNode(3);
const result1 = treeToDoublyList(root1);
let current1 = result1;
const output1 = [];
if (current1) {
  output1.push(current1.val);
  current1 = current1.right;
  while (current1 && current1 !== result1) {
    output1.push(current1.val);
    current1 = current1.right;
  }
}
console.log("Example 1 Output:", output1); // Expected: [1, 2, 3, 4, 5]

// Example 2:
const root2 = new TreeNode(2);
root2.left = new TreeNode(1);
root2.right = new TreeNode(3);
const result2 = treeToDoublyList(root2);
let current2 = result2;
const output2 = [];
if (current2) {
  output2.push(current2.val);
  current2 = current2.right;
  while (current2 && current2 !== result2) {
    output2.push(current2.val);
    current2 = current2.right;
  }
}
console.log("Example 2 Output:", output2); // Expected: [1, 2, 3]



/*
To convert a Binary Search Tree (BST) to a sorted circular doubly-linked list in place, we can use in-order traversal which visits nodes in sorted order.

During the traversal, we'll:

Keep track of the previous node visited (prev)

Link the prev.right to current node, and current.left to prev

At the end, link the head and tail to make it circular

✅ Key Requirements:
Must be in-place

Use left as prev, and right as next

Final list is circular

✅ Time & Space Complexity
Time: O(n), since we visit each node once

Space: O(h) = O(log n) for balanced tree due to recursion stack

*/

function treeToDoublyList(root) {
  if (!root) return null;

  let first = null; // Head of the list
  let last = null;  // Tail (previous node)

  function dfs(node) {
    if (!node) return;

    dfs(node.left);

    if (last) {
      // Link previous node (last) with current node
      last.right = node;
      node.left = last;
    } else {
      // First node visited is the smallest
      first = node;
    }

    last = node;

    dfs(node.right);
  }

  dfs(root);

  // Close the circular doubly linked list
  first.left = last;
  last.right = first;

  return first;
}

let head = treeToDoublyList(root);
let curr = head;
let result = [];
do {
  result.push(curr.val);
  curr = curr.right;
} while (curr !== head);
console.log(result); // Should print sorted values

/* =================================

function insert(head, insertVal) {
  const newNode = { val: insertVal, next: null };

  if (!head) {
    newNode.next = newNode;
    return newNode;
  }

  let curr = head;

  while (true) {
    let next = curr.next;

    const inOrder = curr.val <= insertVal && insertVal <= next.val;
    const isRotationPoint = curr.val > next.val;

    if (
      inOrder ||
      (isRotationPoint && (insertVal >= curr.val || insertVal <= next.val)) ||
      next === head // full loop, no suitable place
    ) {
      curr.next = newNode;
      newNode.next = next;
      break;
    }

    curr = curr.next;
  }

  return head;
}

// Helper to build and print circular list (for test/debug purposes)
function createCircularList(values) {
  if (!values.length) return null;
  const nodes = values.map(val => ({ val, next: null }));
  for (let i = 0; i < nodes.length; i++) {
    nodes[i].next = nodes[(i + 1) % nodes.length];
  }
  return nodes[0]; // return any node
}
function printCircularList(head, count = 10) {
  let result = [];
  let curr = head;
  while (count-- && curr) {
    result.push(curr.val);
    curr = curr.next;
    if (curr === head) break;
  }
  console.log(result);
}

// Example:
let head = createCircularList([3, 4, 1]);
head = insert(head, 2);
printCircularList(head); // Output might be: [3, 4, 1, 2]

VM3368:50 (4) [3, 4, 1, 2]
undefined
let head2 = createCircularList([1]);
head2 = insert(head2, 0);
printCircularList(head2);  // Output might be: [1, 0]

/* ============================================
708. Insert into a Sorted Circular Linked List Medium

Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.



Example 1:
Input: head = [3,4,1], insertVal = 2

1____
↑    ↓
4 <- 3 <- HEAD

Output: [3,4,1,2]

1 -> 2
↑    ↓
4 <- 3 <- HEAD

Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.



Example 2:

Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.
Example 3:

Input: head = [1], insertVal = 0
Output: [1,0]


Constraints:

The number of nodes in the list is in the range [0, 5 * 104].
-106 <= Node.val, insertVal <= 106

✅ Key Concepts
The list is circular, so the last node points back to the first.

The list is sorted in non-descending order.

You may be given any node (not necessarily the smallest).

The inserted value should be placed in the correct order.

You must handle:

Empty list

Single-node list

Normal insertion

Rotation point (where max wraps around to min)

✅ Time & Space Complexity
Time Complexity: O(n) — You may need to traverse all nodes once

Space Complexity: O(1) — No extra space used except new node
*/

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

function insert(head, insertVal) {
  const newNode = new Node(insertVal);

  // Case 1: Empty list
  if (!head) {
    newNode.next = newNode;
    return newNode;
  }

  let curr = head;

  while (true) {
    const next = curr.next;

    const inBetween = curr.val <= insertVal && insertVal <= next.val;
    const atRotation = curr.val > next.val;

    // Case 2: Normal place between two nodes
    // Case 3: At rotation point (insertVal is new min or new max)
    if (
      inBetween ||
      (atRotation && (insertVal >= curr.val || insertVal <= next.val)) ||
      next === head // Case 4: Made full loop with no match (all elements are equal or no place found)
    ) {
      curr.next = newNode;
      newNode.next = next;
      break;
    }

    curr = next;
  }

  return head;
}


// Helper to create a circular list from array
function createCircularList(arr) {
  if (!arr.length) return null;
  const nodes = arr.map(val => ({ val, next: null }));
  for (let i = 0; i < nodes.length; i++) {
    nodes[i].next = nodes[(i + 1) % nodes.length];
  }
  return nodes[0]; // return reference to any node
}

// Helper to print limited number of circular list elements
function printCircularList(head, limit = 10) {
  const result = [];
  let curr = head;
  while (limit-- && curr) {
    result.push(curr.val);
    curr = curr.next;
    if (curr === head) break;
  }
  console.log(result);
}

// Test case:
let head = createCircularList([3, 4, 1]);
head = insert(head, 2);
printCircularList(head); // Output: [3, 4, 1, 2] or rotation variant




/**
 * // Definition for a Node.
 * function Node(val, next) {
 * this.val = val;
 * this.next = next;
 * };
 */

/**
 * @param {Node} head
 * @param {number} insertVal
 * @return {Node}
 */
function insert(head, insertVal) {
    const newNode = new Node(insertVal);

    if (!head) {
        newNode.next = newNode;
        return newNode;
    }

    let current = head;

    while (true) {
        const nextNode = current.next;

        // Case 1: Insertion in the middle of the sorted list
        if ((current.val <= insertVal && insertVal <= nextNode.val) ||
            // Case 2: Insertion at the end of the sorted list (wrapping around)
            (current.val > nextNode.val && (insertVal >= current.val || insertVal <= nextNode.val)) ||
            // Case 3: List with a single node
            current.next === head) {
            newNode.next = nextNode;
            current.next = newNode;
            return head;
        }

        current = nextNode;

        // Safety break to avoid infinite loop in case of all equal values (though the problem states non-descending)
        if (current === head) {
            newNode.next = nextNode;
            current.next = newNode;
            return head;
        }
    }
}

/*
Approach:
Handle Empty List:

If the given head is null, it means the list is empty. In this case, we create a new node with the insertVal, make its next pointer point to itself to form a single-node circular list, and return this new node as the head.

Handle Non-Empty List:

Create a new node newNode with the given insertVal.

Initialize a pointer current to the head of the list.

Iterate through the circular linked list using a while (true) loop. We will break out of this loop when we find the correct insertion point.

In each iteration, get the nextNode (i.e., current.next).

We need to consider three main scenarios for insertion:

Case 1: Insertion in the middle of the sorted list:

If the insertVal is greater than or equal to the current node's value (current.val <= insertVal) and less than or equal to the next node's value (insertVal <= nextNode.val), then the newNode should be inserted between current and nextNode.

We set newNode.next = nextNode and current.next = newNode.

Since the original head reference should be returned, we return head.

Case 2: Insertion at the end of the sorted list (wrapping around):

This case occurs when the sorted circular list has a "break point" where the values decrease (e.g., 3 -> 4 -> 1). If the insertVal needs to be inserted at the end (before the wrap-around) or at the beginning (after the wrap-around), this condition handles it.

If current.val is greater than nextNode.val (indicating the wrap-around), and either insertVal is greater than or equal to current.val (inserting at the end) or insertVal is less than or equal to nextNode.val (inserting at the beginning), then newNode should be inserted between current and nextNode.

We set newNode.next = nextNode and current.next = newNode.

Return head.

Case 3: List with a single node:

If current.next is equal to head, it means the list has only one node. In this case, the newNode should be inserted after this single node.

We set newNode.next = nextNode (which is head) and current.next = newNode.

Return head.

Move the current pointer to the nextNode (current = nextNode) to continue traversing the list.

Include a safety break condition (if (current === head)) to handle cases where all values in the list are the same. In such a scenario, the insertVal can be inserted at any point, and this condition ensures we don't get into an infinite loop.

Time Complexity:
In the worst case, we might need to traverse the entire circular linked list once to find the correct insertion point. This happens when the insertVal is either the new minimum or the new maximum and needs to be inserted at the wrap-around point.

Therefore, the time complexity is O(N), where N is the number of nodes in the circular linked list.

Space Complexity:
We are creating only one new node for the insertVal.

The rest of the operations involve pointer manipulations and do not require additional data structures that scale with the input size.

Therefore, the space complexity is O(1).
*/

/* ========================================================================================
986. Interval List Intersections Medium

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].


Example 1:


Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []


Constraints:

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1
*/



/**
 * @param {number[][]} firstList
 * @param {number[][]} secondList
 * @return {number[][]}
 */
function intervalIntersection(firstList, secondList) {
    let i = 0;
    let j = 0;
    const result = [];

    while (i < firstList.length && j < secondList.length) {
        const [start1, end1] = firstList[i];
        const [start2, end2] = secondList[j];

        const low = Math.max(start1, start2);
        const high = Math.min(end1, end2);

        if (low <= high) {
            result.push([low, high]);
        }

        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }

    return result;
}

// Usage Examples:

// Example 1:
const firstList1 = [[0, 2], [5, 10], [13, 23], [24, 25]];
const secondList1 = [[1, 5], [8, 12], [15, 24], [25, 26]];
const result1 = intervalIntersection(firstList1, secondList1);
console.log("Example 1:", result1); // Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

// Example 2:
const firstList2 = [[1, 3], [5, 9]];
const secondList2 = [];
const result2 = intervalIntersection(firstList2, secondList2);
console.log("Example 2:", result2); // Output: []

// Example 3:
const firstList3 = [[1, 4], [7, 9], [11, 15]];
const secondList3 = [[2, 5], [6, 8], [10, 20]];
const result3 = intervalIntersection(firstList3, secondList3);
console.log("Example 3:", result3); // Output: [[2, 4], [6, 8], [10, 15]]

// Example 4: Overlapping intervals
const firstList4 = [[0, 5]];
const secondList4 = [[0, 5]];
const result4 = intervalIntersection(firstList4, secondList4);
console.log("Example 4:", result4); // Output: [[0, 5]]

// Example 5: No intersection
const firstList5 = [[1, 2]];
const secondList5 = [[3, 4]];
const result5 = intervalIntersection(firstList5, secondList5);
console.log("Example 5:", result5);  // Output: []