Algorithm - LeetCode Problems 13

Problem 278. First Bad Version

• You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

• Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

• You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Examples

• Example 1:

  • Input: n = 5, bad = 4
  • Output: 4
  • Explanation:
    • call isBadVersion(3) -> false
    • call isBadVersion(5) -> true
    • call isBadVersion(4) -> true
    • Then 4 is the first bad version.

• Example 2:

  • Input: n = 1, bad = 1
  • Output: 1

Constraints

• 1 <= bad <= n <= 2^31 - 1

Solution

• for 문을 사용한 풀이

var solution = function(isBadVersion) {
    return function(n) {
        for (let i = 1; i <= n; i++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
    };
};

• Binary Search 알고리즘을 사용한 풀이

var solution = function(isBadVersion) {
    return function(n) {
        let left = 1;
        let right = n;
        let middle;
        let firstBadVersion = n;

        while (left <= right) {
            middle = Math.floor((left + right)/2);
            if (isBadVersion(middle)) {
                firstBadVersion = Math.min(firstBadVersion, middle);
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return firstBadVersion;
    };
};

Problem 2529. Maximum Count of Positive Integer and Negative Integer

• Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

• In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

  • Note that 0 is neither positive nor negative.

Examples

• Example 1:

  • Input: nums = [-2,-1,-1,1,2,3]
  • Output: 3
  • Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.

• Example 2:

  • Input: nums = [-3,-2,-1,0,0,1,2]
  • Output: 3
  • Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.

• Example 3:

  • Input: nums = [5,20,66,1314]
  • Output: 4
  • Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.

Constraints:

• 1 <= nums.length <= 2000
• -2000 <= nums[i] <= 2000
• nums is sorted in a non-decreasing order.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumCount = function(nums) {
    return Math.max(getNegativeCount(nums), getPositiveCount(nums));
};

var getNegativeCount = function(nums) {
    if (nums[0] >= 0) {
        return 0;
    }
  
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const middle = Math.ceil((right+left)/2);
        if (nums[middle] < 0) {
            left = middle;
        } else {
            right = middle - 1;
        }
    }
  
    return left + 1;
}

var getPositiveCount = function(nums) {
    if (nums[nums.length - 1] <= 0) {
        return 0;
    }
  
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const middle = Math.floor((right+ left)/2);
        if (nums[middle] > 0) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
  
    return nums.length - left;
}

Problem 1877. Minimize Maximum Pair Sum in Array

• The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

• For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

• Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

  • Each element of nums is in exactly one pair, and
  • The maximum pair sum is minimized.
  • Return the minimized maximum pair sum after optimally pairing up the elements.

Examples

• Example 1:

  • Input: nums = [3,5,2,3]
  • Output: 7
  • Explanation:
    • The elements can be paired up into pairs (3,3) and (5,2).
    • The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

• Example 2:

  • Input: nums = [3,5,4,2,4,6]
  • Output: 8
  • Explanation:
    • The elements can be paired up into pairs (3,5), (4,4), and (6,2).
    • The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

• n == nums.length
• 2 <= n <= 10^5
• n is even.
• 1 <= nums[i] <= 10^5

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function(nums) {
    const length = nums.length;
    let maxPairSum = 0;

    nums.sort((a, b) => a - b);

    for (let i = 0; i < length/2; i++) {
        const pairSum = nums[i] + nums[length - i - 1];
        maxPairSum = Math.max(maxPairSum, pairSum);
    }

    return maxPairSum;
};