LeetCode 75 (II)

Question 151: Reverse Words in a String

Although this question is marked as “medium” difficulty. But it’s relatively simple to solve it with built-in method.

Following is its 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.

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.

Constraints:

• 1 <= s.length <= 104
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

As what I write at the beginning, we can use some cheeky built-in method to solve it with very simple code.

function reverseWords(s: string): string {
    let wordArr = s.split(' ');
    return wordArr.filter(word => word !== '').reverse().join(' ');
};

But it does feel a little bit lazy. So, what else can we do? There’s a lot of way to solve it. We can use queue to solve it, and I think it’s good in terms of reducing space complexity. But I’d like to just loop through the string backward. It’s easy to understand and sits right in the middle of both time and space complexity.

function reverseWords(s: string): string {
    s = s.trim();
    let ln = s.length;
    let out = '';
    let word = '';

    while(ln > 0) {
        ln--;
        if(s[ln] !== ' ') word = s[ln] + word;
        if(s[ln] === ' ' || ln === 0) {
            if(!!word) {
                out = out + (!out ? '' : ' ') + word;
            }
            word = '';
        }
    }
    return out;
};

The steps are as follows:

• trim the string, this is not necessary though.
• Declare a ln variable for the while loop. An out for our answer. And a word to store a complete word.
• Each iteration we subtract the ln by 1.
• If s[ln] is not a space, we prepend to word.
• If s[ln] is a space, means the word is complete. And do remember to check if our ln reaches the end, it also means the word is complete.
• Concatenate the word into out.

Question 238: Product of Array Except Self

This is the one I have no idea how to do it, because I’m terrible in math. So, I’m only going to explain the solution I found.

Description:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

So, the idea behind it uses prefix product and suffix product. What prefix product means, each index is the product of itself and the previous index. So, given an array [1, 2, 3, 4]. Its prefix product would be [1, 2, 6, 24]. And the suffix product is the opposite. With the same array, its suffix product would be [24, 24, 12, 4].

So, how does this help? In the first example case:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

We can get the following prefix and suffix product if we set the empty prefix and suffix as 1.

Prefix product: [1, 1, 2, 6]
Suffix Product: [24, 12, 4, 1]

We can see the product of each index of prefix and suffix product would be the same as our output [24, 12, 8, 6].

With this concept, it should be relatively easy to implement our code.

function productExceptSelf(nums: number[]): number[] {
    const prefix: number[] = new Array(nums.length);
    const suffix: number[] = new Array(nums.length);
    prefix[0] = 1;
    suffix[suffix.length - 1] = 1;

    // populate prefix pr
    for(let i = 1; i < prefix.length; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }
    // populate suffixproducts
    for(let i = suffix.length - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }
    return prefix.map((p, i) => p * suffix[i]);
};

This should already be the acceptable answer with O(n) time.

There’s a follow up question about how to reduce the space complexity to O(1). Which basically means we have to calculate the product in place of our output array, and use a single variable to keep track our suffix product.

function productExceptSelf(nums: number[]): number[] {
    const out: number[] = new Array(nums.length);
    let suffix = 1
    out[0] = 1;

    for(let i = 1; i < out.length; i++) {
        out[i] = out[i - 1] * nums[i - 1];
    }
    for(let i = out.length - 1; i >= 0; i--) {
        out[i] = suffix * out[i];
        suffix *= nums[i];
    }
    return out;
};

We store our prefix product inside out variable. Since it’s our output, it doesn’t count as extra space. The first loop is same, and the second loop we use suffix variable to keep our next suffix product.

Question 334: Increasing Triplet Subsequence

This one annoys me at the first sight. But it’s actually quite simple if think about it.

Description:

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

The steps are as follows:

• Declare two variables first and second with their value as Infinity.
• Compare if n is smaller than our first and replace it accordingly.
• Our if case makes sure it won’t replace second only if n is larger than first.
• Whenever the n pass down to the else case, means n is larger than our first and second. So, we can return true.

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for(let i = 0; i < nums.length; i++) {
        const n = nums[i]
        if(first >= n) {
            first = n;
        } else if (second >= n) {
            second = n
        } else {
            return true;
        }
    }
    return false;
};

Question 443: String Compression

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group’s length is 1, append the character to s.
• Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

I found these pairs well with two pointers. The first pointer as reader and the second pointer as writer.

function compress(chars: string[]): number {
    let p1 = 0, p2 = 0;
    for(; p1 < chars.length;) {
        const char = chars[p1];
        let count = 0;
        
        for(;p1 < chars.length && chars[p1] === char; p1++) { count++ }
        chars[p2++] = char;
        if(count > 1) {
            count.toString().split('').forEach(c => chars[p2++] = c);
        }
    }
    chars.length = p2;
    return chars.length;
};

So, we start with two pointers at the position 0. Store the character in char variable, and a counter to keep track how many consecutive same characters are there.

The second loop is self-explanatory, we just find the same character and keep counting until the character are not the same.

Then we replace the first index as the character with our writer pointer. If the counter is larger than 1, means we need to put the number behind the character. And convert the counter to string, then assign them with writer pointer.

Finally, we directly reassign the length of our chars to strip out all the unnecessary indices. Then the length or p2 will be our answer.

I actually did more than these. But writing a post tooks too much time for me. So, maybe I should just call it a day now.