# 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 **

. Note that group lengths that are **chars**`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.