DSs

/* 1143. Longest Common Subsequence. Medium

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

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.
*/
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];
}


/* 1151. Minimum Swaps to Group All 1's Together. Medium.
minSwaps([1,0,1,0,1]) = 1
minSwaps([0,0,0,1,0]) = 0
minSwaps([1,0,1,0,1,0,0,1,1,0,1]) = 3

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.
*/
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;
}

/* 1492. The kth Factor of n. Medium
kthFactor(12, 3) = 3
kthFactor(7, 2) = 7
kthFactor(4, 4) = -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.
*/
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;
}



/* 1676. Lowest Common Ancestor of a Binary Tree IV. Medium.
lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4],[4,7]) = 2
lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4],[1]) = 1
lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4],[7,6,2,4]) = 5

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).
*/
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);
}

/* 2268. Minimum Number of Keypresses. Medium
Time Complexity:
Counting frequencies: O(n), where n is the length of the string.
Sorting frequencies: O(26 * log(26)) = O(1), since the alphabet size is fixed at 26 (i.e., there are at most 26 unique characters).
Computing keypresses: O(26) = O(1) due to the fixed size of the alphabet.
Thus, the overall time complexity is O(n), where n is the length of the string.

Space Complexity:
The space complexity is O(1) since we only store a fixed number of character frequencies (26 at most for lowercase English letters).
console.log(minimumKeypresses("abcdefghijkl"));  // Output: 15
console.log(minimumKeypresses("apple"));         // Output: 5
*/
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;
}

/* 2297. Jump Game VIII. Medium
Time Complexity:
O(n): Each index is processed once. The deque operations (insertions and deletions) are amortized O(1), so overall complexity is linear.
Space Complexity:
O(n): The space complexity is primarily due to the DP array and the deque, both of which can store up to n elements. Therefore, the overall space complexity is O(n).

console.log(minCost([3,2,4,4,1], [3,7,6,4,2])); // Output: 8
console.log(minCost([0,1,2], [1,1,1])); // Output: 2
*/
function minCost(nums, costs) {
    const n = nums.length;
    const dp = Array(n).fill(Infinity);
    dp[0] = 0; // Starting at index 0 costs nothing

    let deque = []; // This will store the indices for potential jumps

    for (let i = 0; i < n; i++) {
        // Remove elements from the deque that can't be a valid jump for current index i
        while (deque.length > 0 && (
            (nums[i] >= nums[deque[deque.length - 1]] && nums[i] < nums[deque[0]]) ||
            (nums[i] < nums[deque[deque.length - 1]] && nums[i] >= nums[deque[0]])
        )) {
            deque.pop();
        }

        // Calculate the minimum cost to reach index i
        if (deque.length > 0) {
            dp[i] = Math.min(dp[i], dp[deque[0]] + costs[i]);
        }

        // Add current index to the deque
        deque.push(i);
    }

    return dp[n - 1];
}


/* 2323. Find Minimum Time to Finish All Jobs II. Medium
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.

console.log(minDays([5,2,4], [1,7,5])); // Output: 2
console.log(minDays([3,18,15,9], [6,5,1,3])); // Output: 3
*/
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;
}





/* 2330. Valid Palindrome IV. Medium
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.

console.log(canBePalindrome("abcdba")); // Output: true
console.log(canBePalindrome("aa"));      // Output: true
console.log(canBePalindrome("abcdef"));  // Output: 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;
}


/* 2340. Minimum Adjacent Swaps to Make a Valid Array. Medium
console.log(minimumSwaps([3, 4, 5, 5, 3, 1])); // Output: 6
console.log(minimumSwaps([9]));               // Output: 0

Time Complexity:
O(n): The solution involves a single traversal of the array to find the indices of the smallest and largest elements.
Space Complexity:
O(1): The solution only uses a constant amount of extra space for the indices and counters.
This approach is efficient and scales well even for large input arrays.
*/
function minimumSwaps(nums) {
    let n = nums.length;

    // Finding the leftmost smallest element and its index
    let minIndex = 0;
    for (let i = 1; i < n; i++) {
        if (nums[i] < nums[minIndex]) {
            minIndex = i;
        }
    }

    // Finding the rightmost largest element and its index
    let maxIndex = 0;
    for (let i = 1; i < n; i++) {
        if (nums[i] >= nums[maxIndex]) {
            maxIndex = i;
        }
    }

    // If minIndex is before maxIndex, the swaps don't interfere
    if (minIndex < maxIndex) {
        return minIndex + (n - 1 - maxIndex);
    } else {
        // If minIndex is after maxIndex, subtract 1 to account for the overlap
        return minIndex + (n - 1 - maxIndex) - 1;
    }
}





/* 2405. Optimal Partition of String. Medium
minPartitions("abacaba") = 4
minPartitions("ssssss") = 6

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.
*/
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;
}

/* 2408. Design SQL. Medium

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. */
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];
    }
}


/* 2422. Merge Operations to Turn Array Into a Palindrome. Medium
minOperations([4,3,2,1,2,3,1]) = 2
minOperations([1,2,3,4]) = 3

Time Complexity:
O(n): The solution uses a two-pointer approach and each element is processed at most once, where n is the length of the array.
Space Complexity:
O(1): The solution operates in-place, modifying the original array, and only uses a few extra variables for the pointers and the operations count.
*/
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;
}