Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal
substring consisting of non-space characters only.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.
Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.
Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.
 

Constraints:

1 <= s.length <= 104
s consists of only English letters and spaces ' '.
There will be at least one word in s.

My solution

At first, my solution is to split the string by space and store the words in a vector. Then I return the length of the last word in the vector. So I learned about how to split by space in C++:

1
2
3
4
5
6

vector <string> tokens;
istringstream iss(s);
string token;
while(iss >> token)
    tokens.push_back(token);
return (tokens[tokens.size()-1].length());

In this code,

1

std::istringstream iss(s);

1. std::istringstream is a type provided by the <sstream> header. It stands for “input string stream” and can be thought of as a stream that operates on strings, just as you’d read from or write to files with file streams.

2. When you create an istringstream with a string argument, the content of the string is loaded into the stream. In this case, the content of s is loaded into the iss stream, and you can then “read” from this stream using extraction (>>) operators, as you would with std::cin or any other stream.

1

std::string token;

1. This line simply declares a string named token. This will be used to hold individual space-separated segments (tokens) from the original string as we extract them from the stream.

1
2
3

while (iss >> token) {
    tokens.push_back(token);
}

1. The loop’s condition, iss >> token, tries to extract a “word” (a space-separated segment) from the iss stream and put it into the token string. If the extraction is successful (meaning there’s still content in the stream), the loop continues. If the extraction fails (meaning there’s no more content to extract), the loop exits.

2. The >> operator, when used with streams and strings, automatically splits on whitespace (like spaces, newlines, and tabs), so each iteration extracts one word from the string up to the next space or end of the string.

3. tokens.push_back(token); adds the extracted token to the tokens vector.

The loop, in essence, continues extracting words from iss and adding them to the tokens vector until there’s no more content left in iss.

A solution with more algorithmic idea

Then I thought that a string is actually a vector in c++, and we can use a more algorithmic idea to solve it. To be specific, we can iterate the string from the last to the first, if we meet a character that is not a space, we increase the count by one, if we meet a space and it is behind all the characters, we skip it, if we meet a space and the count is not 0, we then break our loop and return the count:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.size();
        int count = 0;
        for (int i = n -1; i >= 0; i--){
            if (s[i] == ' ' && count == 0)
                continue;
            if (s[i] != ' ')
                count ++;
            else if (s[i] == ' ')
                break;
        }
        return count;
    }
};

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
 

Constraints:

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].

My solution and the improved one

My first idea is set a lot of if statements to deal with different roman letter. It doesn’t cost extra space but the code seems redundant.

The improved solution is create an unordered_map first. Then we find the pattern that if the current letter is smaller than the next one, it means this situation happened:

1
2
3
4

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

So we minus the current letter from the result. Otherwise, we add the current letter to the result.

Full Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int romanToInt(string s) {
        unordered_map <char, int> romanMap;
        romanMap['I'] = 1;
        romanMap['V'] = 5;
        romanMap['X'] = 10;
        romanMap['L'] = 50;
        romanMap['C'] = 100;
        romanMap['D'] = 500;
        romanMap['M'] = 1000;
        int answer = 0;
        for (int i = 0; i < s.size(); i++){
            if (romanMap[s[i]] >= romanMap[s[i+1]])
                answer += romanMap[s[i]];
            else
                answer -= romanMap[s[i]];
        }
        return answer;
    }
};

Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.
Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
 
Constraints:

1 <= num <= 3999

Solution

I create a vector with pairs, in each pair it contains the value and its corresponding string. Then I iterate the vector from the largest value to the smallest value. while the current num, which is the input, is larger or equal than the value, we add the corresponding string to the answer, and update the num by minusing the value. Otherwise, we move to the next pair.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    string intToRoman(int num) {
        vector <pair<int, string>> romanMap;
        romanMap.push_back(make_pair(1000,"M"));
        romanMap.push_back(make_pair(900,"CM"));
        romanMap.push_back(make_pair(500,"D"));
        romanMap.push_back(make_pair(400,"CD"));
        romanMap.push_back(make_pair(100,"C"));
        romanMap.push_back(make_pair(90, "XC"));
        romanMap.push_back(make_pair(50,"L"));
        romanMap.push_back(make_pair(40,"XL"));
        romanMap.push_back(make_pair(10,"X"));
        romanMap.push_back(make_pair(9,"IX"));
        romanMap.push_back(make_pair(5,"V"));
        romanMap.push_back(make_pair(4, "IV"));
        romanMap.push_back(make_pair(1,"I"));

        string answer = "";

        for (const auto& pair : romanMap) {
            while (num >= pair.first) {
                answer += pair.second;
                num = num - pair.first;
            }
        }

        return answer;
    }
};

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

1
2
3
4
5
6
7
8
9
10
11
12
13

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Max Height Approach

The first solution is to get the maximum height of the left of each element and the maximum height of the right of each element respectively. Then based on the two maximum height, we can calculate the water that can be trapped in each element. The total water is the sum of the water trapped in each element.

Left and Right Max Height

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int n = height.size();
    vector <int> max_Left(n, 0);
    vector <int> max_Right(n, 0);
    for (int i = 1; i < n; i++){
        if (height[i - 1] > max_Left[i-1]){
            max_Left[i] = height[i - 1];
        }
        else
            max_Left[i] = max_Left[i-1];
    }
    for (int i = n - 2; i >=0; i --){
        if (height[i + 1] > max_Right[i+1]){
            max_Right[i] = height[i + 1];
        }
        else
            max_Right[i] = max_Right[i+1];
    }

The water trapped in each element

For each element, we know the max height of the left and right, we choose the smaller one because the condition of the trapped water is based on the shortest height. Then we minus the height of the current element, the result is the water trapped in the current element. The reason that we minus the current height is that it represents the height that is solid, which represents that the water can’t be trapped in. We then add the water trapped in each element together, the result is the total water trapped in the elevation map.

1
2
3
4
5
6
7

int trap_water = 0;
for (int i = 0; i < n; i++){
    int minMaxHeight = min (max_Left[i], max_Right[i]);
    if (minMaxHeight - height[i] > 0)
        trap_water += (minMaxHeight - height[i]);
}
return trap_water;

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector <int> max_Left(n, 0);
        vector <int> max_Right(n, 0);
        for (int i = 1; i < n; i++){
            if (height[i - 1] > max_Left[i-1]){
                max_Left[i] = height[i - 1];
            }
            else
                max_Left[i] = max_Left[i-1];
        }
        for (int i = n - 2; i >=0; i --){
            if (height[i + 1] > max_Right[i+1]){
                max_Right[i] = height[i + 1];
            }
            else
                max_Right[i] = max_Right[i+1];
        }
        int trap_water = 0;
        for (int i = 0; i < n; i++){
            int minMaxHeight = min (max_Left[i], max_Right[i]);
            if (minMaxHeight - height[i] > 0)
                trap_water += (minMaxHeight - height[i]);
        }
        return trap_water;

    }
};

Two pointer solution

We can also improved the last solution by using a two pointer solution. In this solution, we don’t need to iterate the loop for three times. The two pointers are called left and right respectively. The left pointer is the index of the leftmost element and the right pointer is the index of the rightmost element. We also create two variables called leftMax and rightMax to store the maximum height of the left and right respectively.

1
2
3
4
5
6

int n = height.size();
int total_water = 0;
int left_max = 0;
int right_max = 0;
int left = 0;
int right = n-1 ;

We called the minimum of leftMax and rightMax water_level, which is to make sure the water will not be leaked in this height. If water_level is higher than the current element’s height, which means some water is trapped in this element, we then update the total_water, left and skip the following operations and jump to the next iteration. The idea from right to the left is similar.

If the current left or right element is higher than the leftMax and the rightMax, we then update the leftmax and the rightMax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

while (left < right){
    int water_level = min (left_max, right_max);
    if (water_level >= height[left]){
        total_water += (water_level - height[left]);
        left ++;
        continue;
    }
    if (water_level >= height[right]){
        total_water += (water_level - height[right]);
        right --;
        continue;
    }
    left_max = max(left_max, height[left]);
    right_max = max(right_max, height[right]);
    }

Full Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int total_water = 0;
        int left_max = 0;
        int right_max = 0;
        int left = 0;
        int right = n-1 ;
        while (left < right){
            int water_level = min (left_max, right_max);
            if (water_level >= height[left]){
                total_water += (water_level - height[left]);
                left ++;
                continue;
            }
            if (water_level >= height[right]){
                total_water += (water_level - height[right]);
                right --;
                continue;
            }
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
        }
        return total_water;
    }
};

Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
 

Constraints:

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

My solution

We can use greedy approach to accomplish this question.

We initialise an array full of 1 as the candy number with the same size of ratings.

1
2

int n = ratings.size();
vector <int> candies (n,1);

The main idea is iterate the ratings array from left to right first. If a child’s rating is greater than their left neighbor’s rating, assign them one more candy than their left neighbor.

1
2
3
4
5

for (int i = 1; i < n; i++){
    if (ratings[i] > ratings[i-1]){
        candies[i] = candies[i-1] + 1;
    }
}

Then we iterate the array again but this time we from the right to the left. If the current child’s rating is greater than the right neighbour’s rating, and the number of candies is smaller than the number of neighbour’s candy plus one, then we update the current child’s candy number by adding one to the neighbour’s candy number.

1
2
3
4
5
6
7
8

for (int i = n - 2; i >= 0; i--){
    if (ratings[i] > ratings[i+1]){
        if (candies[i] > candies[i+1] + 1){
            continue;
        }
        else candies[i] = candies[i+1] + 1;
    }
}

Finally, we sum up the candy array and return the result.

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector <int> candies (n,1);
        for (int i = 1; i < n; i++){
            if (ratings[i] > ratings[i-1]){
                candies[i] = candies[i-1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--){
            if (ratings[i] > ratings[i+1]){
                if (candies[i] > candies[i+1] + 1){
                    continue;
                }
                else candies[i] = candies[i+1] + 1;
            }
        }
        int total = 0;
        for (int i = 0; i < n; i ++){
            total += candies[i];
        }
        return total;
    }
};

Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
 

Constraints:

n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

My solution

My solution is complex and cost O(n^2) time complexity. It fails in the last two tests as the time exceed problem. Here is the fulle code with explanation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // An array to store the Ind that is not zero
        vector <int> maxInd;
        int n = gas.size();
        for (int i = 0; i < n; i ++){
            // if the difference is not zero, store the index to the vector
            if (gas[i] - cost[i] >= 0){
                maxInd.push_back(i);
            }
        }

        while (!maxInd.empty()){
            int maxIndLength = maxInd.size();
            // the index that want to check
            int targetInd = maxInd[maxIndLength-1];
            int current =  targetInd + 1;
            int currentGas = gas[targetInd] - cost[targetInd];
            // loop the array to find out if it can run in a circular route
            while (current != targetInd){
                // if go to the end of the array, return to 0 index
                if (current == n){
                    current = 0;
                    // if the 0 index is the target Index.
                    if (current == targetInd)
                        break;
                }
                // run and calculate the gas we have
                currentGas = currentGas + gas[current] - cost[current];
                // smaller than 0, means can't run the whole circle from this station
                if (currentGas < 0)
                    break;
                current ++;
            }
            if (currentGas >= 0)
                return targetInd;
            else
                maxInd.pop_back();
        }
        return -1;
    }
};

Improved Solution

The improved solution only cost O(n) time complexity.
The main idea is to make sure that the car have enough gas to run around the whole circuit, the total gas, which is the sum of all the gas[i] - cost[i], should be larger than 0. If it is smaller than 0, it means that the car can’t run around the whole circuit.

The second idea is to find out the gas station that can run the whole circuit. If the car can run from gasStation[i] to gasStation[i+1], it means that the car can run from gasStation[i+1] to gasStation[i+2]. So we can use a variable called currentGas to record the gas we have. If the currentGas is smaller than 0, it means that the car can’t run from gasStation[i] to gasStation[i+1], so we update the currentGas to 0 and update the gasStation to i+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalGas = 0;
        int currentGas = 0;
        int gasStation = 0;
        for (int i = 0; i < n; i++){
            totalGas += (gas[i] - cost[i]);
            currentGas += (gas[i] - cost[i]);
            if (currentGas < 0){
                currentGas = 0;
                gasStation = i + 1;
            }
        }
        if (totalGas >= 0)
            return gasStation;
        return -1;
    }
};

Product of Array Except Self

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

My solution

I actually use division operation to solve this question. But this is the first idea that come up to my head, so I record it here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int tot_prod = 1;
        // To count how many zero are there in the array
        int zero_num = 0;
        for (int i = 0; i < n; i++){
            if (nums[i] == 0){
                zero_num ++;
                continue;
            }
            // Calculate the total product for all the elements
            tot_prod *= nums[i];
        }
        vector <int> answer;
        // If there is no zero
        if (zero_num == 0){
            for (int i = 0; i < n; i++){
                // each element in the answer is total product divided by itself
                answer.push_back(tot_prod / nums[i]);
            }
        }
        else if (zero_num == 1){
            // If there is one 0, all the element is 0 except for the index of 0
            for (int i = 0; i < n; i++){
                if (nums[i] == 0)
                    answer.push_back(tot_prod);
                else answer.push_back(0);
            }
        }
        else{
            // If there are more than one 0, all the elements are 0.
            for (int i = 0; i < n; i++){
                answer.push_back(0);
            }
        }
        return answer;
    }
};

Improved Solution

The improved idea is based on computing the products to the left and right of the current element and multiplying them, we obtain the product of all elements except the current one. To be specific, we firstly compute the product of all elements to the left of the current element.

1
2
3
4
5
6

int n = nums.size();
vector <int> answer(n);
answer[0] = 1;
for (int i = 1; i < n; i++){
    answer[i] = answer[i-1] * nums[i-1];
}

Then we initiate a variabe right which is equal to 1 to represent the element at the right of the end element. Then we iterate the array from the end to the beginning, and update the answer array. The variable right is the product of all the elements to the right of the current element.

1
2
3
4
5

int right = 1;
for (int i = n - 1; i >= 0; i--){
    answer[i] = right * answer[i];
    right = right * nums[i];
}

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector <int> answer(n);
        answer[0] = 1;
        for (int i = 1; i < n; i++){
            answer[i] = answer[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--){
            answer[i] = right * answer[i];
            right = right * nums[i];
        }
        return answer;
    }
};

Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
 

Constraints:

-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Use a combination of data structures

Create data structures

We use two data structures in this question, one is unordered_map, the other is vector.

1
2
3

private:
    unordered_map<int, int> elementToIndex;  // Map to store elements and their indices
    vector<int> elements;  // Vector to store the elements

Initialise the class

1
2
3
4
5

RandomizedSet() {
    // Initialize the class
    elementToIndex.clear();
    elements.clear();
}

Insert

For unordered_map, it has a function called find (value). This function returns an iterator pointing to the found element or an iterator equal to the end() of the map if the element is not found. So we use this function to make sure that the value is not in the vector. If the vlaue is already in the vector, we return false. Otherwise, we push the value to the end of the vector, and record the index of it in unordered_map.

1
2
3
4
5
6
7
8
9

bool insert(int val) {
    // Check if the element is already in the map, if not, add it to the vector
    if (elementToIndex.find(val) != elementToIndex.end())
        return false;
    // Return true if the element was inserted, false otherwise
    elements.push_back(val);
    elementToIndex[val] = elements.size() - 1;
    return true;
}

Remove

Similarly, we first check if the value is in the vector. If it is not, we return false.
Then we swap the element of the target value with the end element. After that, we update the index of the end element in the map. Finally, we pop the end element from the vector and erase the target element in the map and return true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool remove(int val) {
    // Check if the element is in the map, if not, return false
    if (elementToIndex.find(val) == elementToIndex.end())
        return false;
    // Swap the element with the last element in the vector to remove it
    int cache;
    int index = elementToIndex[val];
    cache = elements[index];
    elements[index] = elements[elements.size() - 1];
    elements[elements.size() - 1] = cache;
    // Update the map with the new index for the swapped element
    elementToIndex[elements[index]] = index;
    elementToIndex.erase(val);
    // Pop the last element from the vector
    elements.pop_back();
    // Return true
    return true;
}

Random return a value in the array

To return a value in the array randomly, we use rand() function to generate a random number between 0 and the size of the vector. Then we return the element at the index of the random number.

1
2
3
4
5
6
7
8

int getRandom() {
    // Generate a random index within the size of the vector
    if( elements.size() == 0)
        return 0;
    int randomIndex = rand() % elements.size(); 
    // Return the element at that index
    return elements[randomIndex];
}

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class RandomizedSet {
public:
    RandomizedSet() {
        // Initialize the class
        elementToIndex.clear();
        elements.clear();
    }

    bool insert(int val) {
        // Check if the element is already in the map, if not, add it to the vector
        if (elementToIndex.find(val) != elementToIndex.end())
            return false;
        // Return true if the element was inserted, false otherwise
        elements.push_back(val);
        elementToIndex[val] = elements.size() - 1;
        return true;
    }

    bool remove(int val) {
        // Check if the element is in the map, if not, return false
        if (elementToIndex.find(val) == elementToIndex.end())
            return false;
        // Swap the element with the last element in the vector to remove it
        int cache;
        int index = elementToIndex[val];
        cache = elements[index];
        elements[index] = elements[elements.size() - 1];
        elements[elements.size() - 1] = cache;
        // Update the map with the new index for the swapped element
        elementToIndex[elements[index]] = index;
        elementToIndex.erase(val);
        // Pop the last element from the vector
        elements.pop_back();
        // Return true
        return true;
    }

    int getRandom() {
        // Generate a random index within the size of the vector
        if( elements.size() == 0)
            return 0;
        int randomIndex = rand() % elements.size(); 
        // Return the element at that index
        return elements[randomIndex];
    }

private:
    unordered_map<int, int> elementToIndex;  // Map to store elements and their indices
    vector<int> elements;  // Vector to store the elements
};

About Unordered_map

An unordered_map is a container in C++ that provides an associative array (or dictionary) data structure. It allows you to store key-value pairs where keys are unique, and you can quickly retrieve the corresponding values based on the keys. Here are some of the key features of std::unordered_map:

1. Fast Lookup: unordered_map provides fast lookup of values based on their keys. The time complexity for average-case lookups is O(1), which makes it suitable for applications where you need efficient access to data based on keys.

2. Unique Keys: Each key in an unordered_map is unique. This means that you cannot have multiple entries with the same key. If you attempt to insert a key that already exists, the new value will overwrite the old one.

3. Hash-Based: The underlying data structure is based on a hash table, which uses a hash function to map keys to positions in memory. This allows for efficient retrieval and insertion of key-value pairs.

4. Iterating: You can easily iterate through all the key-value pairs in an unordered_map using iterators. This is useful for performing operations on all the elements or searching for specific key-value pairs.

5. No Guaranteed Order: The key-value pairs are not guaranteed to be stored in any specific order. They are organized based on the hash values of the keys, so you may see different orderings when iterating through the map.

6. Dynamic Sizing: unordered_map dynamically resizes itself as you insert or erase elements. This ensures that it remains efficient as you add more data.

7. Custom Key Types: You can use custom types as keys as long as you provide a hash function and equality operator for those types.

Here’s a simple example of how to use unordered_map:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;

    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    std::cout << "Alice's age: " << ages["Alice"] << std::endl;

    // Iterating through the map
    for (const auto& pair : ages) {
        std::cout << pair.first << " is " << pair.second << " years old." << std::endl;
    }

    return 0;
}

In this example, we create an unordered_map to store ages based on names. It demonstrates inserting key-value pairs, accessing values using keys, and iterating through the map.

H-Index

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1
 

Constraints:

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

My solution

My idea is firstly sort the array first from the least to the largest.

1
2
3

sort (citations.begin(), citations.end(), [](int & a, int & b){
    return a <= b;
});

Also, we create two variables, one is the hIndex and the other is called count. For the situation that the ith element is one of the h-index, which means i + citations[i] is smaller than the length of the citations array, during the iteration, we update the maximum h-index.
For example, in the array 0,1,3,5,6, 0 is one h-index; 1 is one h-index and it means the researcher has published at least 1 paper that has been cited at least 1 time; 3 is one h-index and it means the researcher has published at least 3 paper that has been cited at least 3 times, when we count i + citations[i], which is 2 + 3, the result is equal to the length of the array. So we update the h-index to 3.

1
2
3
4

In the loop:
    if ((citations[i] > hInd) && (i + citations[i]) <= n){
        hInd = citations[i];
    }

However, there exists some situation that not fit this method, for example, the array [0,0,4,4].
In this situation, our h-index is 0, however, the correct answer is 2 because the researcher has published 2 papers that have been cited at least 2 times. So I use the variable count to handle this situation, once the result of i + citations[i] is larger than the length of the array, we add one to the count.

1
2
3

In the loop:
    if (i + citations[i] >n)
        count ++;

After iteration, we return the larger one between the h-index and the count.

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int hInd = 0;
        int count = 0;
        sort (citations.begin(), citations.end(), [](int & a, int & b){
            return a <= b;
        });
        for (int i = 0; i < n; i++){
            if ((citations[i] > hInd) && (i + citations[i]) <= n){
                hInd = citations[i];
            }
            if (i + citations[i] >n)
                count ++;
        }
        if (hInd < count)
            return count;
        else
            return hInd;
    }
};

Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
 

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Greedy solution

I try to solve this problem by greedy solution by myself but I failed. One solution is to use greedy method.

First, we initiate a variable called maxReach, which means how far can we jump from a specific index.

Then, we iterate the loop, in each iteration, we compare if the index is larger than the maxReach, if so, it means it cannot jump to the current index, we return false.

1
2

if (i > maxReach)
    return false;

Then we find the max value between maxReach and i + nums[i], the larger one will be the new value of maxReach

1

maxReach = max (maxReach, i + nums[i]);

If the vlaue of maxReach is larger than the length of the array, which means we can jump to the end of the array, we return true.

1
2

if (maxReach >= n - 1)
    return true;

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int maxReach = 0;
        for (int i = 0; i < n; i++){
            if (i > maxReach)
                return false;

            maxReach = max (maxReach, i + nums[i]);
            
            if (maxReach >= n - 1)
                return true;
        }
        return true;
    }
};

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

1
2
3

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: nums = [2,3,0,1,4]
Output: 2
 

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Greedy solution

In this solution, we create a new vairable called currentPosition. When its value is equal to the index in the loop, it means a jump is needed, so we increase the count, and update the currentPosition to the maxJump, which means we need to jump when the index is equal to the current maxJump. Also, during the iteration, we update the maxJump by comparing the current maxJump with (i+nums[i]).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int maxJump = 0;
        int currentPosition = 0;
        int count = 0;
        for (int i = 0; i < n-1; i++){
            maxJump = max(maxJump, i + nums[i]);
            if (currentPosition == i){
                currentPosition = maxJump;
                count ++;
            }
        }
        return count;
    }
};

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
 

Constraints:

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

Greedy solution

The greedy solution loop the whole array and compare the current elemnt to the previous element, if the current one is larger than the previous one, the difference between these two elemets is added to the maximum profits. It’s really a clever method that I can’t think by myself at the first time. The reason that we can use greedy solution is we only can hold one stock at a time and we can’t buy a stock before we sell the previous one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2){
            return 0;
        }
        int maximum_profit = 0;
        for (int i = 1; i < n; i++){
            if (prices[i] > prices[i-1]){
                maximum_profit += (prices[i]-prices[i-1]);
            }
        }
        return maximum_profit;
        
    }
};

Dynamic Programming

We can also solve it by using dynamic programming method, though it’s harder for me to understand.

First, we create two arrays, one is called withstock, which means we buy a stock; the other is called withoutstock, which means we sold a stock or we don’t have one.

1
2

vector<int> withstock (n,0);
vector<int> withoutstock (n,0);

Then we initialise the first value of these two arrays. The first element of withstock is 0 - prices[0] because we loose money for buying this stock. The first element of withoutstock is 0 because we don’t buy the first stock.

1
2

withstock[0] = -prices[0];
withoutstock[0] = 0;

Then we loop the prices array to update the value of withstock and withoutstock. During each iteration, we should find the best solution for each array. For example, for the array withstock, we should find the maximum value between the previous value in the withstock and the difference between the previous value of withoutstock and the price of this current element. It means we are comparing the money we get by don’t buying this current stock (element) or buying this one.

Similarly, for the withoutstock array, we decide whether we keep the stock we had or we sell it by finding the maximum value between withoutstock[i-1] and withstock[i-1] + prices[i]. Uhh, it’s do hard to explain it by words.

1
2
3
4

for (int i = 1; i < n; i++){
    withstock[i] = max(withstock[i - 1], (withoutstock[i-1] - prices[i]));
    withoutstock[i] = max(withoutstock[i-1], (withstock[i-1] + prices[i]));
}

Finally, we return the last element in the withoutstock array because we can’t have a stock at the end of the day.

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2){
            return 0;
        }
        vector<int> withstock (n,0);
        vector<int> withoutstock (n,0);
        withstock[0] = -prices[0];
        withoutstock[0] = 0;
        for (int i = 1; i < n; i++){
            withstock[i] = max(withstock[i - 1], (withoutstock[i-1] - prices[i]));
            withoutstock[i] = max(withoutstock[i-1], (withstock[i-1] + prices[i]));
        }
        return withoutstock[n-1];
    }
};