Sort

349 Intersection of Two Arrays   (N)

Sort both array nums1 and nums2 and call STL set_intersection to save result to nums1.
create a set from nums1 beginning.
create a vector of int out of the result set and return it.

242 Valid Anagram (N)

Solution 1：

sort both the string s and t in ascending order.

return s == t

O(NlgN) time and O(1) space

Solution 2:

Use 2 hash map freq1 and freq2 to save the chars frequency of both s and t

return the freq1 == freq2

350 Intersection of Two Arrays II     (Y)

Solution 1: same with 349
Solution 2: Use hash Map to count the frequency of each number in the first array.
In the second loop, loop each element in the second array, if freq[num]-- still > 0, add it to the result array, otherwise skip it. return the result array in the end.

524	Longest Word in Dictionary through Deleting    (Y)

 Wihtout sorting: O((L + S) * D) = O(D(L + S)), O(L) space
Since sorting the dictionary could lead to a huge amount of extra effort, we can skip the sorting and directly look for the strings x in the unsorted dictionary $d$D such that $x$is a subsequence in $s$ If such a string s $x$is found, we compare it with the other matching strings found till now based on the required length and lexicographic criteria. Thus, after considering every string in D we can obtain the required result.

DNF (Dutch National Flag) problem, 3 pointers

75	Sort Colors

It’s actually Dutch national flag problem (DNF).

[, i): 0
[i, j]: 1
(k, ...]: 2
Once j goes over k, the sorting is complete

Before that, check the value of nums[j]:
(a) If nums[j] == 0, swap with nums[i] and increase both i,j
(b) If nums[j] == 1, no swap needed, just increase j
(c) If nums[j] == 2, swap with nums[k], only decrease k.

j <= k, not j < k. We need equal, otherwise 2, 0, 1 won't work. Because when j == k, it is possible
that the number is 0, we still need to swap it with 1.

767	Reorganize String     (Y)

O(N) time, O(N) space solution, using priority_queue with a helper queue to filter the already 0-counted pairs.

For priority queue, the highest priority element (maximum count element here, therefore we want the pair in the priority queue be pair<int, char> rather than pair<char, int>, the later will sort the queue by descending alphabetical order, the first will sort the array according to the int number in descending order) is always at the front.

147 Insertion Sort List (Y)

Loop each  nodes in the original linked list. Create a new node for each node inside the loop.  Keep going forward until find the element that has a larger value than current node value and insert the current node in front of it.

274 H-Index  (Y)

Using STL unordered_map as hash map, O(N) time and O(N) space
(1) Count the frequency of each citation number in a loop. For these paper
(2) that has citation more than the total number of papers N, treat them as cited as N, since the hIndex is the minimum of number and citation times.
(3) Backward loop the frequency map  i: from N to 1 (all possible h-Index),  and check whether freq[i]  >= i, if so return it. Otherwise, add the freq[i - 1] += freq[i]; If no early return meaning no citation or no paper published at all, return 0.

56	Merge Intervals   (Y)

Sort the arry first. Then in the loop, keep a  maxEnd for starting from the current group, if the next interval start is less or equal to maxEnd then it is mergeable with the current group.  After find all the mergeable interval for current group, the merged interval will be Interval(intervals[first].start, maxEnd).


148  Sort List (Y)
        (s1) int len = getListLen(head);
        (s2)head = mergeSort(head, len);
              recursively call mergeSort to sort the first half and second half and then merge them together (divide and conquer), note the base case is (len == 0 or len == 1) it is NOT (!head || !head->next). And the while loop exit condition is (i < len1 || j < len2), it is NOT (head1 || head2)
        (s3)breakCircle(head, len);

179 Largest Number (N)

(1) Create a vector of string out of vector of number (use to_string to convert num to string)

(2) Sort the vector of string in descending order, (cmp a + b with b + a)

(3) add the sorted string to res

Note: if all 0000, need to use atoi(str.c_str()) to compare with zero, don't use stoi, stoll exceeds limit, runtime error.

324	Wiggle Sort II   (Y)

Sort the array and save it in a array called sorted.
Split the array into two parts: first half (0 ~ (N - 1)/2) and second half ((N + 1)/ 2 ~ N -1).
Assign one element from each half to the result num array backwardly.

Example nums = [1,2,...,7]      Example nums = [1,2,...,8] 

Small half:  4 . 3 . 2 . 1      Small half:  4 . 3 . 2 . 1 .
Large half:  . 7 . 6 . 5 .      Large half:  . 8 . 7 . 6 . 5
--------------------------      --------------------------
Together:    4 7 3 6 2 5 1      Together:    4 8 3 7 2 6 1 5