“That which we need the most will be found where we least want to look.” - Carl Jung.

# 48. Sort List

## Description

Given the `head` of a linked list, return the list after sorting it in ascending order.

## Solution

Merge sort is constantly used when it comes to sort a linked list. This question also appears in my algorithm course's final exam.

• Runtime: `O(nlgn)`
• Space: `O(lgn)` - O(lgn) is the call graph
``````1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
14        // empty list or only one element
19        ListNode* right = sortList(mid);
20
21        return merge(left,right);
22    }
23
24    // famous two finger algorithm
25    ListNode* merge(ListNode* f1, ListNode* f2){
26        ListNode* sentinel = new ListNode(0);
27        ListNode* it = sentinel;
28
29        while(f1&&f2){
30            if(f1->val < f2->val) {
31                it->next = f1;
32                f1 = f1->next;
33            }
34            else{
35                it->next = f2;
36                f2 = f2->next;
37            }
38            it = it->next;
39        }
40
41        while(f1){
42            it->next = f1;
43            f1 = f1->next;
44            it = it->next;
45        }
46
47        while(f2){
48            it->next = f2;
49            f2 = f2->next;
50            it = it->next;
51        }
52
53        return sentinel->next;
54    }
55
57        ListNode *midPrev = nullptr;
59            midPrev = (midPrev == nullptr) ? head : midPrev->next;
61        }
62        ListNode* mid = midPrev->next;
63        // detach the linked list into two halves
64        midPrev->next = nullptr;
65
66        // return the second half, i.e, the detached
67        return mid;
68    }
69};``````

# 2131. Longest Palindrome by Concatenating Two Letter Words

## Description

You are given an array of strings `words`. Each element of `words` consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from `words` and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return `0`.

A palindrome is a string that reads the same forward and backward.

## Solution

• Runtime: `O(n)`
• Space: `O(n)`
``````1class Solution {
2public:
3    int longestPalindrome(vector<string>& words) {
4        unordered_map<string, int> table;
5        int result = 0;
6        for(auto str: words){
7            string rev(1,str[1]);
8            rev+=str[0];
9            if(table[rev]>0){
10                table[rev]-=1;
11                result+=4;
12            }
13            else{
14                table[str]+=1;
15            }
16        }
17        for(auto it:table){
18            if(it.second>0&&it.first[0]==it.first[1]){
19                result+=2;
20                return result;
21            }
22        }
23
24        return result;
25    }
26};``````

## Description

Given a characters array `tasks`, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer `n` that represents the cooldown period between two `same tasks` (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

## Solution

• Runtime: `O(n)`
• Space: `O(1)` : O(26) to be precise.
``````1class Solution {
2public:
3    int leastInterval(vector<char>& tasks, int n) {
4        unordered_map<char, int> table;
6            table[c]++;
7        }
8
9        int time = 0;
10
11        // greedy algorithm, the most heavy tasks goes first, use a max heap to retrieve the heavies taks in log26
13        for(auto it:table){
14            if(it.second>0)
16        }
17
18        // (a, b):  - a is the remaining cycles needed to complete this task
19        //          - b is the next time this task can be executed
20        queue<pair<int,int>> waitQueue;
21
22        // if there is tasks remaining
24            time++;
25            // if there is work in ready queue
30                if(occur-1>0)
31                    // move the task to waitQueue, and "do" 1 cycle's work
32                    waitQueue.push({occur-1,time+n});
33            }
34
35            // if there is work in the waitQueue
36            if(!waitQueue.empty()){
37                // the front() would always has the smallest wake time
38                // check if we can wake up the earliest task
39                if(waitQueue.front().second<=time){
40                    // wake up the task
42                    waitQueue.pop();
43                }
44            }
45        }
46
47        return time;
48    }
49};``````

# 543. Diameter of Binary Tree

## Description

Given the `root` of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the `root`.

The length of a path between two nodes is represented by the number of edges between them.

## Solution

• Runtime: `O(n)`
• Space: `O(n)` : call stack if the tree is a straight line
``````1/**
2* Definition for a binary tree node.
3* struct TreeNode {
4*     int val;
5*     TreeNode *left;
6*     TreeNode *right;
7*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10* };
11*/
12class Solution {
13public:
14   int diameterOfBinaryTree(TreeNode* root) {
15       int maxD = 0;
16       diamaterHelper(root, maxD);
17       return maxD;
18   }
19
20
21   int diameterHelper(TreeNode* root, int &maxD){
22       if(root==nullptr){
23           return 0;
24       }
25
26       int left = diameterHelper(root->left, maxD);
27       int right = diameterHelper(root->right, maxD);
28
29
30       // two cases, the maximum is the left height + right height
31       // tree rooted at this node is not optimal, pass up the height
32       if(left+right>maxD)
33           maxD = left+right
34       return max(left,right)+1;
35   }
36};``````

# 437. Path Sum III

## Description

Given the `root` of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values along the path equals `targetSum`.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

## Solution

• Runtime: `O(n^2)`
• Space: `O(n)` : call stack if the tree is a straight line
``````1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int pathSum(TreeNode* root, int targetSum) {
15        if(root==nullptr){
16            return 0;
17        }
18        // consider two cases
19        // 1: the root is included in the path -> pathSumInclude
20        // 2: the root is not included in the path -> pathSum
21        return pathSumInclude(root, targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
22    }
23
24    int pathSumInclude(TreeNode* root, long targetSum) {
25        if(root==nullptr){
26            return 0;
27        }
28        // if we find what we wanted, add 1
29        if(root->val==targetSum){
30            // but we still need to recurse because there might be nodes added up to 0
31            return 1+pathSumInclude(root->left, targetSum-root->val)+pathSumInclude(root->right, targetSum-root->val);
32        }
33        else{
34            // we need to recurse using pathSumInclude because the path should be continous
35            return pathSumInclude(root->left, targetSum-root->val)+pathSumInclude(root->right, targetSum-root->val);
36        }
37    }
38};``````

# 74. Search a 2D Matrix

## Description

You are given an `m x n` integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return `true` if `target` is in `matrix` or `false` otherwise.

You must write a solution in `O(log(m * n))` time complexity.

## Solution

If you flatten the matrix in to an one-dimension array with size of `m*n`, the 1d array will be in non decreasing order. Thus, we can perform binary search on the 1d array. The `mid` indice translation is `matrix[mid/n][mid%n]`

• Runtime: `O(lg(m*n))`
• Space: `O(1)`
``````1class Solution {
2public:
3    bool searchMatrix(vector<vector<int>>& matrix, int target) {
4        int m = matrix.size(), n = matrix[0].size();
5        int left = 0, right = m*n-1;
6
7        while(left < right){
8            int mid = (left+right)/2;
9            if(matrix[mid/n][mid%n]<target){
10                left = mid+1;
11            }
12            else if (matrix[mid/n][mid%n]>target)
13            {
14                right = mid-1;
15            }
16            else{
17                return true;
18            }
19        }
20        return matrix[left/n][left%n]==target;
21    }
22};``````

# 33. Search in Rotated Sorted Array

## Description

There is an integer array `nums` sorted in ascending order (with distinct values).

Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (0-indexed). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index 3 and become `[4,5,6,7,0,1,2]`.

Given the array `nums` after the possible rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

## Solution

The only difference between this problem with ordinary binary search is there is a pivot point where the ascending ordered list is rotated. If we can find the pivot point, the problem just rolls back to a binary search problem.

• Runtime: `O(lgn)`
• Space: `O(1)`
``````1class Solution {
2public:
3    int search(vector<int>& nums, int target) {
4        int low = 0, high = nums.size() - 1;
5
6        // find the smallest element => pivot point
7        while (low < high)
8        {
9            int mid = (low + high) / 2;
10
11            if (nums[mid] > nums[high])
12            {
13                low = mid + 1;
14            }
15            else
16            {
17                high = mid ;
18            }
19        }
20        // find the point that is the pivot
21        int pivot = low;
22
23        low = 0, high = nums.size() - 1;
24        // find the element
25        while (low <= high)
26        {
27            int mid = (low + high) / 2;
28            int realmid = (mid + pivot) % nums.size();
29
30            if (nums[realmid] == target)
31            {
32                return realmid;
33            }
34
35            if (nums[realmid] < target)
36            {
37                low = mid+1;
38            }
39            else{
40                high = mid-1;
41            }
42        }
43
44        return -1;
45    }
46};``````

# 108. Convert Sorted Array to Binary Search Tree

## Description

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

## Solution

• Runtime: `O(n)`
• Space: `O(1)`
``````1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    TreeNode* sortedArrayToBST(vector<int>& nums) {
15        if(nums.size()>0){
16            TreeNode *sentinel = new TreeNode();
17            // build the tree rooted the sentinel's left child
18            helper(sentinel, nums, 0, nums.size()-1, true);
19            return sentinel->left;
20        }
21        return nullptr;
22    }
23
24    void helper(TreeNode* parent,vector<int>& nums, int left, int right,bool leftChild ){
25
26        if(left<=right){
27            // get the mid element
28            int mid = (left+right)/2;
29            // create new node
30            TreeNode *temp = new TreeNode(nums[mid]);
31            // attach to parent's left
32            if(leftChild){
33                parent->left = temp;
34            } // attach to parent's right
35            else {
36                parent->right = temp;
37            }
38            // recursive build subtrees
39            helper(temp, nums, left, mid-1, true);
40            helper(temp, nums, mid+1, right, false);
41        }
42    }
43};``````

# 230. Kth Smallest Element in a BST

## Description

Given the `root` of a binary search tree, and an integer `k`, return the `kth` smallest value (1-indexed) of all the values of the nodes in the tree.

## Solution

• Runtime: `O(n)`
• Space: `O(n)`
``````1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int kthSmallest(TreeNode* root, int k) {
15        // this could be done in an inorder traversal
16        // inorder traversal is a form of DFS
17        // use stack to carry the dfs
18        stack<TreeNode*> stack;
19
20        while(!stack.empty()||root){
21            // keep descend to the most left leaf
22            while(root){
23                stack.push(root);
24                root = root -> left;
25            }
26            // traversal backwards
27            root = stack.top();
28            stack.pop();
29
30            if(--k==0){
31                // if the current is kth smallest, return
32                return root->val;
33            }
34            else{
35                // traversal on the right substree
36                root = root ->right;
37            }
38        }
39        return -1;
40    }
41};``````

# 173. Binary Search Tree Iterator

## Description

Implement the `BSTIterator` class that represents an iterator over the in-order traversal of a binary search tree (BST):

`BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.

`boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns false.

`int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()` will return the smallest element in the BST.

You may assume that `next()` calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()` is called.

## Solution

• Runtime: `O(1)`: each operation is constant
• Space: `O(n)`
``````1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class BSTIterator {
13private:
14    vector<int> nums;
15    int ptr = 0;
16
17    void inorder(TreeNode* root){
18        if(root){
19            inorder(root->left);
20            nums.push_back(root->val);
21            inorder(root->right);
22        }
23    }
24
25public:
26    BSTIterator(TreeNode* root) {
27        inorder(root);
28    }
29
30    int next() {
31        return nums[ptr++];
32
33    }
34
35    bool hasNext() {
36        return ptr < nums.size();
37    }
38};
39
40/**
41 * Your BSTIterator object will be instantiated and called as such:
42 * BSTIterator* obj = new BSTIterator(root);
43 * int param_1 = obj->next();
44 * bool param_2 = obj->hasNext();
45 */``````

# 994. Rotting Oranges

## Description

You are given an `m x n` `grid` where each cell can have one of three values:

`0` representing an empty cell, `1` representing a fresh orange, or `2` representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1`.

## Solution

• Runtime: `O(mn)`
• Space: `O(mn)`
``````1class Solution {
2public:
3    int orangesRotting(vector<vector<int>>& grid) {
4        int m = grid.size();
5        int n = grid[0].size();
6        queue<pair<int,int>> rotten;
7        int fresh = 0;
8        // find the intiial rotten oranges
9        // count the initial number of fresh oranges
10        for(int i=0; i<m; i++){
11            for(int j=0; j<n; j++){
12                if(grid[i][j]==1){ // fresh oranges
13                    fresh++;
14                }
15                else if(grid[i][j]==2){ // rotten oranges
16                    rotten.push({i,j});
17                    // grid[i][j] = -1;
18                }
19            }
20        }
21        int mins = 0;
22
23        vector<pair<int,int>> directions = {{0,1},{0,-1},{1,0},{-1,0}};
24
25        while(!rotten.empty() && fresh>0){
26            int times = rotten.size();
27            // take a snapshot of the queue at this minute
28
29            for(int k=0; k<times; k++){
30                auto ro = rotten.front();
31                rotten.pop();
32                for(auto dir : directions) {
33                    int row = ro.first + dir.first;
34                    int col = ro.second + dir.second;
35                    if(row >=0 && row<m && col>=0 && col<n && grid[row][col]==1){
36                        grid[row][col]=2;
37                        rotten.push({row,col});
38                        fresh--;
39                    }
40                }
41            }
42            mins++;
43        }
44
45        return fresh>0?-1:mins;
46    }
47};``````

# 417. Pacific Atlantic Water Flow

## Description

There is an `m x n` rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an `m x n` integer matrix `heights` where `heights[r][c]` represents the height above sea level of the cell at coordinate `(r, c)`.

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates `result` where `result[i] = [ri, ci]` denotes that rain water can flow from cell `(ri, ci)` to both the Pacific and Atlantic oceans.

## Solution

<!-- - Runtime: `O()` - Space: `O()` -->
``````1class Solution {
2public:
3    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
4
5    }
6};``````

# 210. Course Schedule II

## Description

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`.

For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

## Solution

• Runtime: `O()`
• Space: `O()`