Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

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

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].
Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].
 

Constraints:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

Solution

Main idea:

We know that eventually we have to shoot down every balloon, so for each ballon there must be an arrow whose position is between balloon[0] and balloon[1] inclusively. Given that, we can sort the array of balloons by their ending position. Then we make sure that while we take care of each balloon in order, we can shoot as many following balloons as possible.

So what position should we pick each time? We should shoot as to the right as possible, because since balloons are sorted, this gives you the best chance to take down more balloons. Therefore the position should always be balloon[i][1] for the ith balloon.

This is exactly what I do in the for loop: check how many balloons I can shoot down with one shot aiming at the ending position of the current balloon. Then I skip all these balloons and start again from the next one (or the leftmost remaining one) that needs another arrow.

1
2
3
4
5
6
7

Example:

balloons = [[7,10], [1,5], [3,6], [2,4], [1,4]]
After sorting, it becomes:

balloons = [[2,4], [1,4], [1,5], [3,6], [7,10]]
So first of all, we shoot at position 4, we go through the array and see that all first 4 balloons can be taken care of by this single shot. Then we need another shot for one last balloon. So the result should be 2.

So we need to first order by the right position of each ballon first, then iterate the loop. The Arrow position is the right position of the first ballon. If the next ballon’s left position is smaller than the arrow position, then we can skip this ballon. If the next ballon’s left position is larger than the arrow position, then we need to shoot another arrow. The arrow position is the right position of the next ballon. After the iteration, we get the number of arrows.

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 findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(points.begin(), points.end(), [](vector<int> & a, vector<int> & b){
            return a[1] < b[1];
        });
        int n = points.size();
        int count = 1;
        int arrowPosition = points[0][1];
        for (int i = 1; i < n; i++){
            if (arrowPosition >= points[i][0]){
                continue;
            }
            else{
                count ++;
                arrowPosition = points[i][1];
            }
        }
        return count;
    }
};

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

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

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
 

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

Solution

In this solution, we iterate through the intervals. If the current interval’s end is smaller than the new interval’s start, we push the current interval to the answer vector. If the current interval’s start is larger than the new interval’s end, we push the new interval to the answer vector and update the new interval to the current interval. If the new interval overlaps with the current interval, we update the new interval’s start to the minimum of the two intervals’ start and update the new interval’s end to the maximum of the two intervals’ end. After the iteration, we push the new interval to the answer vector.

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:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n; i ++){
            if (intervals[i][1] < newInterval[0]){
                ans.push_back(intervals[i]);
            }
            else if (intervals[i][0] > newInterval[1]){
                ans.push_back(newInterval);
                newInterval = intervals[i];
            }
            else if (newInterval[1] >= intervals[i][0] || newInterval[0] <= intervals[i][1]){
                newInterval[0] = min (newInterval[0], intervals[i][0]);
                newInterval[1] = max (newInterval[1], intervals[i][1]);
            }
        }
        ans.push_back(newInterval);
        return ans;
    }
};

Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

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

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
 

Constraints:

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

Solution

In the solution, we sort the array first, then we iterate through the array. If the next interval’s start is smaller than the current interval’s end, then we merge the two intervals. If not, we push the current interval to the answer vector. After the iteration, we push the last interval to the answer vector.

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }

        // Sort intervals by start time
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> ans;
        ans.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); i++) {
            // If current interval overlaps with the last interval in ans
            if (intervals[i][0] <= ans.back()[1]) {
                // Merge the overlapping intervals
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            } else {
                ans.push_back(intervals[i]);
            }
        }

        return ans;
    }
};

Summary Ranges

You are given a sorted unique integer array nums. A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

“a->b” if a != b
“a” if a == b

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

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

My solution

My solution is redundant and not elegant. I use two pointers to record the first and last number of a range. If the next number is not the next number of the last number, then I push the range to the answer vector. If the next number is the next number of the last number, then I update the last number. If the last number is the last number of the array, then I push the range to the answer vector. If the array is empty, then I return an empty vector. If the array only has one number, then I return a vector with only one element.

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

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int n = nums.size();
        vector<string> ans;
        string single_ans = "";
        if (nums.empty()){
            return ans;
        }
        int first = nums[0];
        int last = nums[0] ;
        if (nums.size() == 1){
            ans.push_back(to_string(nums[0]));
            return ans;
        }
        for (int i = 0; i < n-1; i ++){
            if(nums[i+1] != nums[i] + 1 && first != last){
                single_ans = to_string(first) + "->" + to_string(last);
                ans.push_back(single_ans);
                first = last = nums[i+1];
            }
            else if (nums[i+1] != nums[i] + 1 && first == last){
                single_ans = to_string(first);
                ans.push_back(single_ans);
                first = last = nums[i+1];
            }
            else{
                last++;
            }
        }
        if (nums[n-1] != nums[n-2]+1)
            ans.push_back(to_string(nums[n-1]));
        else
            ans.push_back(to_string(first) + "->" + to_string(last));
        return ans;
    }
};

Solution from Leetcode

A solution with similar idea but more elegant shows below:

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

class Solution {
public:
    vector<string> summaryRanges(vector<int>& arr) {
        int n = arr.size(); // extracting size of the array
        vector<string> ans; // declaring answer array to store our answer
        
        string temp = ""; // temproray string that stores all possible answer
        
        for(int i = 0; i < n; i++) // start traversing from the array
        {
            int j = i; // declare anthor pointer that will move
            
            // run that pointer until our range is not break
            while(j + 1 < n && arr[j + 1] == arr[j] + 1)
            {
                j++;
            }
            
            // if j > i, that means we got our range more than one element
            if(j > i)
            {
                temp += to_string(arr[i]); // first store starting point
                temp += "->"; // then store arrow, as question wants it
                temp += to_string(arr[j]); // and lastly store the end point
            }
            else // we got only one element as range
            {
                temp += to_string(arr[i]); // then store that element in temp
            }
            
            ans.push_back(temp); // push one possible answer string to our answer
            temp = ""; // again reintiliaze temp for new possible answers
            i = j; // and move i to j for a fresh start
        }
        
        return ans; // and at last finally return the answer array
    }
};

In his code, he doesn’t need to check if the array is empty or only has one element. He uses a while loop to check if the next number is the next number of the last number. If it is, then he updates the last number. If it is not, then he pushes the range to the answer vector.

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

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

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
 

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109

My solution

We use the data structure unordered_set to store all the numbers in the array. Then we iterate through the array and check if the number is the start of a consecutive sequence. If it is, we keep checking the next number until we find the end of the sequence. We update the best length if the current length is longer than the best length.

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

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {
        std::unordered_set<int> numSet(nums.begin(), nums.end());
        int best = 0;
        
        for (int n : numSet) {
            if (numSet.find(n - 1) == numSet.end()) {  // only check for one direction
                int m = n + 1;
                while (numSet.find(m) != numSet.end()) {
                    m++;
                }
                best = std::max(best, m - n);
            }
        }
        
        return best;
    }
};

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

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

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

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

Constraints:

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

My solution

My solution is using a map to store the value in the array as the key and the index as the value. If the map already contains the key, we check if the difference between the current index and the index stored in the map is less than or equal to k. If it is, then we return true. If not, we update the value of the key in the map to the current index. If the map does not contain the key, we add the key and value to the map. If we finish the loop, we return false.

Code

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

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map <int, vector<int>> numberMap;
        for (int i = 0; i < nums.size(); i++){
            if (numberMap[nums[i]].size()>0){
                if(i- numberMap[nums[i]][0] <= k)
                    return true;
                else
                    numberMap[nums[i]].pop_back();
            }
            numberMap[nums[i]].push_back(i);
        }
        return false;
    }
};

Difference between map and unordered_map

I also see some solutions with unordered_map. So I did some research on the difference between map and unordered_map.
Both std::map and std::unordered_map are associative containers in C++ that store elements in key-value pairs, but they have some fundamental differences in terms of their internal workings, performance characteristics, and functionalities:

1. Underlying Data Structure:

   • std::map: Implemented using a balanced tree (usually a red-black tree). This guarantees that the elements are always ordered by their keys.
   • std::unordered_map: Implemented using a hash table. The elements are not ordered.

2. Order of Elements:

   • std::map: The elements are always ordered according to the keys (based on the comparison function, which is operator< by default).
   • std::unordered_map: There is no order guarantee for the keys or the values.

3. Performance:

   • std::map:
     • Insertion, deletion, and search have a logarithmic complexity: (O(\log n)).
   • std::unordered_map:
     • In average cases, the insertion, deletion, and search have constant time complexity: (O(1)).
     • In the worst case (when there are hash collisions), these operations can degrade to (O(n)).

4. Hash Function:

   • std::map: Does not use hashing, so there’s no need for a hash function.
   • std::unordered_map: Uses a hash function to map keys to buckets. You can provide a custom hash function, but there’s a default one provided for most standard types.

5. Memory Overhead:

   • std::map: Typically has a lesser memory overhead compared to std::unordered_map because it doesn’t need to manage the hash table.
   • std::unordered_map: Might have more memory overhead due to managing the hash table, especially when the load factor increases.

6. Iterators:

   • std::map: Iterators are ordered and remain valid as long as the corresponding element exists in the map. Inserting or deleting elements does not invalidate iterators to other elements.
   • std::unordered_map: Iterators are not ordered. Inserting an element might invalidate iterators if rehashing occurs, but erasing an element only invalidates the iterator to that element.

7. Usage Scenarios:

   • std::map: Useful when you need to maintain an order (like when you need the smallest or largest key frequently) or when you need to work with operations that rely on order (e.g., finding elements in a range).
   • std::unordered_map: Useful when you need faster average-case insertion, deletion, and search times, and you don’t need the keys to be ordered.

In summary, the choice between std::map and std::unordered_map depends on the specific requirements of your application. If ordering is essential, go with std::map. If you need faster average-time operations and don’t care about order, std::unordered_map might be the better choice.

I’d like to share my third year project experience with you. It is to use Mitsuba, which is a physical based renderer to simulate the chenrenkov particles in the Europe Large Hadron Collider, which is in CERN. The reason that I did this is because for now, the experiences in CERN are simulated by Geant4, which is a Monte Carlo simulation toolkit. However, Geant4 is very slow and cost huge memory usage. In the end, with collaborating with students in the department of physics, our application reduce over 99% time and only cost less than 1mb memory usage with the same accuracy.

The challanges I faced out is that I knew nothing about the particle physics since my major is computer science. So in the beginning of the project, it’s tough for me to understand what the result should be look like and how to achieve it. In the team, everyone has their own role. Mine is to implement the Mitsuba renderer and the interface between Mitsuba and Geant4, wheareas my colleagues’ are study the physical theory of Cherenkov radiation. The method that I overcame the challange is to communicate with my colleagues frequently and ask them questions. We held weekly meetings and in the meeting, we shared our new progress and discussed the problems we met. If they have any questions about the Mitsuba, they will ask me. If I have any questions about the physical theory, I will ask them.

This project is meaningful for me because it is not a toy tool. It is a real application that can be used in the future. We also attend the sharing meeting in CERN and got a lot of positive feedbacks.

At the beginning of choosing my third year project, I noticed that there are large amount of resources consumed and cost has always been a problem with simulation experiments based on the report of usage of computing resources by CERN. Therefore, I got the idea to reduce simulation time by using other tools.

My step to develop this idea is firstly, shared this idea with my supervisor. She is very supportive and told me that the department of physics is also interested in this topic. Then I contacted the department of physics and we decided to collaborate together. After that, I started to learn Mitsuba and implemented the Mitsuba renderer and the interface between Mitsuba and Geant4. My colleagues studied the physical theory of Cherenkov radiation. In the end, we combined our work together and got the final result.

It was important to be innovative in this instance because it is the first time that Mitsuba is used to simulate the Cherenkov radiation. Before that, Geant4 is the only tool that can be used to simulate the Cherenkov radiation. Also, the tool we developed can be used in real life, it is different from the tools that I developed before, which are just for fun or course projects. I’m motivated to do this project because I want to do something meaningful and useful. I want to use my knowledge to help others.

Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.

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

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:

Input: n = 2
Output: false
 

Constraints:

1 <= n <= 231 - 1

My solution

My solution is very intuitive, I convert the number to string and then convert each digit back to int and square it. Then I add all the squared digits together. I repeat this process until the sum is 1 or the iterate times achieve the maximum set. If the sum is 1, then the number is happy. If the loop is endless, then the number is not happy.

I learnt that in C++, we can use to_string() to convert a number to string and stoi() to convert a string to int.

If we want to convert a char to int, we can use char - '0'. The reason is that the ASCII value of ‘0’ is 48, ‘1’ is 49, etc. So if we want to convert ‘0’ to 0, we can use 48 - 48 = 0, for other digits, we can use 49 - 48 = 1, 50 - 48 = 2, etc.

Floyd Cycle Detection Algorithm

Firstly, let’s find out what is Floyd Cycle Detection Algorithm. It is also called Tortoise and Hare Algorithm.

Basic Idea:

The algorithm uses two pointers that move through the sequence at different speeds:

• Tortoise (or slow pointer): Advances one step at a time.
• Hare (or fast pointer): Advances two steps at a time.

If there’s a loop in the sequence, the hare will eventually catch up to the tortoise.

Relationship with the Happy Number Problem:

In the context of the happy number problem, the sequence is formed by repeatedly applying the “sum of the squares of its digits” operation. If a number is not happy, it will eventually fall into a cycle (or loop).

For example, for the number 4:

1. (4^2 = 16)
2. (1^2 + 6^2 = 37)
3. (3^2 + 7^2 = 58)
4. (5^2 + 8^2 = 89)
5. (8^2 + 9^2 = 145)
6. (1^2 + 4^2 + 5^2 = 42)
7. (4^2 + 2^2 = 20)
8. (2^2 + 0^2 = 4)
   … and it goes back to 4, forming a cycle.

By using the Tortoise and Hare approach:

• The slow pointer will produce the sequence: 4, 16, 37, 58, …
• The fast pointer will produce the sequence: 16, 58, 20, 4, …

After a few iterations, both the slow and fast pointers will meet, indicating a cycle. In this problem, detecting a cycle means the number is not happy.

Why it works:

Imagine a circular racetrack. If you have two runners - one running twice as fast as the other - they’ll eventually end up at the same position on the track, because the faster runner will catch up to the slower runner from behind.

Similarly, in the context of sequences, if there’s a cycle, the fast pointer (hare) will eventually meet the slow pointer (tortoise) inside the loop.

Conclusion:

Floyd’s Cycle Detection Algorithm is a powerful tool for detecting loops in sequences without needing to use extra space (like storing all seen elements in a set).

Get the sum of the squared digits

I learnt that we can use % to get the last digit of a number and / to get the rest of the digits. For example, if we want to get the last digit of 123, we can use 123 % 10 = 3. If we want to get the rest of the digits, we can use 123 / 10 = 12.

1
2
3
4
5
6
7
8
9

int getSum (int n){
    int sum = 0, digit;
    while (n != 0){
        digit = n % 10;
        sum += digit * digit;
        n = n / 10;
    }
    return sum;
}

Implementation of Floyd Cycle Detection Algorithm

1
2
3
4
5
6
7
8
9

bool isHappy(int n) {
    int slow = n, fast = n;
    do{ slow = getSum(slow);
        fast = getSum(getSum(fast));
        if (fast == 1)
            return true;
    }while(fast!=slow);
    return false;
}

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

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

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

My solution

My first idea is to use two for loops to loop through the array and find the two numbers. However, this method is not efficient. The time complexity is O(n^2).

Then I found a better solution. I use a unordered_map to store the numbers and their indices. Then I loop through the array and check if the target minus the current number is in the map. If it is, then we find the two numbers. If it is not, we put the current number and its index into the map.

What I learnt today:

1. I can insert multiple numbers into a vector at the same time:

   1	list.insert(list.end(), {element,element});

Full code

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> map;
        vector <int> ans;
        for (int i = 0; i< nums.size(); i++){
            int plusNo = target - nums[i];
            if (map.find(plusNo) != map.end()){
                ans.insert(ans.end(), {i,map[plusNo]});
                return ans;
            }
            map[nums[i]] = i;
        }
        return ans;
    }
};

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:

Input: strs = [""]
Output: [[""]]
Example 3:

Input: strs = ["a"]
Output: [["a"]]
 

Constraints:

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

My solution

I found one solution to solve “Anagrams” problems, which is to sort the string. If the sorted result for two strings are the same, then they are anagrams.

Based on this idea, I sort each string and put the sorted result as the keys of the map. The values of the map are the original strings. Then I loop through the map and put the values into the result vector.

Two things I learnt today:

1. How to create a map:

   1	map <string, vector<string>> strOrder;

2. How to loop through a map and select the values (select key is pair.first):

   1 2 3

   for (const auto &pair: strOrder){ ans.push_back(pair.second); }

   Full code

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

   class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { map <string, vector<string>> strOrder; for (int i = 0; i < strs.size(); i++){ string str_copy(strs[i]); sort(str_copy.begin(), str_copy.end()); strOrder[str_copy].push_back(strs[i]); } vector <vector<string>> ans; for (const auto &pair: strOrder){ ans.push_back(pair.second); } return ans; } };

Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

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: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
 

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

My solution

Let me explain my solution in the 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

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        // create two maps to store the mapping between characters and words
        unordered_map <char, string> charMatch;
        unordered_map <string, char> stringMatch;
        // create a pointer to point to the pattern
        int patternPointer = 0;
        string word = "";
        // create a counter to count the number of words
        int wordCounter = 0;
        for (int i = 0; i <= s.size(); i++){
            // if we reach the end of the string or we reach a space
            if (s[i] == ' ' || i == s.size()){
                auto find = charMatch.find(pattern[patternPointer]);
                auto findS = stringMatch.find(word);
                // if we don't find the element in the map
                if (find == charMatch.end() && findS == stringMatch.end()){
                    // insert the element into the map
                    charMatch[pattern[patternPointer]] = word;
                    stringMatch[word] = pattern[patternPointer];
                    word = "";
                    patternPointer ++;
                    wordCounter ++;
                }
                else{
                    // if we find the element in the map but the mapping is not correct
                    if (charMatch[pattern[patternPointer]] != word || stringMatch[word] != pattern[patternPointer]) 
                        return false;
                    else{
                        word = "";
                        patternPointer ++;
                        wordCounter ++;
                    }
                }
            }
            else
                word += s[i];
        }
        // if the number of words is not equal to the number of characters
        if (wordCounter != pattern.size())
            return false;
        return true;
    }
};

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false
 

Constraints:

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

My solution

Let me explain my solution in the 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:
    bool isAnagram(string s, string t) {
        unordered_map <char, int> wordCount;
        // count the number of characters in s
        for (int i = 0; i < s.size(); i++){
            wordCount[s[i]] ++;
        }
        // check if the characters in t are in s
        for (int j = 0; j < t.size(); j++){
            // if the character is not in s or the number of the character in t is more than in s
            if(wordCount[t[j]] == 0)
                return false;
            // if the character is in s
            else
                wordCount[t[j]]--;
        }
        // check if there are any characters left in s
        for (int i = 0; i < s.size(); i++){
            // if there are characters left in s
            if (wordCount[s[i]] != 0)
                return false;
        }
        // if there are no characters left in s
        return true;
    }
};