Forem: jihyun-j

[Algorithm] 151. Reverse Words in a String

jihyun-j — Wed, 05 Feb 2025 02:58:13 +0000

Description

Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Key Requirements

Remove extra spaces between words and at the beginning/end of the string.
Reverse the order of words (not characters).

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

✔️ My Submission

var reverseWords = function(s) {
    return s.replace(/\s+/g, " ").trim().split(' ').reverse().join(' ');
};

Removed all extra spaces from s using the regular expression /\s+/g with the replace method.
However, this alone did not remove the leading and trailing spaces, so I added the trim method to eliminate them.
Next, I used split(' ') to break the string into an array of words.
Since it’s now an array, I applied the reverse method to rearrange the words in reverse order.
Finally, I used the join(' ') method to convert the array back into a string.

[Algorithm] 1431. Kids With the Greatest Number of Candies

jihyun-j — Fri, 31 Jan 2025 14:22:48 +0000

Description

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

⭐️ Key Requirement

Each kid can receive all extraCandies at once, meaning we check each kid individually.
Compare with the maximum number of candies to see if the kid can have the most after receiving extraCandies.
Return a boolean array, where true means the kid has the greatest number of candies, and false means they do not.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints:

n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

📌 My Submission

/**
 * @param {number[]} candies
 * @param {number} extraCandies
 * @return {boolean[]}
 */
var kidsWithCandies = function(candies, extraCandies) {
    const max = Math.max(...candies)
    let result = []

    for(let i=0; i<candies.length; i++){
        if(candies[i]+extraCandies >= max){
            result.push(true)
        } else {
            result.push(false)
        }
    }
    return result
};

Create an empty array to store the results.
Find the maximum number in the candies array to use as a reference for comparison.
Loop through the candies array and check if candies[i] + extraCandies is greater than or equal to the maximum value.
If candies[i] + extraCandies is greater than or equal to the maximum, push true to the result array; otherwise, push false.
Return the result array.

[Algorithm] 771. Jewels and Stones

jihyun-j — Mon, 27 Jan 2025 06:37:36 +0000

Description

You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Key Requirements of the Problem

Find the characters in the jewels string that are present in the stones string and return the total count of those characters.

Example 1

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints:

1 <= jewels.length, stones.length <= 50
jewels and stones consist of only English letter.
All the characters of jewels are unique.

My Submission 1 — Using the `includes()` Method

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */

var numJewelsInStones = function(jewels, stones) {
    let count = 0
    for(let i=0; i < stones.length; i++){
        if(jewels.includes(stones[i])){
            count++
        }
    }
    return count
};

Initialize the count variable to store the final count of jewels.
Loop through the stones string, and check if each character is present in the jewels string using the includes() method.
If it is included, increment the count variable.
Finally, return the count variable.

This solution has a time complexity of O(m×n), where m is the length of the stones string and n is the length of the jewels string. This is because the includes() method iterates through the jewels string for each character in stones. If the input size increases, this approach becomes inefficient. We need to optimize the solution to reduce the time complexity.

My Submission 2 — Using the `Set()` Method (Hash Table)

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsMap = new Set(jewels)
    let count = 0
    for(let i=0; i < stones.length; i++){
        if(jewelsMap.has(stones[i])) {
            count++
        }
    }
    return count
};

Initialize the count variable to store the final count of jewels.
Create a Set from the jewels string. A Set allows for faster lookups because it uses a hash table internally.
Loop through the stones string, and check if each character exists in the Set using the has() method.
If the character exists, increment the count variable.
Finally, return the count variable.

Why `Set()` is Faster Than `includes()`?

The includes() method checks for a value by iterating through the jewels string one character at a time. This means the time complexity for each check is O(n), where n is the length of the jewels string.

On the other hand, the Set data structure uses a hash table internally. This allows for constant-time O(1) lookups using the has() method. While creating the Set initially takes O(n) time, subsequent lookups are much faster compared to the includes() method.

If you find any mistakes in my post or have a different perspective, feel free to leave a comment below. I always enjoy learning from different viewpoints! 😊 Also, if you liked this post, I'm happy to connect on LinkedIn anytime.

Forem: jihyun-j

[Algorithm] 151. Reverse Words in a String

Description

Key Requirements

Example 1:

Example 2:

Example 3:

✔️ My Submission

[Algorithm] 1431. Kids With the Greatest Number of Candies

Description

⭐️ Key Requirement

Example 1:

Example 2:

Example 3:

Constraints:

📌 My Submission

[Algorithm] 771. Jewels and Stones

Description

Key Requirements of the Problem

Example 1

Example 2

Constraints:

My Submission 1 — Using the includes() Method

My Submission 2 — Using the Set() Method (Hash Table)

Why Set() is Faster Than includes()?

My Submission 1 — Using the `includes()` Method

My Submission 2 — Using the `Set()` Method (Hash Table)

Why `Set()` is Faster Than `includes()`?