Algorithm - LeetCode Problems 2

Problem 496. Next Greater Element 1

• The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

• You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

• For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

• Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Examples

• Example 1

  • Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
  • Output: [-1,3,-1]
  • Explanation: The next greater element for each value of nums1 is as follows:
    • 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
    • 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
    • 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

• Example 2

  • Input: nums1 = [2,4], nums2 = [1,2,3,4]
  • Output: [3,-1]
  • Explanation: The next greater element for each value of nums1 is as follows:
    • 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
    • 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique.
• All the integers of nums1 also appear in nums2.

Solution

• indexOf를 사용하여 nextNumberIndex를 구한 풀이

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    return nums1.map((number) => {
        let nextNumberIndex = nums2.indexOf(number) + 1;
        while (nextNumberIndex < nums2.length && nums2[nextNumberIndex] < number) {
            nextNumberIndex++;
        }
        return nextNumberIndex >= nums2.length ? -1 : nums2[nextNumberIndex];
    });
};

• stack을 사용한 풀이 (다른 사람 풀이 참고)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const numObj = {};
    const stack = [];

    for (let i = 0; i < nums2.length; i++) {
        let curNumber = nums2[i];

        while (curNumber > stack[stack.length - 1]) {
            let nextNumber = stack.pop();
            numObj[nextNumber] = curNumber;
        }

        stack.push(curNumber);
    }

    return nums1.map((number) => numObj[number] || -1);
};

Problem 442. Find All Duplicates in an Array

• Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

• You must write an algorithm that runs in O(n) time and uses only constant extra space.

Examples

• Example 1:

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

• Example 2:

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

Constraints

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function(nums) {
    const numMap = new Map();
    const answer = [];

    for (const number of nums) {
        if (!numMap.get(number)) {
            numMap.set(number, 1);
        } else {
            numMap.set(number, 2);
            answer.push(number);
        }
    }

    return answer;
};

Problem 383. Ransom Note

• Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

• Each letter in magazine can only be used once in ransomNote.

Examples

• Example 1:

  • Input: ransomNote = "aa", magazine = "ab"
  • Output: false

• Example 2:

  • Input: ransomNote = "aa", magazine = "aab"
  • Output: true

Constraints

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

Solution

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const magazineMap = new Map();
    for (let i = 0; i < magazine.length; i++) {
        const str = magazine[i];
        magazineMap.set(str, (magazineMap.get(str) || 0) + 1);
    }

    for (let i = 0; i < ransomNote.length; i++) {
        const str = ransomNote[i];
        if (!magazineMap.get(str)) {
            return false;
        } else {
            magazineMap.set(str, magazineMap.get(str) - 1);
        }
    }
    return true;
}

Problem 416. Partition Equal Subset Sum

• Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Examples

• Example 1:

  • Input: nums = [1,5,11,5]
  • Output: true
  • Explanation: The array can be partitioned as [1, 5, 5] and [11].

• Example 2:

  • Input: nums = [1,2,3,5]
  • Output: false
  • Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const totalSum = nums.reduce((sum, number) => sum + number, 0);
    if (totalSum % 2 === 1) {
        return false;
    }

    const target = totalSum /2;
    const dp = { 0: true };

    for (let i = 0; i < nums.length; i++) {
        const number = nums[i];
        Object.keys(dp).forEach((element) => {
            let sum = parseInt(element);
            dp[sum + number] = true;
            dp[sum] = true;
        });
    }

    return dp[target] ? true : false;
};

Problem 698. Partition to K Equal Sum Subsets

• Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Examples

• Example 1:

  • Input: nums = [4,3,2,3,5,2,1], k = 4
  • Output: true
  • Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

• Example 2:

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

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 10^4
• The frequency of each element is in the range [1, 4].

Solution

• backtracking을 사용한 풀이

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function(nums, k) {
    const totalSum = nums.reduce((sum, number) => sum + number, 0);
    if (totalSum % k) {
        return false;
    }
    const target = totalSum / k;
    const visited = new Array(nums.length).fill(false);

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

    const backtracking = (index, subsetCount, sum) => {
        if (subsetCount === 0) {
            return true;
        }
      
        if (sum === target) {
            return backtracking(0, subsetCount - 1, 0);
        }

        for (let i = index; i < nums.length; i++) {
            const number = nums[i];
            if (visited[i] || (sum + number > target)) {
                continue;
            }
            visited[i] = true;
            if (backtracking(i + 1, subsetCount, sum + number)) {
                return true;
            }
            visited[i] = false;
        }
      
        return false;
    };
  
    return backtracking(0, k, 0);
};

Problem 503. Next Greater Element II

• Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

• The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Examples

• Example 1:
  • Input: nums = [1,2,1]
  • Output: [2,-1,2]
  • Explanation:
    • The first 1's next greater number is 2;
    • The number 2 can't find next greater number.
    • The second 1's next greater number needs to search circularly, which is also 2.

Constraints:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

Solution

 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {
    const length = nums.length;
    const stack = [];
    const answer = new Array(length).fill(-1);

    for (let i = 0; i < 2 * length; i++) {
        let index = i % length;
        while (stack.length && nums[index] > nums[stack[stack.length - 1]]) {
            answer[stack.pop()] = nums[index];
        }
        stack.push(index);
    }
  
    return answer;
};