Algorithm - LeetCode Problems 18

Problem 1614. Maximum Nesting Depth of the Parentheses

• A string is a valid parentheses string (denoted VPS) if it meets one of the following:

  • It is an empty string "", or a single character not equal to "(" or ")",
  • It can be written as AB (A concatenated with B), where A and B are VPS's, or
  • It can be written as (A), where A is a VPS.

• We can similarly define the nesting depth depth(S) of any VPS S as follows:

  • depth("") = 0
  • depth(C) = 0, where C is a string with a single character not equal to "(" or ")".
  • depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's.
  • depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

• For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

• Given a VPS represented as string s, return the nesting depth of s.

Examples

• Example 1:

  • Input: s = "(1+(2*3)+((8)/4))+1"
  • Output: 3
  • Explanation: Digit 8 is inside of 3 nested parentheses in the string.

• Example 2:

  • Input: s = "(1)+((2))+(((3)))"
  • Output: 3

Constraints

• 1 <= s.length <= 100
• s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
• It is guaranteed that parentheses expression s is a VPS.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function(s) {
    const openBracket = '(';
    const closeBracket = ')';
    let bracketCount = 0;
    let maxDepth = 0;

    for (const letter of s) {
        if (letter === openBracket) {
            bracketCount++;
        } 
        if (letter === closeBracket) {
            maxDepth = Math.max(maxDepth, bracketCount);
            bracketCount--;
        }
    }

    return maxDepth;
};

Problem 78. Subsets

• Given an integer array nums of unique elements, return all possible subsets (the power set).

• The solution set must not contain duplicate subsets. Return the solution in any order.

Examples

• Example 1:

  • Input: nums = [1,2,3]
  • Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

• Example 2:

  • Input: nums = [0]
  • Output: [[],[0]]

Constraints

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const dfs = (index, subArr, result, visited) => {
        if (subArr.length > nums.length || index > nums.length) {
            return;
        }
        result.push([...subArr]);

        for (let i = index; i < nums.length; i++) {
            const number = nums[i];
            if (!visited[number]) {
                subArr.push(number);
                visited[number] = true;    
                dfs(i, subArr, result, visited);
                subArr.pop();
                visited[number] = false;
            }
        }

        return result;
    };

    return dfs(0, [], [], []);
};

Problem 561. Array Partition

• Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Examples

• Example 1:

  • Input: nums = [1,4,3,2]
  • Output: 4
  • Explanation: All possible pairings (ignoring the ordering of elements) are:
    1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
    2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
    3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
    • So the maximum possible sum is 4.

• Example 2:

  • Input: nums = [6,2,6,5,1,2]
  • Output: 9
  • Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints

• 1 <= n <= 10^4
• nums.length == 2 * n
• -10^4 <= nums[i] <= 10^4

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    nums.sort((a, b) => b - a);
    let sum = 0;
    
    for (let i = 0; i < nums.length - 1; i += 2) {
        const minNumber = Math.min(nums[i], nums[i+1]);
        sum += minNumber;
    }

    return sum;
};

Solution 1561. Maximum Number of Coins You Can Get

• There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

  • In each step, you will choose any 3 piles of coins (not necessarily consecutive).
  • Of your choice, Alice will pick the pile with the maximum number of coins.
  • You will pick the next pile with the maximum number of coins.
  • Your friend Bob will pick the last pile.
  • Repeat until there are no more piles of coins.

• Given an array of integers piles where piles[i] is the number of coins in the ith pile.

• Return the maximum number of coins that you can have.

Examples

• Example 1:

  • Input: piles = [2,4,1,2,7,8]
  • Output: 9
  • Explanation:
    • Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
    • Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
      The maximum number of coins which you can have are: 7 + 2 = 9.
    • On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

• Example 2:

  • Input: piles = [2,4,5]
  • Output: 4

• Example 3:

  • Input: piles = [9,8,7,6,5,1,2,3,4]
  • Output: 18

Constraints

• 3 <= piles.length <= 10^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

Solution

/**
 * @param {number[]} piles
 * @return {number}
 */
var maxCoins = function(piles) {
    piles.sort((a, b) => b - a);
    const length = piles.length; 
    const quotient = length / 3;
    let sum = 0;

    for (let i = 1; i < length - quotient; i += 2) {
        sum += piles[i];
    }

    return sum;
};