DS

/* 1143. Longest Common Subsequence. Medium

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.



Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

To solve the problem of finding the longest common subsequence (LCS) between two strings text1 and text2, we can use dynamic programming (DP). The idea is to build a 2D DP table where dp[i][j] represents the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

Dynamic Programming Approach:
Initialization:

Create a 2D array dp of size (m+1) x (n+1) where m is the length of text1 and n is the length of text2.
Initialize all elements of dp to 0. The idea is that if either string is empty, the LCS is 0.
Filling the DP Table:

Iterate through each character of text1 and text2.
If the characters match (text1[i-1] == text2[j-1]), then dp[i][j] = dp[i-1][j-1] + 1.
If the characters don't match, then dp[i][j] = max(dp[i-1][j], dp[i][j-1]) required for cases like console.log(longestCommonSubsequence("abcde", "acbe")); // Output: 3
Result:

The value at dp[m][n] will give us the length of the LCS of text1 and text2.
*/

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;

    // Create a 2D dp array with (m+1) x (n+1) dimensions and fill it with 0
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // Fill the dp array, skip first row and column initialized with 0
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // check char at index - 1 as we loop from 1, not zero
            if (text1[i - 1] === text2[j - 1]) {
                // If characters match dp value is 1 more than diagonally previous element
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // If characters not match dp value is max of top and left element
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // The answer is the bottom-right cell of the dp array
    return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3
/*
dp
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]
*/
console.log(longestCommonSubsequence("abc", "abc")); // Output: 3
console.log(longestCommonSubsequence("abc", "def")); // Output: 0

/*
Explanation:
"abcde" and "ace": The LCS is "ace" with length 3.
"abc" and "abc": The LCS is "abc" with length 3.
"abc" and "def": There is no common subsequence, so the output is 0.
Time Complexity:
O(m * n): We need to fill in a table of size m * n where m is the length of text1 and n is the length of text2.
Space Complexity:
O(m * n): We need to store the DP table of size (m+1) x (n+1).
This approach efficiently computes the length of the longest common subsequence using dynamic programming.
1143 */



/*
1151. Minimum Swaps to Group All 1's Together. Medium

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.



Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.
Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.
Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].


Constraints:

1 <= data.length <= 105
data[i] is either 0 or 1.

To solve the problem of finding the minimum number of swaps required to group all 1’s in a binary array together, we can use the sliding window approach. The key idea is to determine the size of the window (which is the total number of 1's in the array) and then find the window with the maximum number of 1's. The minimum number of swaps required is the difference between the window size and the maximum number of 1's found in any window of that size.

*/


function minSwaps(data) {
    const totalOnes = data.reduce((sum, val) => sum + val, 0);

    if (totalOnes === 0) return 0; // No 1's in the array, no swaps needed

    let maxOnesInWindow = 0;
    let currentOnes = 0;
    let left = 0;

    // Sliding window to find the max number of 1's in a window of size `totalOnes`
    for (let right = 0; right < data.length; right++) {
        currentOnes += data[right];

        // Once the window reaches the size of totalOnes
        if (right - left + 1 > totalOnes) {
            currentOnes -= data[left];
            left++;
        }

        maxOnesInWindow = Math.max(maxOnesInWindow, currentOnes);
    }

    // The minimum number of swaps required is the difference between totalOnes and maxOnesInWindow
    return totalOnes - maxOnesInWindow;
}

console.log(minSwaps([1,0,1,0,1]));   // 1
console.log(minSwaps([0,0,0,1,0]));   // 0
console.log(minSwaps([1,0,1,0,1,0,0,1,1,0,1]));   // 3


/*
To solve the problem of finding the minimum number of swaps required to group all 1’s in a binary array together, we can use the sliding window approach. The key idea is to determine the size of the window (which is the total number of 1's in the array) and then find the window with the maximum number of 1's. The minimum number of swaps required is the difference between the window size and the maximum number of 1's found in any window of that size.

Explanation:
Calculate total number of 1's (totalOnes): This determines the size of the sliding window.
Initialize maxOnesInWindow and currentOnes:
maxOnesInWindow keeps track of the maximum number of 1's found in any window of size totalOnes.
currentOnes tracks the number of 1's in the current window.
Sliding Window:
Iterate through the array using a right pointer (right).
Add the current element to currentOnes.
If the window size exceeds totalOnes, move the left pointer (left) to the right, reducing the window size to totalOnes.
Update maxOnesInWindow with the maximum number of 1's found in the current window.
Calculate the minimum swaps: The minimum number of swaps needed to group all 1's together is totalOnes - maxOnesInWindow.
Time Complexity:
O(n): We traverse the array once with a sliding window, where n is the length of the array.
Space Complexity:
O(1): Only a few variables are used, and no extra space is required relative to the input size.
This approach ensures that the solution is efficient even for large arrays.

1151 */







/*

1475. Final Prices With a Special Discount in a Shop. Easy

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.



Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.
Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:

Input: prices = [10,1,1,6]
Output: [9,0,1,6]


Constraints:

1 <= prices.length <= 500
1 <= prices[i] <= 1000

Here's the solution for the problem in JavaScript. The approach is straightforward: for each item, check the subsequent items to find the first eligible discount and adjust the price accordingly.

Optimized Solution Using a Stack
To improve efficiency, we can use a monotonic stack:

Traverse the prices array.
Use a stack to keep track of indices of prices in a way that ensures the first smaller or equal value is easily accessible.
Whenever a smaller or equal price is found for a price at the top of the stack, apply the discount and remove the index from the stack.


*/



function finalPrices(prices) {
    const stack = [];
    const n = prices.length;
    const result = [...prices]; // Initialize result array with original prices

    for (let i = 0; i < n; i++) {
        // Check the stack for discounts
        while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {
            const index = stack.pop();
            result[index] -= prices[i];
        }
        // Add the current index to the stack
        stack.push(i);
    }

    return result;
}

// Example usage:
console.log(finalPrices([8, 4, 6, 2, 3])); // Output: [4, 2, 4, 2, 3]
console.log(finalPrices([1, 2, 3, 4, 5])); // Output: [1, 2, 3, 4, 5]
console.log(finalPrices([10, 1, 1, 6]));   // Output: [9, 0, 1, 6]


/*


Explanation:
Initialization:

Use a stack to track indices of prices for which a discount hasn't been found yet.
The result array is initialized as a copy of prices.
Stack Processing:

For each price, check the top of the stack:
If the price at the current index (prices[i]) is less than or equal to the price at the index stored in the stack, a discount is applied, and the index is removed from the stack.
Push the current index onto the stack.
Output:

After processing all prices, result contains the final prices with discounts applied.
Complexity:
Time Complexity:
O(n) because each price is pushed to and popped from the stack exactly once.
Space Complexity:
O(n) for the stack in the worst case when no discounts are found.
This is efficient and works well within the given constraints.



*/





/*

1492. The kth Factor of n. Medium

You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.



Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.


Constraints:

1 <= k <= n <= 1000


Follow up:

Could you solve this problem in less than O(n) complexity?

*/

// A-I

function kthFactor(n, k) {
    let factors = [];
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            factors.push(i);
        }
    }
    return factors.length >= k ? factors[k - 1] : -1;
}

console.log(kthFactor(12, 3));   // 3
console.log(kthFactor(7, 2));   // 7
console.log(kthFactor(4, 4));   // -1

/*
Explanation:
Initialize an empty array factors: This will store all factors of n.
Loop through numbers from 1 to n: For each number i, check if i is a factor of n by using the modulo operation (n % i === 0).
Store the factor: If i is a factor, add it to the factors array.
Return the k-th factor: After the loop, check if the number of factors is at least k. If so, return the k-th factor (which is at index k-1 in the zero-indexed array). If not, return -1.
Time Complexity:
The loop runs from 1 to n, hence the time complexity is O(n).
Space Complexity:
The space complexity is O(n) in the worst case because we store all factors of n in an array.
This approach ensures that we efficiently find and return the k-th factor, or -1 if there are fewer than k factors.
1492 */



/*

1676. Lowest Common Ancestor of a Binary Tree IV. Medium

Given the root of a binary tree and an array of TreeNode objects nodes, return the lowest common ancestor (LCA) of all the nodes in nodes. All the nodes will exist in the tree, and all values of the tree's nodes are unique.

Extending the definition of LCA on Wikipedia: "The lowest common ancestor of n nodes p1, p2, ..., pn in a binary tree T is the lowest node that has every pi as a descendant (where we allow a node to be a descendant of itself) for every valid i". A descendant of a node x is a node y that is on the path from node x to some leaf node.



Example 1:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.
Example 2:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
Output: 1
Explanation: The lowest common ancestor of a single node is the node itself.

Example 3:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output: 5
Explanation: The lowest common ancestor of the nodes 7, 6, 2, and 4 is node 5.


Constraints:

The number of nodes in the tree is in the range [1, 104].
-109 <= Node.val <= 109
All Node.val are unique.
All nodes[i] will exist in the tree.
All nodes[i] are distinct.

To solve the problem of finding the lowest common ancestor (LCA) of multiple nodes in a binary tree, we can use a modified depth-first search (DFS) approach. The idea is to recursively traverse the tree and find the LCA based on the given nodes.

Here's the JavaScript solution:

*/

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

function lowestCommonAncestor(root, nodes) {
    const nodeSet = new Set(nodes);

    function dfs(node) {
        if (!node) return null;
        if (nodeSet.has(node)) return node;

        const left = dfs(node.left);
        const right = dfs(node.right);

        if (left && right) return node;
        return left ? left : right;
    }

    return dfs(root);
}

/*

Explanation:
TreeNode class: This defines the structure of a tree node.
lowestCommonAncestor function:
Convert the nodes array into a Set for quick lookup.
Define a helper function dfs that performs a depth-first search.
In dfs, if the current node is null, return null.
If the current node is in the nodeSet, return the current node.
Recursively call dfs on the left and right children.
If both left and right recursive calls return non-null values, the current node is the LCA.
If only one of the recursive calls returns a non-null value, return that value (it means the subtree rooted at that child contains all the nodes in nodes).
Call dfs with the root of the tree.
Time Complexity:
The time complexity is O(n), where n is the number of nodes in the tree. This is because we potentially visit every node in the tree once during the DFS traversal.
Space Complexity:
The space complexity is O(h), where h is the height of the tree. This is the maximum depth of the recursion stack. In the worst case, the height of the tree can be n (in the case of a skewed tree), making the space complexity O(n). In a balanced tree, the height would be O(log n).

To test the above solution, you'll need a few helper functions to construct the binary tree from the input array and to convert nodes from the array format to TreeNode objects.

Here's a complete example, including helper functions to build the tree and run the test:

*/

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

// Helper function to insert nodes in the binary tree in level order
function insertLevelOrder(arr, root, i) {
    if (i < arr.length) {
        let temp = new TreeNode(arr[i]);
        root = temp;

        root.left = insertLevelOrder(arr, root.left, 2 * i + 1);
        root.right = insertLevelOrder(arr, root.right, 2 * i + 2);
    }
    return root;
}

// Helper function to find a TreeNode by value
function findNode(root, val) {
    if (!root) return null;
    if (root.val === val) return root;
    let leftResult = findNode(root.left, val);
    if (leftResult) return leftResult;
    return findNode(root.right, val);
}

// Function to test the lowestCommonAncestor function
function testLowestCommonAncestor() {
    let rootArray = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4];
    let nodesValues = [7, 6, 2, 4];

    let root = insertLevelOrder(rootArray, null, 0);
    let nodes = nodesValues.map(val => findNode(root, val));

    let lca = lowestCommonAncestor(root, nodes);
    console.log(lca ? lca.val : null);
}

function lowestCommonAncestor(root, nodes) {
    const nodeSet = new Set(nodes);

    function dfs(node) {
        if (!node) return null;
        if (nodeSet.has(node)) return node;

        const left = dfs(node.left);
        const right = dfs(node.right);

        if (left && right) return node;
        return left ? left : right;
    }

    return dfs(root);
}

// Run the test
testLowestCommonAncestor();


/*

Explanation:
TreeNode class: Defines the structure of a tree node.
insertLevelOrder function: A helper function to construct the binary tree from the given array representation. This function inserts nodes into the tree level by level.
findNode function: A helper function to find a node in the tree by its value. This is used to convert node values into TreeNode objects.
testLowestCommonAncestor function: Sets up the test by creating the tree and nodes, calls the lowestCommonAncestor function, and prints the result.
lowestCommonAncestor function: The implementation of the LCA function as discussed earlier.
Run the test: Calls testLowestCommonAncestor to execute the test.
Time Complexity:
insertLevelOrder: O(n) for building the tree, where n is the number of elements in the array.
findNode: O(n) in the worst case for finding each node in the tree.
lowestCommonAncestor: O(n) for finding the LCA.
Space Complexity:
insertLevelOrder: O(h), where h is the height of the tree due to the recursion stack.
findNode: O(h) for each call due to the recursion stack.
lowestCommonAncestor: O(h) due to the recursion stack.
This setup and these functions will allow you to test the lowestCommonAncestor function with the given inputs and verify its correctness.

1676 */


/* 2182. Construct String With Repeat Limit. Medium

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.



Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.
Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.


Constraints:

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

Approach
Count Frequencies: Count the frequency of each character in the string s.
Sort Characters: Sort the characters in descending lexicographical order.
Build Result String:
Append the current largest character to the result string up to repeatLimit times.
If the current largest character is exhausted or cannot be added due to the repeatLimit, temporarily add the next largest character.
Backtrack to the current largest character if it still has remaining frequency.

*/

function repeatLimitedString(s, repeatLimit) {
    // Step 1: Count frequencies
    const freq = new Array(26).fill(0);
    for (const char of s) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    // Step 2: Sort characters in descending lexicographical order
    const result = [];
    const chars = [];
    for (let i = 25; i >= 0; i--) {
        if (freq[i] > 0) chars.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
    }

    // Step 3: Build result string
    while (chars.length > 0) {
        let used = 0; // Count of how many times the current char is used
        const currentChar = chars[0]; // Largest available character

        // Use the largest character up to repeatLimit times
        while (used < repeatLimit && freq[currentChar.charCodeAt(0) - 'a'.charCodeAt(0)] > 0) {
            result.push(currentChar);
            freq[currentChar.charCodeAt(0) - 'a'.charCodeAt(0)]--;
            used++;
        }

        // If the largest character still has remaining frequency
        if (freq[currentChar.charCodeAt(0) - 'a'.charCodeAt(0)] > 0) {
            if (chars.length === 1) break; // No other character to add, stop
            const nextChar = chars[1]; // Next largest character
            result.push(nextChar);
            freq[nextChar.charCodeAt(0) - 'a'.charCodeAt(0)]--;
            if (freq[nextChar.charCodeAt(0) - 'a'.charCodeAt(0)] === 0) chars.splice(1, 1); // Remove if exhausted
        } else {
            // Remove the current largest character if it's exhausted
            chars.shift();
        }
    }

    return result.join('');
}

// Example usage
console.log(repeatLimitedString("cczazcc", 3)); // Output: "zzcccac"
console.log(repeatLimitedString("aababab", 2)); // Output: "bbabaa"


/*

Explanation of Example 1
Input: s = "cczazcc", repeatLimit = 3

Frequency count: {'a': 1, 'c': 4, 'z': 2}
Sorted characters: ['z', 'c', 'a']
Construction steps:
Add z twice: zz.
Add c three times: zzccc.
Add a once: zzccca.
Add c once: zzcccac.
Result: "zzcccac"
Complexity Analysis
Time Complexity:

Counting frequencies: O(n)
Sorting characters: O(26⋅log26)→O(1) (since there are at most 26 characters).
Building the result string: O(n)
Overall: O(n)
Space Complexity:

Frequency array:  O(26)→O(1)
Result string:  O(n)
Overall: O(n)
*/


/* 2268. Minimum Number of Keypresses. Medium

You have a keypad with 9 buttons, numbered from 1 to 9, each mapped to lowercase English letters. You can choose which characters each button is matched to as long as:

All 26 lowercase English letters are mapped to.
Each character is mapped to by exactly 1 button.
Each button maps to at most 3 characters.
To type the first character matched to a button, you press the button once. To type the second character, you press the button twice, and so on.

Given a string s, return the minimum number of keypresses needed to type s using your keypad.

Note that the characters mapped to by each button, and the order they are mapped in cannot be changed.



Example 1:

Keyboard: {
1:["a" , "b", "c"],
2: ["d", "f"],
3: ["e" , "i", "j"],
4:["g" , "q", "s"],
5: ["l" , "k", "x"],
6: ["p" , "t", "u"],
7:["m" , "n", "r"],
8: ["h" , "y", "z"],
9: ["o" , "v", "w"],
}

Input: s = "apple"
Output: 5
Explanation: One optimal way to setup your keypad is shown above.
Type 'a' by pressing button 1 once.
Type 'p' by pressing button 6 once.
Type 'p' by pressing button 6 once.
Type 'l' by pressing button 5 once.
Type 'e' by pressing button 3 once.
A total of 5 button presses are needed, so return 5.

Example 2:

Keyboard: {
1:["a" , "j", "s"],
2: ["b", "k", "t"],
3: ["c" , "l", "u"],
4:["d" , "m", "v"],
5: ["e" , "n", "w"],
6: ["f" , "o", "x"],
7:["g" , "p", "y"],
8: ["h" , "q", "z"],
9: ["i" , "r"],
}

Input: s = "abcdefghijkl"
Output: 15
Explanation: One optimal way to setup your keypad is shown above.
The letters 'a' to 'i' can each be typed by pressing a button once.
Type 'j' by pressing button 1 twice.
Type 'k' by pressing button 2 twice.
Type 'l' by pressing button 3 twice.
A total of 15 button presses are needed, so return 15.


Constraints:

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

To solve the problem of determining the minimum number of keypresses required to type a given string on a keypad where each button is mapped to up to three characters, we can approach the problem using a greedy algorithm.
*/

function minimumKeypresses(s) {

    // Create an array to count the occurrences of each character.
    const frequencyCounter = new Array(26).fill(0);

    // Increment the frequency count for each character in the string.
    for (const character of s) {
        frequencyCounter[character.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    // Sort the frequency array in non-increasing order.
    frequencyCounter.sort((a, b) => b - a);

    // Initialize the answer to 0, which will hold the minimum keypresses required.
    let minimumKeyPresses = 0;

    /* The number of keystrokes needed to type a character is determined by its  position in the sorted frequency array. The most frequent characters take 1 keystroke, the next 9 take 2 keystrokes, and so on */
    let keystrokes = 1; // Start with 1 keystroke for the most frequent characters.


    // Loop through the frequency array to calculate the total number of keypresses.
    for (let i = 0; i < 26; ++i) {
        // Calculate the keypresses required for the current character frequency and add it to the minimumKeyPresses total.
        minimumKeyPresses += keystrokes * frequencyCounter[i];
        // Every 9 characters, the number of keypresses increases by 1, since we are basing our calculation on a 9-key keyboard layout
        if ((i + 1) % 9 === 0) {
            keystrokes++;
        }
    }

    return minimumKeyPresses;
}

// Example usage:
console.log(minimumKeypresses("apple"));         // Output: 5
console.log(minimumKeypresses("abcdefghijkl"));  // Output: 15


/*
Explanation:
Frequency Calculation: The frequency of each character is computed using an array of size 26, where each index corresponds to a letter ('a' = 0, 'b' = 1, ..., 'z' = 25).
Sorting: The characters are sorted by frequency, placing the most frequent ones at the beginning.
Keystroke Calculation: For each character, depending on its position in the sorted list, it is assigned either 1, 2, or 3 keystrokes based on how many characters are already assigned. Every 9 characters increase the number of keystrokes needed by 1.

Time Complexity:
Frequency Counting: Iterating over the string s to count character frequencies takes O(n), where n is the length of the string s.
Sorting Frequencies: Sorting the frequency array of size 26 (since there are 26 lowercase English letters) takes O(26 log 26), which simplifies to O(1) because the number of English letters is constant.
Calculating Keystrokes: Iterating over the frequency array (which has 26 elements) takes O(26), which simplifies to O(1) because it's a constant-sized array.
Thus, the overall time complexity is O(n), where n is the length of the input string.(since sorting a constant-sized array is negligible)

Space Complexity:
Frequency Array: We use a fixed-size array of 26 integers to store the frequency of each character. This takes O(26) space, which simplifies to O(1).
Input Storage: The input string s is already provided, so no additional space is used beyond storing the input.
Thus, the space complexity is O(1) because the frequency array size is fixed, and no additional space is used based on the input size.(constant space usage)
2268 */


/* 2297. Jump Game VIII. Medium

You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where i < j if:

nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, or
nums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j.
You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i.

Return the minimum cost to jump to the index n - 1.



Example 1:

Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
Output: 8
Explanation: You start at index 0.
- Jump to index 2 with a cost of costs[2] = 6.
- Jump to index 4 with a cost of costs[4] = 2.
The total cost is 8. It can be proven that 8 is the minimum cost needed.
Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4.
These have a total cost of 9 and 12, respectively.
Example 2:

Input: nums = [0,1,2], costs = [1,1,1]
Output: 2
Explanation: Start at index 0.
- Jump to index 1 with a cost of costs[1] = 1.
- Jump to index 2 with a cost of costs[2] = 1.
The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums[0] <= nums[1].


Constraints:

n == nums.length == costs.length
1 <= n <= 105
0 <= nums[i], costs[i] <= 105

To solve the problem efficiently, we use a dynamic programming (DP) approach combined with monotonic stacks to maintain the constraints on jumping conditions.

Approach:
Define DP State:

Let dp[i] represent the minimum cost to reach index i.
Initialize dp[0] = 0 (starting point) and dp[i] = Infinity for all i > 0.
Monotonic Stacks:

Use two stacks:
increasingStack: Maintains indices where nums is in a non-decreasing order.
decreasingStack: Maintains indices where nums is in a strictly decreasing order.
These stacks help efficiently find valid jumps for each index while respecting the constraints.
Iterate Over the Array:

For each index i, check both stacks:
Pop from the top of the stack if the jump is valid and update dp[i].
Push the current index onto the stack for future jumps.
Return Result:

The result is dp[n - 1].

*/

function minCostJump(nums, costs) {
    const n = nums.length;
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;

    const increasingStack = [];
    const decreasingStack = [];

    for (let i = 0; i < n; i++) {
        // Process increasing stack for valid jumps
        while (
            increasingStack.length > 0 &&
            nums[increasingStack[increasingStack.length - 1]] <= nums[i]
        ) {
            const j = increasingStack.pop();
            dp[i] = Math.min(dp[i], dp[j] + costs[i]);
        }

        // Process decreasing stack for valid jumps
        while (
            decreasingStack.length > 0 &&
            nums[decreasingStack[decreasingStack.length - 1]] > nums[i]
        ) {
            const j = decreasingStack.pop();
            dp[i] = Math.min(dp[i], dp[j] + costs[i]);
        }

        // Push current index onto both stacks
        increasingStack.push(i);
        decreasingStack.push(i);
    }

    return dp[n - 1];
}

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


/*
Explanation:
Initialization:

dp[0] = 0: No cost to start at index 0.
dp[i] = Infinity: Assume unreachable until proven otherwise.
Processing Stacks:

For increasingStack:
Ensure valid jumps where nums[j] <= nums[i] and all intermediate values are < nums[j].
For decreasingStack:
Ensure valid jumps where nums[j] > nums[i] and all intermediate values are >= nums[j].
Update DP:

For each valid jump, calculate dp[i] as dp[j] + costs[i] where j is a valid previous index.
Result:

After processing all indices, dp[n - 1] holds the minimum cost to reach the last index.
Complexity:
Time Complexity: O(n):

Each index is pushed and popped from the stack at most once, leading to a linear time complexity.
Space Complexity: O(n):

Space is used for the dp array and the two stacks.
This approach is efficient and works within the constraints (1 <= n <= 10⁵).
2297 */


/* 2323. Find Minimum Time to Finish All Jobs II. Medium

You are given two 0-indexed integer arrays jobs and workers of equal length, where jobs[i] is the amount of time needed to complete the ith job, and workers[j] is the amount of time the jth worker can work each day.

Each job should be assigned to exactly one worker, such that each worker completes exactly one job.

Return the minimum number of days needed to complete all the jobs after assignment.

Example 1:

Input: jobs = [5,2,4], workers = [1,7,5]
Output: 2
Explanation:
- Assign the 2nd worker to the 0th job. It takes them 1 day to finish the job.
- Assign the 0th worker to the 1st job. It takes them 2 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 1 day to finish the job.
It takes 2 days for all the jobs to be completed, so return 2.
It can be proven that 2 days is the minimum number of days needed.
Example 2:

Input: jobs = [3,18,15,9], workers = [6,5,1,3]
Output: 3
Explanation:
- Assign the 2nd worker to the 0th job. It takes them 3 days to finish the job.
- Assign the 0th worker to the 1st job. It takes them 3 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 3 days to finish the job.
- Assign the 3rd worker to the 3rd job. It takes them 3 days to finish the job.
It takes 3 days for all the jobs to be completed, so return 3.
It can be proven that 3 days is the minimum number of days needed.


Constraints:

n == jobs.length == workers.length
1 <= n <= 105
1 <= jobs[i], workers[i] <= 105


To solve this problem, the key idea is to minimize the maximum number of days it takes for any worker to complete their assigned job. Since each job must be assigned to exactly one worker and each worker must be assigned exactly one job, we can approach this by sorting both the jobs and workers arrays, and then pairing the most demanding job with the most capable worker, the second most demanding job with the second most capable worker, and so on. This way, we ensure that we are minimizing the days needed to complete all jobs.

Approach:
Sort the Arrays:

Sort the jobs array in ascending order.
Sort the workers array in ascending order.
Calculate Days Required:

Pair each job with the corresponding worker (since both arrays are sorted, pair jobs[i] with workers[i]).
Calculate the days required for each worker to complete their assigned job, which is Math.ceil(jobs[i] / workers[i]).
Keep track of the maximum days required across all pairs.
Return the Result:

The result is the maximum days calculated in the previous step.

*/

function minDays(jobs, workers) {
    // Sort jobs and workers in ascending order
    jobs.sort((a, b) => a - b);
    workers.sort((a, b) => a - b);

    let maxDays = 0;

    // Pair each job with a worker and calculate the required days
    for (let i = 0; i < jobs.length; i++) {
        const days = Math.ceil(jobs[i] / workers[i]);
        maxDays = Math.max(maxDays, days);
    }

    return maxDays;
}

console.log(minDays([5,2,4], [1,7,5])); // Output: 2
console.log(minDays([3,18,15,9], [6,5,1,3])); // Output: 3

/*
Explanation:
Input: jobs = [5,2,4], workers = [1,7,5]:

After sorting, jobs = [2, 4, 5], workers = [1, 5, 7].
Pairing:
Job 2 with Worker 1 → 2 days
Job 4 with Worker 5 → 1 day
Job 5 with Worker 7 → 1 day
Maximum days = 2, so return 2.
Input: jobs = [3,18,15,9], workers = [6,5,1,3]:

After sorting, jobs = [3, 9, 15, 18], workers = [1, 3, 5, 6].
Pairing:
Job 3 with Worker 1 → 3 days
Job 9 with Worker 3 → 3 days
Job 15 with Worker 5 → 3 days
Job 18 with Worker 6 → 3 days
Maximum days = 3, so return 3.
Time Complexity:
O(n log n): Sorting the jobs and workers arrays takes O(n log n), where n is the length of the array.
O(n): The loop to calculate the required days for each worker is O(n).
Overall, the time complexity is dominated by the sorting step, so it is O(n log n).

Space Complexity:
O(1): The space complexity is constant as we only use a few extra variables, regardless of the input size.
This approach efficiently finds the minimum number of days needed to complete all the jobs by minimizing the maximum days any worker spends on their job.
2323 */


/* 2330. Valid Palindrome IV. Medium

You are given a 0-indexed string s consisting of only lowercase English letters. In one operation, you can change any character of s to any other character.

Return true if you can make s a palindrome after performing exactly one or two operations, or return false otherwise.



Example 1:

Input: s = "abcdba"
Output: true
Explanation: One way to make s a palindrome using 1 operation is:
- Change s[2] to 'd'. Now, s = "abddba".
One operation could be performed to make s a palindrome so return true.
Example 2:

Input: s = "aa"
Output: true
Explanation: One way to make s a palindrome using 2 operations is:
- Change s[0] to 'b'. Now, s = "ba".
- Change s[1] to 'b'. Now, s = "bb".
Two operations could be performed to make s a palindrome so return true.
Example 3:

Input: s = "abcdef"
Output: false
Explanation: It is not possible to make s a palindrome using one or two operations so return false.


Constraints:

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

To solve the problem of determining whether you can make a string s a palindrome with exactly one or two operations, we can use the following approach:

Approach:
Initial Checks:

If the string is already a palindrome, return true because zero operations are also valid.
Count Mismatches:

Compare characters from the start and the end of the string, moving towards the center.
Count the number of positions where characters do not match (mismatches).
Decision Logic:

If the number of mismatches is 0, the string is already a palindrome, so return true.
If the number of mismatches is 1, we can change one character to make the string a palindrome, so return true.
If the number of mismatches is 2, we can change two characters to make the string a palindrome, so return true.
If there are more than 2 mismatches, return false.

*/

function canBePalindrome(s) {
    let mismatchCount = 0;
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) {
            mismatchCount++;
        }
        left++;
        right--;
    }

    // If there are 0, 1, or 2 mismatches, it's possible to make the string a palindrome with 1 or 2 operations
    return mismatchCount <= 2;
}

console.log(canBePalindrome("abcdba")); // Output: true
console.log(canBePalindrome("aa"));      // Output: true
console.log(canBePalindrome("abcdef"));  // Output: false

/*
Explanation:
Input: "abcdba":

Mismatches: 1 (position 2, 'c' vs 'd').
One operation can make it a palindrome ("abddba"), so return true.
Input: "aa":

Mismatches: 0 (already a palindrome).
No changes needed, but even with 2 operations, it remains a palindrome, so return true.
Input: "abcdef":

Mismatches: 3 (positions 0, 1, and 2).
More than 2 mismatches mean it's not possible to make it a palindrome with only 2 operations, so return false.
Time Complexity:
O(n): We traverse the string once from both ends, where n is the length of the string.
Space Complexity:
O(1): We only use a constant amount of extra space for the counters and indices.
This approach efficiently determines if the string can be transformed into a palindrome with one or two operations.

2330 */



/*
2340. Minimum Adjacent Swaps to Make a Valid Array. Medium

You are given a 0-indexed integer array nums.

Swaps of adjacent elements are able to be performed on nums.

A valid array meets the following conditions:

The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.
Return the minimum swaps required to make nums a valid array.



Example 1:

Input: nums = [3,4,5,5,3,1]
Output: 6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum swaps required to make a valid array.
Example 2:
Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0.


Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 105

To solve this problem, we can break it into two main steps:

Identify the positions of the smallest and largest elements in the array:
The smallest element should move to the leftmost position.
The largest element should move to the rightmost position.
Count the swaps required to move these elements:
Move the smallest element from its current position to the beginning.
Move the largest element from its current position to the end, taking into account the position of the smallest element if the two overlap.

Approach
Traverse the array to find:
The first occurrence of the smallest element (minIndex).
The last occurrence of the largest element (maxIndex).
Calculate the number of swaps:
If minIndex < maxIndex, the swaps for the smallest and largest elements do not interfere.
Otherwise, reduce the total swaps by one, as the largest element needs to account for the already swapped smallest element.
*/

function minimumSwaps(nums) {
    const n = nums.length;

    // Find the first occurrence of the smallest element
    let minIndex = 0;
    for (let i = 1; i < n; i++) {
        if (nums[i] < nums[minIndex]) {
            minIndex = i;
        }
    }

    // Find the last occurrence of the largest element
    let maxIndex = n - 1;
    for (let i = n - 2; i >= 0; i--) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }

    // Calculate swaps
    let swaps = minIndex + (n - 1 - maxIndex);

    // Adjust if smallest is to the right of the largest
    if (minIndex > maxIndex) {
        swaps -= 1;
    }

    return swaps;
}

// Example usage
console.log(minimumSwaps([3, 4, 5, 5, 3, 1])); // Output: 6
console.log(minimumSwaps([9]));                // Output: 0


/*
Explanation of Example 1:
Input: [3, 4, 5, 5, 3, 1]

Smallest Element: 1 at index 5.
Largest Element: 5 at index 3.
Swaps:
Move 1 from index 5 to index 0 (5 swaps).
Move 5 from index 3 to index 5 (1 swap).
Total swaps = 6.
Complexity Analysis
Time Complexity: O(n)
One pass to find minIndex and maxIndex.
Calculation of swaps is done in constant time.
Space Complexity: O(1)
We use a constant amount of extra space.
2340 */






/*

2405. Optimal Partition of String. Medium

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.



Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.
Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").


Constraints:

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

*/

// A-I

function minPartitions(s) {
    let partitions = 0;
    let seen = new Set();

    for (let char of s) {
        if (seen.has(char)) {
            partitions++;
            seen.clear();
        }
        seen.add(char);
    }

    return partitions + 1;
}


// Example usage:
console.log(minPartitions("abacaba")); // Output: 4
console.log(minPartitions("ssssss"));           // Output: 6

/*

Explanation:
Initialize partitions to 0: This variable will count the number of partitions.
Create a Set named seen: This set will store the characters in the current substring to ensure uniqueness.
Iterate through each character char in the string s:
If char is already in the seen set, it means a new partition is needed because we encountered a duplicate character.
Increment the partitions count and clear the seen set to start a new substring.
Add the current character char to the seen set.
Return partitions + 1: Add one to account for the last substring which would not have triggered the partitions++ inside the loop.
Time Complexity:
The time complexity is O(n), where n is the length of the string s, since we are iterating through the string once.
Space Complexity:
The space complexity is O(1) for the partitions counter.
The space complexity is O(26) = O(1) for the seen set since it can only store up to 26 unique lowercase English letters.

2405 */



/*
2408. Design SQL. Medium

You are given n tables represented with two arrays names and columns, where names[i] is the name of the ith table and columns[i] is the number of columns of the ith table.

You should be able to perform the following operations:

Insert a row in a specific table. Each row you insert has an id. The id is assigned using an auto-increment method where the id of the first inserted row is 1, and the id of each other row inserted into the same table is the id of the last inserted row (even if it was deleted) plus one.
Delete a row from a specific table. Note that deleting a row does not affect the id of the next inserted row.
Select a specific cell from any table and return its value.
Implement the SQL class:

SQL(String[] names, int[] columns) Creates the n tables.
void insertRow(String name, String[] row) Adds a row to the table name. It is guaranteed that the table will exist, and the size of the array row is equal to the number of columns in the table.
void deleteRow(String name, int rowId) Removes the row rowId from the table name. It is guaranteed that the table and row will exist.
String selectCell(String name, int rowId, int columnId) Returns the value of the cell in the row rowId and the column columnId from the table name.


Example 1:

Input
["SQL", "insertRow", "selectCell", "insertRow", "deleteRow", "selectCell"]
[[["one", "two", "three"], [2, 3, 1]], ["two", ["first", "second", "third"]], ["two", 1, 3], ["two", ["fourth", "fifth", "sixth"]], ["two", 1], ["two", 2, 2]]
Output
[null, null, "third", null, null, "fifth"]

Explanation
SQL sql = new SQL(["one", "two", "three"], [2, 3, 1]); // creates three tables.
sql.insertRow("two", ["first", "second", "third"]); // adds a row to the table "two". Its id is 1.
sql.selectCell("two", 1, 3); // return "third", finds the value of the third column in the row with id 1 of the table "two".
sql.insertRow("two", ["fourth", "fifth", "sixth"]); // adds another row to the table "two". Its id is 2.
sql.deleteRow("two", 1); // deletes the first row of the table "two". Note that the second row will still have the id 2.
sql.selectCell("two", 2, 2); // return "fifth", finds the value of the second column in the row with id 2 of the table "two".


Constraints:

n == names.length == columns.length
1 <= n <= 104
1 <= names[i].length, row[i].length, name.length <= 20
names[i], row[i], and name consist of lowercase English letters.
1 <= columns[i] <= 100
All the strings of names are distinct.
name exists in the array names.
row.length equals the number of columns in the chosen table.
rowId and columnId will be valid.
At most 250 calls will be made to insertRow and deleteRow.
At most 104 calls will be made to selectCell.

To solve this problem, we need to implement a class that simulates a simple SQL-like table system. This involves creating tables, inserting rows with auto-incrementing IDs, deleting rows, and selecting specific cells from the table.

Here's how we can implement the SQL class in JavaScript:
*/
class SQL {
    constructor(names, columns) {
        this.tables = {};

        // Initialize the tables with their respective columns
        for (let i = 0; i < names.length; i++) {
            this.tables[names[i]] = {
                columns: columns[i],
                rows: {},
                nextId: 1
            };
        }
    }

    insertRow(name, row) {
        const table = this.tables[name];
        table.rows[table.nextId] = row;
        table.nextId++;
    }

    deleteRow(name, rowId) {
        const table = this.tables[name];
        delete table.rows[rowId];
    }

    selectCell(name, rowId, columnId) {
        const table = this.tables[name];
        return table.rows[rowId][columnId - 1];
    }
}

/*
Explanation:
Constructor (SQL):

Initializes a dictionary (tables) to store each table's metadata.
For each table, stores the number of columns (columns), a dictionary for storing rows (rows), and a counter for the next ID (nextId).
Insert a Row (insertRow):

Finds the table by name.
Inserts the row into the rows dictionary with the current nextId as the key.
Increments the nextId counter for the next insertion.
Delete a Row (deleteRow):

Finds the table by name.
Deletes the row by rowId from the rows dictionary.
Select a Cell (selectCell):

Finds the table by name.
Accesses the row using rowId and returns the value from the specified columnId.
Note that columnId - 1 is used to convert the 1-based index to a 0-based index.
Time Complexity:
Insert Row: O(1) for each insert since we're simply adding a row to the dictionary.
Delete Row: O(1) for each delete since we're removing a key from the dictionary.
Select Cell: O(1) for each cell selection since we're directly accessing an element in a dictionary and an array.
Space Complexity:
O(n + r), where n is the number of tables and r is the total number of rows across all tables. The space is used for storing the tables, rows, and their metadata.
This solution is efficient, with constant time operations for inserting, deleting, and selecting rows, making it scalable for large inputs within the given constraints.
2408 */


/*
2422. Merge Operations to Turn Array Into a Palindrome. Medium

You are given an array nums consisting of positive integers.

You can perform the following operation on the array any number of times:

Choose any two adjacent elements and replace them with their sum.
For example, if nums = [1,2,3,1], you can apply one operation to make it [1,5,1].
Return the minimum number of operations needed to turn the array into a palindrome.

Example 1:

Input: nums = [4,3,2,1,2,3,1]
Output: 2
Explanation: We can turn the array into a palindrome in 2 operations as follows:
- Apply the operation on the fourth and fifth element of the array, nums becomes equal to [4,3,2,3,3,1].
- Apply the operation on the fifth and sixth element of the array, nums becomes equal to [4,3,2,3,4].
The array [4,3,2,3,4] is a palindrome.
It can be shown that 2 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We do the operation 3 times in any position, we obtain the array [10] at the end which is a palindrome.


Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 106


To solve this problem, we need to turn the array into a palindrome by performing the given operation (replacing two adjacent elements with their sum) the minimum number of times.

The key observation is that, to form a palindrome, the elements on the left and right ends of the array need to be equal. If they aren't, we can either:

Merge the left element with its neighbor (by summing them).
Merge the right element with its neighbor.
This effectively reduces the problem size by one, and we continue this process until the entire array becomes a palindrome.

*/

function minOperations(nums) {
    let left = 0;
    let right = nums.length - 1;
    let operations = 0;

    while (left < right) {
        if (nums[left] === nums[right]) {
            left++;
            right--;
        } else if (nums[left] < nums[right]) {
            nums[left + 1] += nums[left];
            left++;
            operations++;
        } else {
            nums[right - 1] += nums[right];
            right--;
            operations++;
        }
    }

    return operations;
}

/*

2422 /*

/* 3264

3264. Merge Operations to Turn Array Into a Palindrome. Medium

You are given an integer array nums, an integer k, and an integer multiplier.

You need to perform k operations on nums. In each operation:

Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
Replace the selected minimum value x with x * multiplier.
Return an integer array denoting the final state of nums after performing all k operations.



Example 1:

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

Output: [8,4,6,5,6]

Explanation:

Operation   Result
After operation 1   [2, 2, 3, 5, 6]
After operation 2   [4, 2, 3, 5, 6]
After operation 3   [4, 4, 3, 5, 6]
After operation 4   [4, 4, 6, 5, 6]
After operation 5   [8, 4, 6, 5, 6]
Example 2:

Input: nums = [1,2], k = 3, multiplier = 4

Output: [16,8]

Explanation:

Operation   Result
After operation 1   [4, 2]
After operation 2   [4, 8]
After operation 3   [16, 8]


Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 10
1 <= multiplier <= 5

To solve the problem, the solution involves repeatedly finding the minimum value in the nums array and replacing it with its multiplied value x * multiplier for k iterations.

Approach:
Iterate k times:
Find the first occurrence of the minimum value x in the array.
Replace it with x * multiplier.
Return the modified array after k operations.
*/

function performOperations(nums, k, multiplier) {
    for (let i = 0; i < k; i++) {
        // Find the first occurrence of the minimum value in nums
        let minIndex = 0;
        for (let j = 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        // Replace the minimum value with its multiplied value
        nums[minIndex] *= multiplier;
    }
    return nums;
}

// Example usage:
console.log(performOperations([2, 1, 3, 5, 6], 5, 2)); // Output: [8, 4, 6, 5, 6]
console.log(performOperations([1, 2], 3, 4));          // Output: [16, 8]

/*
Explanation:
For each iteration, we identify the index of the smallest element in nums using a loop (minIndex).
Replace the value at minIndex with its multiplied value.
Repeat this process k times.
Complexity:
Time Complexity:
Finding the minimum value takes O(n), where n is the size of nums.
Performing k iterations makes the complexity O(k * n).
Space Complexity:
The solution uses only constant extra space, so the space complexity is O(1).
This is efficient given the constraints (1 <= nums.length <= 100 and 1 <= k <= 10).
*/