// Minimum Path Sum
int minPathSum(vector<vector<int>>& grid) {
    if (grid.empty())
        return 0;
    const int n = grid.size(), m = grid[0].size();
    int f[n][m];
    f[0][0] = grid[0][0];
    for (int i = 1; i < n; i++)
        f[i][0] = f[i - 1][0] + grid[i][0];
    for (int j = 1; j < m; j++)
        f[0][j] = f[0][j - 1] + grid[0][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
    return f[n - 1][m - 1];
}
// Minimum Two Path Sum
// Consider diagonal DP

// Search in Rotated Sorted Array
int search(vector<int>& nums, int target) {
    if (nums.empty())
        return -1;
        
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[low] <= nums[mid]) {
            if (nums[mid] > target && nums[low] <= target)
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            if (nums[mid] < target && nums[high] >= target)
                low = mid + 1;
            else
                high = mid - 1;
        }
    }        
    return -1;
}
// Search in Rotated Sorted Array II
bool search(vector<int>& nums, int target) {
    if (nums.empty())
        return false;
        
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return true;
        } else if (nums[low] < nums[mid]) {
            if (nums[mid] > target && nums[low] <= target)
                high = mid - 1;
            else
                low = mid + 1;
        } else if (nums[low] > nums[mid]) {
            if (nums[mid] < target && nums[high] >= target)
                low = mid + 1;
            else
                high = mid - 1;
        } else {
            low++;
        }
    }        
    return false;
}

// Copy List with Random Pointer (LeetCode)
RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == NULL)
        return NULL;
    unordered_map<RandomListNode*, RandomListNode*> cache;
    RandomListNode dummy(-1);
    RandomListNode *p = head, *q = &dummy;
    while (p) {
        q->next = new RandomListNode(p->label);
        q = q->next;
        cache[p] = q;
        p = p->next;
    }
    p = head;
    while (p) {
        if (p->random)
            cache[p]->random = cache[p->random];
        p = p->next;
    }
    return dummy.next;
}

// Binary Tree Level Order Traversal
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> q, p;
    vector<vector<int>> res;
    if (root)
        q.push(root);
    while (!q.empty()) {
        vector<int> level;
        while (!q.empty()) {
            level.push_back(q.front()->val);
            if (q.front()->left)
                p.push(q.front()->left);
            if (q.front()->right)
                p.push(q.front()->right);
            q.pop();
        }
        swap(p, q);
        res.push_back(level);
    }
    return res;
}

// Divide Two Integers
// Divide two integers without using multiplication, division and mod operator.
// If it is overflow, return MAX_INT.
// O((log n)^2)
int divide(int dividend, int divisor) {
    if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) // Overflow
        return INT_MAX;
    bool negative = (divisor > 0) ^ (dividend > 0);
    long long dvd = dividend, dvs = divisor;
    dvd = abs(dvd); dvs = abs(dvs);
    int res = 0;
    while (dvd >= dvs) {
        long long temp = dvs;
        int mutiple = 1;
        while (dvd >= (temp << 1)) {
            temp <<= 1;
            mutiple <<= 1;
        }
        dvd -= temp;
        res += mutiple;
    }
    return negative ? -res : res;
}
// O(1)
int divide(int dividend, int divisor) {
    if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) // Overflow
        return INT_MAX;
    bool negative = (divisor > 0) ^ (dividend > 0);
    // Transform to unsigned int
    unsigned int dvd = (dividend > 0) ? dividend : -dividend;
    unsigned int dvs = (divisor > 0) ? divisor : -divisor;
    // Shift W (= 32) times
    const int W = sizeof(int) * 8;
    int res = 0;
    for (int i = W - 1; i >= 0; i--) {
        if ((dvd >> i) >= dvs) { // dvd >= 2^i * dvs
            res = (res << 1) | 1; // res = 2 * res + 1
            dvd -= (dvs << i);
        } else
            res <<= 1; // res = 2 * res
    }
    return negative ? -res : res;
}

// Regular Expression Matching
// Implement regular expression matching with support for '.' and '*'.
// '.' Matches any single character.
// '*' Matches zero or more of the preceding element.
bool isMatch(string s, string p) {
    if (p.empty())
        return s.empty();
    if (p.size() > 1 && p[1] == '*') {
        return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
    } else {
        return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
    }
}
// Dynamic Programming
bool isMatch(string s, string p) {
    // f[i][j]: if s[0..i-1] matches p[0..j-1]
    int m = s.size(), n = p.size();
    vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
    
    f[0][0] = true;
    for (int i = 1; i <= m; i++)
        f[i][0] = false;
    for (int j = 2; j <= n; j++)
        f[0][j] = (p[j - 1] == '*' && f[0][j - 2]);
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= m; i++) {
            if (p[j - 1] == '*')
                f[i][j] = f[i][j - 2] || (f[i - 1][j] && (p[j - 2] == '.' || s[i - 1] == p[j - 2]));
            else
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
        }
    }
    return f[m][n];    
}

// Wildcard Matching
// Implement wildcard pattern matching with support for '?' and '*'.
// '?' Matches any single character.
// '*' Matches any sequence of characters (including the empty sequence).
// Time Limit Exceeded
bool isMatch(const string& s, const string& p) {
    if (p.empty())
        return s.empty();
    if (p[0] == '*')
        return isMatch(s, p.substr(1)) || (!s.empty() && isMatch(s.substr(1), p));
    return !s.empty() && (p[0] == '?' || s[0] == p[0]) && isMatch(s.substr(1), p.substr(1));
}
// Time Limit Exceeded
bool isMatch(const string& s, const string& p) {
    if (p.empty())
        return s.empty();
    if (p[0] == '*') {
        int i = 1;
        while (i < p.size() && p[i] == '*')
            i++; // Skip continous '*'
        return isMatch(s, p.substr(i)) || (!s.empty() && isMatch(s.substr(1), p));
    }
    return !s.empty() && (p[0] == '?' || s[0] == p[0]) && isMatch(s.substr(1), p.substr(1));
}
// Dynamic Programming
bool isMatch(string s, string p) {
    // f[i][j]: is s[0..i-1] matches p[0..j-1]
    int m = s.size(), n = p.size();
    vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
    f[0][0] = true;
    for (int i = 1; i <= m; i++)
        f[i][0] = false;
    for (int j = 1; j <= n; j++)
        f[0][j] = p[j - 1] == '*' && f[0][j - 1];
    for (int j = 1; j <= n; j++)
        for (int i = 1; i <= m; i++)
            if (p[j - 1] == '*')
                f[i][j] = f[i][j - 1] || f[i - 1][j];
            else
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
    return f[m][n];
}

// Longest Consecutive Sequence
// Union-Find
int longestConsecutive(vector<int>& nums) {
    vector<int> parent(nums.size(), -1), rank(nums.size(), 1);
    unordered_map<int, int> cache;
    for (int i = 0; i < nums.size(); i++) {
        cache[nums[i]] = i;
    }
    for (auto iter = cache.begin(); iter != cache.end(); iter++) {
        int num = iter->first;
        if (cache.find(num + 1) != cache.end())
            Union(parent, rank, iter->second, cache[num + 1]);
    }
    int max_length = 0;
    for (int r : rank)
        max_length = max(max_length, r);
    return max_length;
}

int find(vector<int>& parent, int i) {
    if (parent[i] == -1)
        return i;
    parent[i] = find(parent, parent[i]); // uses path compression technique
    return parent[i];
}

void Union(vector<int>& parent, vector<int>& rank, int i, int j) {
    // can't use the function name union(), union is a c++ keyword
    int x = find(parent, i);
    int y = find(parent, j);
    if (x != y) {
        if (rank[x] <= rank[y]) {
            parent[x] = y;
            rank[y] += rank[x];
        }
        else {
            parent[y] = x;
            rank[x] += rank[y];
        }
    }
}
// 哈希表 只更新線段端點(diǎn)的長(zhǎng)度
int longestConsecutive(vector<int>& nums) {
    int max_length = 0;
    unordered_map<int, int> sequence; // pair (num, length)
    for (int num : nums) {
        if (sequence.find(num) != sequence.end())
            continue;
        int left = (sequence.find(num - 1) != sequence.end()) ? sequence[num - 1] : 0;
        int right = (sequence.find(num + 1) != sequence.end()) ? sequence[num + 1] : 0;
        int length = 1 + left + right;
        sequence[num] = length;
        sequence[num - left] = length;
        sequence[num + right] = length;
        max_length = max(max_length, length);
    }
    return max_length;
}

// Edit Distance
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();            
    int D[m + 1][n + 1];
    for (int i = 0; i <= m; i++)
        D[i][0] = i;
    for (int j = 1; j <= n; j++)
        D[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1])
                D[i][j] = min(min(D[i - 1][j] + 1, D[i][j - 1] + 1), D[i - 1][j - 1]);
            else
                D[i][j] = min(min(D[i - 1][j] + 1, D[i][j - 1] + 1), D[i - 1][j - 1] + 1);
        }
    }
    return D[m][n];
}

// Populating Next Right Pointers in Each Node II
// 既然上一層的節(jié)點(diǎn)已經(jīng)通過(guò)next指針連起來(lái)了，那么就只要能得到上一層的第一個(gè)節(jié)點(diǎn)就可以依次把上一層節(jié)點(diǎn)的子節(jié)點(diǎn)串聯(lián)起來(lái)了
// 通過(guò)添加一個(gè)dummy假節(jié)點(diǎn)來(lái)標(biāo)記當(dāng)前行的首節(jié)點(diǎn)
void connect(TreeLinkNode *root) {
    while (root) {
        TreeLinkNode dummy(-1);
        TreeLinkNode *p = &dummy, *q = root;
        while (q) {
            if (q->left) {
                p->next = q->left;
                p = p->next;
            }
            if (q->right) {
                p->next = q->right;
                p = p->next;
            }
            q = q->next;
        }
        root = dummy.next;
    }
}

// Binary Search Tree Iterator
// In-order Traveral Binary Tree Iterator
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *p = root;
        while (p) {
            s.push(p);
            p = p->left;
        }
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }
    /** @return the next smallest number */
    int next() {
        int res = s.top()->val;
        TreeNode *p = s.top()->right;
        if (p) {
            while (p) {
                s.push(p);
                p = p->left;
            }
        } else {
            p = s.top();
            s.pop();
            while (!s.empty() && p == s.top()->right) {
                p = s.top();
                s.pop();
            }
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *p = root;
        while (p) {
            s.push(p);
            p = p->left;
        }
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }
    /** @return the next smallest number */
    int next() {
        int res = s.top()->val;
        TreeNode *p = s.top()->right;
        s.pop();
        while (p) {
            s.push(p);
            p = p->left;
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};

// Kth Largest Element in an Array
// Sort 
// O(N lg N) running time + O(1) memory
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};
// Use a min oriented priority queue storing the K-th largest values
// O(N lg K) running time + O(K) memory
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minpq;
        for (int i = 0; i < k; i++)
            minpq.push(nums[i]);
        for (int i = k; i < nums.size(); i++)
            if (nums[i] > minpq.top()) {
                minpq.pop();
                minpq.push(nums[i]);
            }
        return minpq.top();
    }
};
// Use the selection algorithm (based on the partion method - the same one as used in quicksort)
// O(N) best case / O(N^2) worst case / amortized O(N) running time + O(1) memory
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        random_shuffle(nums.begin(), nums.end());        
        k = nums.size() - k;
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = partition(nums, low, high);
            if (mid < k)
                low = mid + 1;
            else if (mid > k)
                high = mid - 1;
            else
                break;                
        }
        return nums[k];
    }
    int partition(vector<int>& nums, int low, int high) {
        int pivot = nums[low], i = low;
        // nums[0..i] <= pivot, nums[i+1..j-1] > pivot, nums[j..n-1] unknown
        for (int j = low + 1; j <= high; j++) {
            if (nums[j] <= pivot)
                swap(nums[++i], nums[j]);
        }
        swap(nums[low], nums[i]);
        return i;
    }
};

// Minimum Window Substring
// Hash Table + Two Pointers + String
string minWindow(string s, string t) {
    string res = "";
    unordered_map<char, int> pattern, window;
    int count = 0, min_window = INT_MAX;
    for (char c : t)
        pattern[c]++;
    for (int start = 0, end = 0; end < s.size(); end++) {
        char c = s[end];
        if (pattern.find(c) != pattern.end()) {
            window[c]++;
            if (window[c] <= pattern[c])
                count++;
            if (count == t.size()) {
                while (pattern.find(s[start]) == pattern.end() || window[s[start]] > pattern[s[start]]) {
                    if (pattern.find(s[start]) != pattern.end())
                        window[s[start]]--;
                    start++;
                }
                if (end - start + 1 < min_window) {
                    min_window = end - start + 1;
                    res = s.substr(start, min_window);
                }       
            }
        }
    }
    return res;
}

// Longest Substring Without Repeating Characters
// Hash Table + Two Pointers + String
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> cache;
        int start = 0, max_length = 0;
        for (int end = 0; end < s.size(); end++) {
            if (cache.find(s[end]) == cache.end() || cache[s[end]] < start) {
                cache[s[end]] = end;
                max_length = max(max_length, end - start + 1);
            } else {
                start = cache[s[end]] + 1;
                cache[s[end]] = end;
                max_length = max(max_length, end - start + 1);
            }
        }
        return max_length;
    }
};

// Decode Ways
int numDecodings(string s) {
    if (s.empty() || s[0] == '0')
        return 0;
    vector<int> f(s.size() + 1);
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= s.size(); i++) {
        if (s[i - 1] == '0') {
            if (!(s[i - 2] == '1' || s[i - 2] == '2'))
                return 0;
            f[i] = f[i - 2];    
        } else if (s[i - 1] >= '1' && s[i - 1] <= '6') {
            f[i] = ((s[i - 2] == '1' || s[i - 2] == '2') ? (f[i - 1] + f[i - 2]) : f[i - 1]);
        } else {
            f[i] = ((s[i - 2] == '1') ? (f[i - 1] + f[i - 2]) : f[i - 1]);
        }          
    }
    return f[s.size()];
}

// LCA of Binary Tree
// Find the paths to p and q and then find the last node where the paths match
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root == p || root == q)
        return root;
    vector<TreeNode*> path_p, path_q;
    dfs(root, p, q, {}, path_p, path_q);
    int i = 0;
    while (path_p[i] == path_q[i])
        i++;
    return path_p[i - 1];
}
void dfs(TreeNode* root, TreeNode* p, TreeNode* q, vector<TreeNode*> path, vector<TreeNode*> &path_p, vector<TreeNode*> &path_q) {
    if (root == NULL)
        return;
    path.push_back(root);
    if (root == p)
        path_p = path;
    if (root == q)
        path_q = path;
    dfs(root->left, p, q, path, path_p, path_q);
    dfs(root->right, p, q, path, path_p, path_q);
}
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == NULL || root == p || root == q)
        return root;
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    if (l != NULL && r != NULL)
        return root;
    if (l != NULL)
        return l;
    return r;
}

// Task Scheduler
int leastInterval(vector<char>& tasks, int n) {
    vector<int> count(26);
    for (char c : tasks)
        count[c - 'A']++;
    sort(count.begin(), count.end());
    int timer = 0;
    while (count[25] > 0) {
        for (int i = 0, j = 25; i < n + 1; i++, j--) {
            if (j >= 0 && count[j] > 0)
                count[j]--;
            else if (count[25] == 0)
                break;
            timer++;
        }
        sort(count.begin(), count.end());
    }
    return timer;
}
int leastInterval(vector<char>& tasks, int n) {
    int count[26];
    for (int i = 0; i < 26; i++)
        count[i] = 0;
    for (char c : tasks)
        count[c - 'A']++;
    sort(count, count + 26, greater<int>()); // sort in decreasing order
    int timer = 0;
    int j = 25;
    while (j >= 0 && count[j] == 0)
        j--;
    while (j >= 0) {
        timer += ((j >= n || count[0] > 1) ? n + 1 : j + 1); // j + 1 means #tasks left
        for (int i = 0; i <= j && i < n + 1; i++)
            count[i]--;
        sort(count, count + j + 1, greater<int>());
        while (j >= 0 && count[j] == 0)
            j--;
    }
    return timer;
}

// Combination Sum
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<vector<int>>> sums(1 + target);
    sums[0] = vector<vector<int>>(1); // sums[0].push_back(vector<int>());
    for (int num : candidates) {
        for (int i = num; i <= target; i++) {
            vector<vector<int>> copy(sums[i - num].begin(), sums[i - num].end());
            for (int j = 0; j < copy.size(); j++)
                copy[j].push_back(num);
            sums[i].insert(sums[i].end(), copy.begin(), copy.end());
        }
    }
    return sums[target];
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    combinationSum(0, candidates, target, path, res);
    return res;
}
void combinationSum(int i, vector<int>& candidates, int target, vector<int> &path, vector<vector<int>> &res) {
    if (i == candidates.size()) {
        if (target == 0)
            res.push_back(path);
        return;
    }
    for (int num = 0; num <= target; num += candidates[i]) {
        combinationSum(i + 1, candidates, target - num, path, res);
        path.push_back(candidates[i]);
    }
    for (int num = 0; num <= target; num += candidates[i])
        path.pop_back();
}

// Flatten Binary Tree to Linked List
void flatten(TreeNode* root) {
    TreeNode *p = root;
    stack<TreeNode*> s;
    while (p) {
        if (p->right)
            s.push(p->right);
        if (p->left) {
            p->right = p->left;
            p->left = NULL;
        } else if (!s.empty()) {
            p->right = s.top();
            s.pop();
        }
        p = p->right;
    }
}

// Reverse Words in a String
// Given an input string, reverse the string word by word.
// For example, given s = "the sky is blue", return "blue is sky the".
// For C programmers: Try to solve it in-place in O(1) space.
/* Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
*/
void reverseWords(string &s) {
    vector<string> words;
    string cur = "";
    for (char c : s) {
        if (c == ' ') {
            if (cur != "")
                words.push_back(cur);
            cur = "";
        } else {
            cur += c;
        }
    }
    if (cur != "")
        words.push_back(cur);
    if (words.empty()) {
        s = "";
        return;
    }
    reverse(words.begin(), words.end());
    s = words[0];
    for (int i = 1; i < words.size(); i++)
        s += (' ' + words[i]);
}
// In place simple solution
// First, reverse the whole string, then reverse each word.
void reverseWords(string &s) {
    // i: the beginning of one word, j: the end of one word(including one trailing space)
    // k: the current position available for insertion
    reverse(s.begin(), s.end());
    int i = 0, j, k = 0; 
    while (i < s.size() && s[i] == ' ')
        i++;
    while (i < s.size()) {
        if (k != 0)
            s[k++] = ' ';
        j = i;
        while(j < s.size() && s[j] != ' ')
            s[k++] = s[j++];
        reverse(s.begin() + k - (j - i), s.begin() + k);
        i = j + 1;
        while (i < s.size() && s[i] == ' ')
            i++;
    }
    s.erase(s.begin() + k, s.end()); // s.erase(k);
}

// Kth Smallest Element in a Sorted Matrix
// Heap
struct Element {
    int i, j, num;
    Element(int i, int j, int num): i(i), j(j), num(num) {}
    bool operator< (const Element &other) const {
        return num > other.num;
    }
};
int kthSmallest(vector<vector<int>>& matrix, int k) {
    const int n = matrix.size(), m = matrix[0].size();
    priority_queue<Element> pq;
    for (int i = 0; i < n; i++)
        pq.push(Element(i, 0, matrix[i][0]));
    for (int ii = 0; ii < k - 1; ii++) {
        Element e = pq.top();
        pq.pop();
        if (e.j + 1 < m)
            pq.push(Element(e.i, e.j + 1, matrix[e.i][e.j + 1]));
    }
    return pq.top().num;
}
// Binary Search
int kthSmallest(vector<vector<int>>& matrix, int k) {
    // Find the smallest number num which #{numbers in the matrix <= num} >= k
    const int n = matrix.size(), m = matrix[0].size();
    int low = matrix[0][0], high = matrix[n - 1][m - 1];
    while (low < high) {
        int mid = low + (high - low) / 2;
        int count = 0, i = n - 1, j = 0;
        while (i >= 0 && j < m) {
            if (matrix[i][j] <= mid) {
                count += (i + 1);
                j++;
            } else {
                i--;
            }
        }
        if (count >= k)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

// Largest Rectangle in Histogram
int largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    heights.push_back(0);
    
    int max_sum = 0, i = 0;
    while (i < heights.size()) {
        if (s.empty() || heights[i] > heights[s.top()]) {
            s.push(i);
            i++;
        } else {
            int j = s.top();
            s.pop();
            max_sum = max(max_sum, heights[j] * (s.empty() ? i : (i - 1 - s.top())));
        }
    }
    return max_sum;
}