Leetcode Programming Skills study plan list I

  1. Day 1 Array
  2. Day 2 Operator
  3. Day 3 Conditional Statements
  4. Day 4 Loop
  5. Day 5 Function
  6. Day 6 Array
  7. Day 7 Array
  8. Day 8 String
  9. Day 9 String
  10. Day 10 Linked List & Tree
  11. Day 11 Containers & Libraries
  12. Day 12 Class & Object
class Solution {
public:
    int countOdds(int low, int high) {
        int total = (high - low) >> 1;
        if (low & 1 or high & 1) total++; 
        return total;
    }
};
class Solution {
public:
    double average(vector<int>& salary) {
        int min_salary = salary[0], max_salary = salary[0];
        double total = 0;
        for (int amt : salary){
            min_salary = min(min_salary, amt);
            max_salary = max(max_salary, amt);
            total = total + amt;
        }
        return (total - min_salary - max_salary) / (salary.size() -  2);    
    }
};
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int nbits = 0;
        while (n){
            nbits += n & 1;
            n >>= 1;
        }
        return nbits;
    }
};
class Solution {
public:
    int subtractProductAndSum(int n) {
        int accum_prod=1, accum_sum=0, digit;
        while (n){
            digit = n % 10;
            n = n / 10;
            accum_prod *= digit;
            accum_sum += digit;
        }
        return accum_prod - accum_sum;
    }
};
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int i, int j)->bool {return j < i;});
        int result = 0;
        for (int i=0; i < nums.size() - 2; i++) {
            if (nums[i] < nums[i+1] + nums[i+2]) {
                result = nums[i] + nums[i+1] + nums[i+2];
                break;
            }
        }
        return result;
    }
};
class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int min_dist = INT_MAX, nearest_point_idx=-1;
        
        auto manhattan_dist = [](int x1, int y1, int x2, int y2) -> int {
            return abs(y2 - y1) + abs(x2 - x1);
        };
        
        for (int i = 0; i < points.size(); i++) {
            auto point = points[i];
            if (point[0] == x or point[1] == y) {
                int dist = manhattan_dist(point[0], point[1], x, y);
                if (dist < min_dist) {
                    min_dist = dist;
                    nearest_point_idx = i;
                }
            }
        }
        return nearest_point_idx;
    }
};
class Solution {
public:
    int arraySign(vector<int>& nums) {
        int sign = 1;
        for (auto num: nums) {
            if (num == 0) return 0;
            else if (num > 0) sign *= 1;
            else sign *= -1;
        }
        return sign;
    }
};
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        set<int> nums; 
        int min_val = arr[0], max_val = arr[0];
        
        for (auto num: arr) {
            min_val = min(min_val, num);
            max_val = max(max_val, num);
            nums.insert(num);
        }
        
        if (max_val == min_val) return true;
        
        if ((max_val - min_val) % (arr.size() - 1)) return false;
        
        int delta = (max_val - min_val) / (arr.size() - 1);
        for (int curr = min_val; curr + delta <= max_val; curr += delta) {
            if (not nums.count(curr)) return false;
        }
        return true;
    }
};
class Solution {
public:
    bool isHappy(int n) {
        set<int> seen;
        while (not seen.count(n)) {
            seen.insert(n);
            int m = 0, d;
            while (n > 0) {
                d = n % 10;
                m += d * d;
                n /= 10;
            }
            n = m;
        }
        return n == 1;
    }
};
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        char c11, c12, c21, c22;
        int num_diff = 0;
        for (int i = 0; i < s1.size(); i++){
            if (s1[i] != s2[i]) {
                num_diff++;
                if (num_diff == 1) {
                    c11 = s1[i];
                    c21 = s2[i];
                }
                if (num_diff == 2) {
                    c12 = s1[i];
                    c22 = s2[i];
                }
            }
            if (num_diff > 2) return false;
        }
        if (num_diff == 0) return true;
        if (num_diff == 1) return false;
        return (c11 == c22 and c21 == c12);
    }
};
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> result;
        if (root == nullptr) return result;
        stack<Node*> s;
        s.push(root);
        while (not s.empty()) {
            auto node = s.top();
            s.pop();
            result.push_back(node->val);
            for (int i=node->children.size()-1; i >= 0; i--) {
                s.push(node->children[i]);
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> s;
        vector<int> result;
        
        for (auto num: nums2) {
            while (not s.empty() and s.top() < num) {
                map[s.top()] = num;
                s.pop();
            }
            s.push(num);
        }
        
        for (auto num: nums1) {
            if (not map.count(num)) result.push_back(-1);
            else result.push_back(map[num]);    
        }
        return result;
    }
};
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x1 = coordinates[0][0], y1 = coordinates[0][1];
        int x2 = coordinates[1][0], y2 = coordinates[1][1];
        
        if (x1 == x2) {
            for (auto point: coordinates) {
                if (point[0] != x1) return false;
            }
        } else {
            double slope, intercept;
            slope = (y2 - y1) * 1.0 / (x2 - x1);
            intercept = y1 - x1 * slope;
            
            for (auto point: coordinates) {
                int expected_y = slope * point[0] + intercept;
                if (expected_y != point[1]) return false;
            }
        }
        return true;        
    }
};
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int total = 0, n = arr.size();
        for (int i = 0; i < n; ++i) {
            total += arr[i] * (((i + 1) * (n - i) + 1) / 2);
        }
        return total;
    }
};
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0, r = 0;
        while (r <  nums.size()) {
            while (r < nums.size() and nums[r] == 0) r++;
            if (r < nums.size()) swap(nums[l], nums[r]);
            l++;
            r++;
        }
    }
};
class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int max_wealth=accounts[0][0];
        for (auto account: accounts) {
            int total = accumulate(account.begin(), account.end(), 0);
            max_wealth = max(max_wealth, total);
        }
        return max_wealth;
    }
};
class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int total=0, r, c, n=mat.size();
        
        r = 0, c = 0; 
        while (0 <= r and r < n and 0 <= c and  c < n) {
            total += mat[r++][c++];
        }
        r = 0, c = n - 1;
        while (0 <= r and r < n and 0 <= c and c < n) {
            total += mat[r++][c--];
        }
        if (n % 2) total -= mat[n / 2][n / 2];
        return total;
    }
};
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int nrow=mat.size(), ncol=mat[0].size(), i=0;
        if (nrow * ncol != r * c) return mat;
        vector<vector<int>> result(r);
        while (i < r * c) {
            int val = mat[i/ncol][i%ncol];
            result[i/c].push_back(val);
            i++;
        }
        return result;
    }
};
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string merged;
        auto it1 = word1.begin(), it2 = word2.begin();
        while (it1 < word1.end() or it2 < word2.end()) {
            if (it1 < word1.end()) merged.push_back(*it1++);
            if (it2 < word2.end()) merged.push_back(*it2++);
        }
        return merged;
    }
};
class Solution {
public:
    string interpret(string command) {
        string result;
        for (auto i=0; i < command.size(); ) {
            if (command[i] == 'G') {
                result += 'G';
                i += 1;
            } else if (command.compare(i, 2, "()") == 0) {
                result += 'o';
                i += 2;
            } else {
                result += "al";
                i += 4;
            }
        }
        return result;
    }
};
class Solution {
public:
    char findTheDifference(string s, string t) {
        char diff=0;
        for (auto c: s) diff ^= c;
        for (auto c: t) diff ^= c;
        return diff;
    }
};
class Solution {
public:
    string toLowerCase(string s) {
        for (int i=0; i < s.size(); i++) {
            if (s[i] >= 'A' and s[i] <= 'Z') s[i] += 32;
        }
        return s;
    }
};
class Solution {
public:
    string freqAlphabets(string s) {
        string result;
        int i = 0;
        while (i < s.size()) {
            if (i + 2 < s.size() and s[i+2] == '#') {
                result.push_back('j' + stoi(s.substr(i, 2)) - 10);
                i += 3;
            } else {
                result.push_back('a' + stoi(s.substr(i, 1)) - 1);
                i++;
            }
        }
        return result;
    }
};
class Solution {
public:
    bool is_ordered(string& w1, string&w2, unordered_map<char, int>& rank) {
        for (int i=0; i < min(w1.size(), w2.size()); i++) {
            if (rank[w1[i]] < rank[w2[i]]) return true;
            if (rank[w1[i]] > rank[w2[i]]) return false;
        }
        return w1.size() <= w2.size();
    }

    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> rank;
        for (int i=0; i < order.size(); i++) {
            rank[order[i]] = i;
        }
        for (int i=0; i < words.size() -1; i++) {
            if (not is_ordered(words[i], words[i+1], rank)) return false;
        }
        return true;
    }
};
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int val = 0;
        while (head != nullptr) {
            val <<= 1;
            val += head->val;
            head = head->next;
        }
        return val;
    }
};
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto slow=head, fast=head;
        while (fast and fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (not root) return 0;
        
        int max_depth = 0;
        
        stack<pair<TreeNode*, int>> s;
        s.push({root, 1});
        
        while (not s.empty()) {
            auto node = s.top();
            s.pop();
            max_depth = max(max_depth, node.second);
            
            if (node.first->left) s.push({node.first->left, node.second + 1});
            if (node.first->right) s.push({node.first->right, node.second + 1});
        }
        return max_depth;
    }
};
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int total=0;
        
        stack<pair<TreeNode*, int>> s;
        s.push({root, 0});
        
        while (not s.empty()) {
            auto p = s.top(); s.pop();
            TreeNode* node = p.first;
            int is_left = p.second;
            if (is_left and not (node->left or node->right)) {
                total += node->val;
            }
            if (node->left) s.push({node->left, 1});
            if (node->right) s.push({node->right, 0});
        }
        return total;
    }
};
#include <bit>


class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(
            arr.begin(), 
            arr.end(), 
            [](int a, int b) -> bool {
                int a_bits = __popcount(a), b_bits = __popcount(b);
                if (a_bits == b_bits) return a < b;
                return  a_bits < b_bits;
            }
        );
        return arr;
    }
};
class MyQueue {
    stack<int> instack;
    stack<int> outstack;

public:
    MyQueue() {}
    
    void push(int x) { instack.push(x); }
    
    int pop() {
        shuffle();
        int val = outstack.top();
        outstack.pop();
        return val;
    }
    
    void shuffle() {
        if (outstack.empty()) {
            while (instack.size()) {
                int val = instack.top();
                instack.pop();
                outstack.push(val);
            }
        }
    }
    
    int peek() {
        shuffle();
        return outstack.top();
    }
    
    bool empty() { return instack.size() + outstack.size() == 0;}
};
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> char_freq;
        for (char c: s) {
            if (char_freq.count(c)) char_freq[c]++;
            else char_freq[c] = 1;
        }
        for (char c: t) {
            if (not char_freq.count(c)) return false;
            else {
                char_freq[c]--;
                if (char_freq[c] == 0) char_freq.erase(c);
            }
        }
        return char_freq.size() == 0;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> m;
        for (int num:nums) {
            if (m.count(num)) return true;
            m.insert(num);
        }
        return false;
    }
};
class ParkingSystem {
private:    
    vector<int> car_counts;
public:
    ParkingSystem(int big, int medium, int small) {
        car_counts = {big, medium, small};
    }
    
    bool addCar(int carType) {
        return --car_counts[carType-1] >= 0;
    }
};
class NumArray {
private:
    vector<int> prefix_sum;
public:
    NumArray(vector<int>& nums) {
        prefix_sum = {0};
        int accum = 0;
        for (auto num: nums) {
            accum += num;
            prefix_sum.push_back(accum);
        }
    }
    
    int sumRange(int left, int right) {
        return prefix_sum[right + 1] - prefix_sum[left];
    }
};

Leetcode Programming Skills study plan list II

  1. Day 1
  2. Day 2
  3. Day 3
  4. Day 4
  5. Day 5
  6. Day 6
  7. Day 7
  8. Day 8
  9. Day 9
  10. Day 10
  11. Day 11
  12. Day 12
  13. Day 13
  14. Day 14
  15. Day 15
  16. Day 16
  17. Day 17
  18. Day 18
  19. Day 19
  20. Day 20
class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool asc=true, dsc=true;
        for (int i=0; i<nums.size()-1; i++){
            if (nums[i+1] > nums[i]) dsc=false;
            if (nums[i+1] < nums[i]) asc=false;
        }
        return asc or dsc;
    }
};
class Solution {
private:
    vector<int> table(string p) {
        int m = p.size();
        vector<int> lps = {0, 0};
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j and p[i] != p[j]) j = lps[j];
            if (p[i] == p[j]) j++;
            lps.push_back(j);
        }
        return lps;
    }

    int match(string s, string p) {
        int n=s.size(), m=p.size();
        vector<int> lps = table(p);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j and s[i] != p[j]) j = lps[j];
            if (s[i] == p[j]) j++;
            if (j == m) return i - m + 1;
        }
        return -1;
    }        
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        return match(haystack, needle);
    }
};
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        unordered_map<TreeNode*, int> heights;
        heights[nullptr] = 0;
        stack<pair<TreeNode*, int>> tour;
        tour.push({root, 0});
        
        while (not tour.empty()) {
            auto element = tour.top(); tour.pop();
            auto node = element.first;
            int backtrack = element.second;
            if (node == nullptr) continue;
            if (backtrack) {
                int l = heights[node->left], r = heights[node->right];
                if (r > l + 1 or l > r + 1) return false;
                heights[node] = max(l, r) + 1;
            } else {
                tour.push({node, 1});
                tour.push({node->left, 0});
                tour.push({node->right, 0});
            }
        }
        return true;
    }
};
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> table = {0, 0};
        int j = 0;
        
        for (int i = 1; i < n; i++) {
            while (j > 0 and s[i] != s[j]) j = table[j];
            if (s[i] == s[j])              j++;
            table.push_back(j);
        }
        return (table[n] and table[n] % (n - table[n]) == 0);
        
    }
};
class Solution {
private:    
    int eval(int num1, int num2, string op) {
        if (op == "+") return num1 + num2;
        if (op == "-") return num1 - num2;
        if (op == "*") return num1 * num2;
        if (op == "/") return num1 / num2;
        return 0;
    }
public:
    int evalRPN(vector<string>& tokens) {
        unordered_set<string> operators = {"+", "-", "*", "/"};
        stack<int> partials;
        
        for (auto token: tokens) {
            if (operators.count(token)) {
                int num2 = partials.top(); partials.pop();
                int num1 = partials.top(); partials.pop();
                partials.push(eval(num1, num2, token));
            } else {
                partials.push(stoi(token));
            }
        }
        return partials.top();
    }
};
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        for (int i = digits.size() - 1; i >= 0; --i) {
            auto result = div(digits[i] + carry, 10);
            digits[i] = result.rem;
            carry = result.quot;
        }
        if (carry) digits.insert(digits.begin(), carry);
        return digits;
    }
};
class Solution {
private:
    bool is_sub_path_dfs(ListNode* lnode, TreeNode* tnode) {
        if (lnode->val != tnode->val) return false;
        if (lnode->next == nullptr) return true;
        bool l_ok = false, r_ok = false; 
        if (tnode->left) l_ok = is_sub_path_dfs(lnode->next, tnode->left);
        if (tnode->right) r_ok = is_sub_path_dfs(lnode->next, tnode->right);
        return l_ok or r_ok;
    }
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        
        while (not s.empty()) {
            auto tnode = s.top(); s.pop();
            if (is_sub_path_dfs(head, tnode)) return true;
            if (tnode->left) s.push(tnode->left);
            if (tnode->right) s.push(tnode->right);
        }
        return false;
    }
};
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" or num2 == "0") return "0";
        
        int l1 = num1.size(), l2 = num2.size();
        
        vector<int> result(l1+l2, 0);
        
        for (int i = l1-1; i >= 0; i--) {
            int d1 = num1[i] - '0';
            for (int j = l2-1; j >= 0; j--) {
                int d2 = num2[j] - '0';
                result[i + j + 1] += d1 * d2;
                result[i + j] += result[i + j + 1] / 10;
                result[i + j + 1] %= 10;
            }
        }

        int i = 0;
        string ans = "";
        while (result[i] == 0) i++;
        while (i < result.size()) ans += to_string(result[i++]);
        return ans;
    }
};
class Solution {
public:
    string addBinary(string a, string b) {
        string result;
        int carry = 0, i = a.size()-1, j = b.size()-1;
        
        while (i >= 0 or j >= 0 or carry != 0) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            result.push_back((char)(carry % 2 + '0'));
            carry /= 2;
        }

        reverse(result.begin(), result.end());
        return result;        
    }
};
class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> result;
        int i = num.size() - 1, carry = 0;
        
        while (i >= 0 or k > 0 or carry > 0) {
            if (i >= 0) carry += num[i--];
            if (k){
                carry += k % 10;
                k /= 10;
            } 
            result.push_back(carry % 10);
            carry /= 10;
        }

        reverse(result.begin(), result.end());
        return result;
    }
};
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result (temperatures.size(), 0);
        stack<int> s;
        int n = temperatures.size();
        
        for (int day = 0; day < n; day++) {
            int temp = temperatures[day];
            while (!s.empty() and temp > temperatures[s.top()]) {
                int prev_day = s.top(); s.pop();
                result[prev_day] = day - prev_day;
            }
            s.push(day);
        }
        return result;
    }
};
class Solution {
public:
    int lengthOfLastWord(string s) {
        int last = 0, curr = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ' and curr) last = curr;
            if (s[i] == ' ') curr = 0;
            else curr++;
        }
        return curr > 0 ? curr : last;
    }
};
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i=0; i < (n - n / 2); i++) {
            for (int j=0; j < n / 2; j++) {
                vector<int> tmp = {
                    matrix[n - j - 1][i],
                    matrix[n - i - 1][n - j - 1],
                    matrix[j][n - i - 1],
                    matrix[i][j]
                };
                matrix[i][j] = tmp[0];
                matrix[n - j - 1][i] = tmp[1];
                matrix[n - i - 1][n - j - 1] = tmp[2];
                matrix[j][n - i - 1] = tmp[3];
            }
        }
    }
};
class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        vector<bool> c(4, true);
        int n = mat.size();
        
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                if (mat[i][j] != target[i][j]) c[0] = false;
                if (mat[i][j] != target[n-j-1][i]) c[1] = false;
                if (mat[i][j] != target[j][n-i-1]) c[2] = false;
                if (mat[i][j] != target[n-i-1][n-j-1]) c[3] = false;
            }
        }
        return c[0] or c[1] or c[2] or c[3];
    }
};
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int row_start = 0, col_start = 0, row_end = matrix.size() - 1, col_end = matrix[0].size() - 1;
        
        while (row_start <= row_end and col_start <= col_end) {
            for (int c=col_start; c<=col_end; c++) result.push_back(matrix[row_start][c]);
            row_start++;
            for (int r=row_start; r<=row_end; r++) result.push_back(matrix[r][col_end]);
            col_end--;
            
            if (row_start <= row_end) {
                for (int c=col_end; c>=col_start; c--) result.push_back(matrix[row_end][c]);
                row_end--;
            }
            
            if (col_start <= col_end) {
                for (int r=row_end; r>=row_start; r--) result.push_back(matrix[r][col_start]);
                col_start++;
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<vector<int>> pq;
        
        auto dist = [](auto x) { return x[0] * x[0] + x[1] * x[1]; };
        
        for (auto p: points) {
            int d = dist(p);
            pq.push({d, p[0], p[1]});
            if (pq.size() > k) pq.pop();
        }
        vector<vector<int>> result;
        while (!pq.empty()) {
            auto r = pq.top(); pq.pop();
            result.push_back({r[1], r[2]});    
        }
        return result;
    }
};
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> result;
        for (int i = 0; i < l.size(); i ++){
            unordered_set<int> window;
            for (int j = l[i]; j <= r[i]; j++) window.insert(nums[j]);
            
            int window_size = (r[i] - l[i] + 1);
            int min_val = *min_element(window.begin(), window.end());
            int max_val = *max_element(window.begin(), window.end());

            auto divmod = div(max_val - min_val, window_size - 1);
            
            if (divmod.rem != 0) {
                result.push_back(false);
            } else {
                bool is_arithmetic_subarr = true;
                for (int k = 0; k < window_size; k++) {
                    if (not window.count(min_val + k * divmod.quot)) {
                        is_arithmetic_subarr = false;
                    }
                }
                result.push_back(is_arithmetic_subarr);
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> q;
        if (root == nullptr) return result;
        q.push(root);
        
        while (!q.empty()) {
            vector<int> level_vals;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto node = q.front(); q.pop();
                level_vals.push_back(node->val);
                for (auto child: node->children) q.push(child);
            }
            result.push_back(level_vals);
        }
        return result;
    }
};
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> next_greater(nums.size(), -1);
        stack<int> s;
        
        for (int i=0; i<nums.size() * 2; i++) {
            int j = i % nums.size();
            int num = nums[j];
            while (!s.empty() and nums[s.top()] < num) {
                next_greater[s.top()] = num;
                s.pop();
            }
            s.push(j);
        }
        return next_greater;
    }
};
class Solution {
public:
    int nextGreaterElement(int n) {
        string digits = to_string(n);

        int i = digits.size() - 1;        
        while (i > 0 and digits[i-1] >= digits[i]) i--;
        if (i == 0) return -1;
        
        int j = digits.size() - 1;
        while (j > 0 and digits[j] <= digits[i-1]) j--;
        
        swap(digits[j], digits[i-1]);
        reverse(digits.begin()+i, digits.end());
        
        size_t ans = stoll(digits);
        return ans > INT_MAX ? -1 : ans;        
        
    }
};
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        unordered_map<int, vector<int>> reports; 
        for (int e=0; e<manager.size(); e++) reports[manager[e]].push_back(e);
        
        stack<pair<int, int>> s;
        s.push({headID, 0});
        int max_time = INT_MIN;
        
        while (!s.empty()) {
            auto node = s.top(); s.pop();
            int e_id = node.first, t = node.second;
            max_time = max(max_time, t);
            for (auto report: reports[e_id]) s.push({report, t + informTime[e_id]});
        }
        return max_time;        
    }
};
class Solution {
public:
    string hash(string str) {
        stringstream freq_str;
        vector<int> freq_table(26);
        for (auto chr: str) freq_table[chr - 'a'] += 1;
        copy(freq_table.begin(), freq_table.end(), ostream_iterator<int>(freq_str, ","));
        return freq_str.str().c_str();
    }
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> group_by;
        vector<vector<string>> anagrams;
        for (auto str: strs) group_by[hash(str)].push_back(str);
        for (auto group: group_by) anagrams.push_back(group.second);
        return anagrams;
    }
};
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.size() < p.size()) return {};
        unordered_map<char, int> req_freq, window;
        for (char c:p) req_freq[c]++;
        for (int i=0;i<p.size();i++) if (req_freq.count(s[i])) window[s[i]]++;
        int to_match = req_freq.size();
        for (auto kv:window) to_match -= kv.second == req_freq[kv.first];
        if (not to_match) result.push_back(0);
        for (int r=p.size(),l=0;r<s.size();r++,l++){
            char in_char=s[r], out_char=s[l];
            if (req_freq.count(in_char)) {
                if (window[in_char] == req_freq[in_char]) to_match++;
                if (window[in_char]+1==req_freq[in_char]) to_match--;
                window[in_char]++;
            }
            if (req_freq.count(out_char)){
                if (window[out_char] == req_freq[out_char]) to_match++;
                if (window[out_char]-1==req_freq[out_char]) to_match--;
                window[out_char]--;
            }
            if (not to_match) result.push_back(l+1);
        }
        return result;
    }
};
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int accum=1, count=0, l=0;
        for (int r=0; r<nums.size(); r++) {
            int num = nums[r];
            accum *= num;
            while (l <= r and accum >= k) {
                accum /= nums[l];
                l++;
            }
            if (accum < k) count += r - l + 1;
        }
        return count;
    }
};
class NumMatrix {
private:
    vector<vector<int>> dp;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int nrow = matrix.size(), ncol = matrix[0].size();
        dp.resize(nrow + 1, vector<int>(ncol+1));
        for (int r = 1; r < nrow + 1; r++) {
            for (int c = 1; c < ncol + 1; c++) {
                dp[r][c] = dp[r][c-1] + dp[r-1][c] - dp[r-1][c-1] + matrix[r-1][c-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
    }
};
class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int min_range = nums[n-1] - nums[0];
        for (int i = 0; i < n-1; i ++) {        
            int large = max(nums[n-1], nums[i] + 2 * k);
            int small = min(nums[i+1], nums[0] + 2 * k);
            min_range = min(min_range, large - small);
        }
        return min_range;
    }
};
class Solution {
private:
    ListNode* get_middle(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr and fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* reverse(ListNode* head) {
        ListNode *prev = nullptr, *curr = head, *temp = nullptr;
        while (curr != nullptr) {
            temp = curr->next, curr->next = prev, prev = curr, curr = temp;
        }
        return prev;
    }
    
    void merge(ListNode* l1, ListNode* l2) {
        ListNode *curr = new ListNode();
        while (l1 != nullptr and l2 != nullptr) {
            curr->next = l1, curr = l1, l1 = l1->next;
            curr->next = l2, curr = l2, l2 = l2->next;
        }
        if (l1 != nullptr) curr->next = l1;
    }
public:
    void reorderList(ListNode* head) {
        ListNode *l1_tail = get_middle(head);
        ListNode *l2_head = l1_tail->next;
        l1_tail->next = nullptr;
        l2_head = reverse(l2_head);
        merge(head, l2_head);
    }
};
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (not head) return head;
        Node *curr=head, *copy, *new_head;
        while (curr) {
            copy = new Node(curr->val);
            copy->next = curr->next;
            curr->next = copy;
            curr = copy->next;
        }
        
        curr = head;
        while (curr) {
            if (curr->random) curr->next->random = curr->random->next;
            curr = curr->next->next;
        }
        
        curr = head;
        copy = head->next;
        new_head = head->next;
        while (curr) {
            curr->next = curr->next->next;
            copy->next = copy->next ? copy->next->next : nullptr;
            curr = curr->next;
            copy = copy->next;
        }
        return new_head;
    }
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode();
        ListNode* curr = ret;
        int carry = 0;
        while (l1 or l2 or carry) {
            if (l1) {
                carry += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                carry += l2->val;
                l2 = l2->next;
            }
            curr->next = new ListNode(carry%10);
            curr = curr-> next;
            carry = carry / 10;
        }
        return ret->next;
    }
};
class Solution {
private:
    ListNode* reverse(ListNode* head) {
        ListNode *prev = nullptr, *curr = head, *temp = nullptr;
        while (curr != nullptr) {
            temp = curr->next, curr->next = prev, prev = curr, curr = temp;
        }
        return prev;
    }
    
    ListNode* add(ListNode* l1, ListNode* l2) {
        int carry = 0, val = 0;
        ListNode *sentinel = new ListNode();
        ListNode *curr = new ListNode();
        sentinel->next = curr;
        while (l1 != nullptr or l2 != nullptr or carry != 0) {
            if (l1 != nullptr) {
                carry += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                carry += l2->val;
                l2 = l2->next;
            }
            val = carry % 10;
            carry /= 10;
            curr->next = new ListNode(val);
            curr = curr->next;
        }
        return sentinel->next->next;
    }

public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode *l3 = add(l1, l2);
        l3 = reverse(l3);
        return l3;
    }
};
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (not head or not head->next) return head;
        ListNode *curr = head, *tail, *prev;
        
        int n = 1;
        while (curr->next) {
            curr = curr->next;
            n++;
        }
        tail = curr;
        tail->next = head;
        
        // find split point
        curr = head;        
        k %= n;
        while (k < n) {
            prev = curr;
            curr = curr->next;
            k++;
        }
        
        // split
        prev->next = nullptr;
        return curr;
    }
};
class BSTIterator {
private:
    TreeNode* root_node;
    stack<pair<TreeNode*, int>> s;
public:
    BSTIterator(TreeNode* root) {
        root_node = root;
        s = {};
        s.push({root_node, 0});
    }
    
    int next() {
        while (!s.empty()) {
            auto e = s.top(); s.pop();
            TreeNode* node = e.first;
            int is_backtrack = e.second;
            if (is_backtrack) return node->val;
            if (node->right != nullptr) s.push({node->right, 0});
            if (node != nullptr) s.push({node, 1});
            if (node->left != nullptr) s.push({node->left, 0});
        }
        return 0;
    }
    
    bool hasNext() {
        return (!s.empty());
    }
};
class SeatManager {
private:
    set<int> set;

public:
    SeatManager(int n) {
        for (int i = 1; i <= n; ++i) set.insert(set.end(), i);
    }
    
    int reserve() {
        int val = *set.begin();
        set.erase(set.begin());
        return val;
        
    }
    
    void unreserve(int seatNumber) {
        set.insert(seatNumber);
    }
};
class Bank {
private:
    vector<int> vals = {20, 10, 5};
    unordered_map<int, int> changes;
public:
    Bank() { for (int val: vals) changes[val] = 0; }
    
    bool change(int bill) {
        changes[bill]++;
        bill -= 5;
        for (int val: vals) {
            while (bill >= val and changes[val] > 0) {
                bill -= val;
                changes[val]--;
            }
        }
        return bill == 0;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        Bank* bank = new Bank();
        for (int bill: bills) {
            if (not bank->change(bill)) return false;
        }
        return true;
    }
};
class MinStack {
private:
    stack<int> vals;
    stack<tuple<int, int>> mins;
public:
    MinStack() {
        vals = {};
        mins = {};
    }
    
    void push(int x) {
        vals.push(x);
        if (mins.empty() or x < getMin()) mins.push({x, 1});
        else if (x == getMin()) get<1>(mins.top())++;
    }
    
    void pop() {
        if (vals.top() == getMin()) {
            if (get<1>(mins.top()) == 1) mins.pop();
            else get<1>(mins.top())--;
        }
        vals.pop();
    }
    
    int top() { return vals.top(); }
    
    int getMin() { return get<0>(mins.top()); }
};
class NestedIterator {
private:
    stack<NestedInteger*> stack;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) 
            stack.push(&nestedList[i]);
    }
    int next() {
        int nxt = stack.top()->getInteger();
        stack.pop();
        return nxt;
    }
    bool hasNext() {
        while (!stack.empty()) {
            NestedInteger *p = stack.top();
            if (p->isInteger()) return true;
            vector<NestedInteger> &vec = p->getList();
            stack.pop();
            for (int i = vec.size() - 1; i >= 0; i--) 
                stack.push(&vec[i]);
        }
        return false;
    }
};
class AuthenticationManager {
    int ttl;
    unordered_map<string, int> tokens;
public:
    AuthenticationManager(int timeToLive) { ttl = timeToLive; }
    
    void generate(string tokenId, int currentTime) {
        tokens[tokenId] = currentTime + ttl;
    }
    
    void renew(string tokenId, int currentTime) {
        auto tokenIt = tokens.find(tokenId);
        if (tokenIt != end(tokens) && tokenIt->second > currentTime) {
            tokenIt->second = currentTime + ttl;
        }
    }
    
    int countUnexpiredTokens(int currentTime) {
        int res = 0;
        for (auto token: tokens) {
            if (token.second > currentTime) res++;
        }
        return res;
    }
};
struct MyListNode {
    int val;
    MyListNode *next;
    MyListNode(int x) : val(x), next(NULL) {}
};

class MyLinkedList {
private:
    MyListNode* head;
public:
    MyLinkedList() { head=nullptr;}
    
    MyListNode* getNode(int index) {
        MyListNode* trav = head;
        for (int i=0;i<index and trav;i++) trav=trav->next;
        return index >= 0 ? trav : nullptr;
    }
    
    MyListNode* getTail() {
        MyListNode* trav = head;
        MyListNode* tail = nullptr;
        while (trav) {
            if (not trav->next) tail=trav;
            trav = trav->next;
        }
        return tail;
    }
    
    int get(int index) {
        auto node = getNode(index);
        return node ? node->val : -1;
    }
    
    void addAtHead(int val) {
        MyListNode *node = new MyListNode(val);
        node->next = head;
        head = node;
    }
    
    void addAtTail(int val) {
        if (not head) { addAtHead(val); return; }
        MyListNode *tail = getTail();
        MyListNode *node = new MyListNode(val);
        tail->next = node;
    }
    
    void addAtIndex(int index, int val) {
        if (index == 0) { addAtHead(val); return; }
        MyListNode *prev = getNode(index - 1);
        if (not prev) { return; }
        MyListNode *node = new MyListNode(val);
        MyListNode *next = prev->next;
        node->next = next;
        prev->next = node;
    }

    void deleteAtIndex(int index) {
        MyListNode *node = getNode(index);
        if (not node) { return; }
        
        MyListNode *prev = getNode(index-1);
        if (prev) prev->next = node->next; 
        else head = node->next;
    }
};
class RandomizedSet {
private:
    unordered_map<int, int> lookup;
    vector<int> values;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        lookup = {};
        values = {};
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (lookup.count(val)) return false;
        lookup[val] = values.size();
        values.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (not lookup.count(val)) return false;
        int last_elem = values.back();
        lookup[values.back()] = lookup[val];
        swap(values[lookup[val]], values[values.size()-1]);
        values.pop_back();
        lookup.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return values[rand() % values.size()];
    }
};
class MyCircularQueue {
private:
    int capacity, first, n;
    vector<int> queue;
public:
    MyCircularQueue(int k) {
        capacity = k;
        queue.resize(k, 0);
        first = 0; 
        n = 0;
    }
    
    bool enQueue(int value) {
        if (n == capacity) return false;
        queue[(first + n) % capacity] = value;
        n++;
        return true;
    }
    
    bool deQueue() {
        if (n == 0) return false;
        first = (first + 1) % capacity;
        n--;
        return true;
    }
    
    int Front() {
        if (n == 0) return -1;
        return queue[first];
    }
    
    int Rear() {
        if (n == 0) return -1;
        return queue[(first + n - 1) % capacity];
    }
    
    bool isEmpty() {
        return n == 0;
    }
    
    bool isFull() {
        return n == capacity;
    }
};
class MyCalendar {
public:
    MyCalendar() {}
    
    bool book(int start, int end) {        
        auto it = booked_.lower_bound(start);
        if (it != booked_.cend() && it->first < end)
            return false;        
        if (it != booked_.cbegin() && (--it)->second > start)
            return false;        
        booked_[start] = end;
        return true;
    }
private:
    map<int, int> booked_;
};

Leetcode Programming Skills study plan list III

  1. Day 1
  2. Day 2
  3. Day 3
  4. Day 4
  5. Day 5
  6. Day 6
  7. Day 7
  8. Day 8
  9. Day 9
  10. Day 10
  11. Day 11
  12. Day 12
  13. Day 13
  14. Day 14
  15. Day 20
  16. Day 21
  17. Day 22
class Solution {
public:
    PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
        PolyNode *sentinel = new PolyNode();
        PolyNode *curr = sentinel;
        
        while (poly1 != nullptr and poly2 != nullptr) {
            if (poly1->power > poly2->power) {
                curr->next = new PolyNode(poly1->coefficient, poly1->power);
                curr = curr->next;
                poly1 = poly1->next;
            } else if (poly2->power > poly1->power) {
                curr->next = new PolyNode(poly2->coefficient, poly2->power);
                curr = curr->next;
                poly2 = poly2->next;            
            } else {
                int coef = poly1->coefficient + poly2->coefficient;
                if (coef != 0) {
                    curr->next = new PolyNode(coef, poly1->power);
                    curr = curr->next;
                }
                poly1 = poly1->next;
                poly2 = poly2->next;
            }
        // curr->next = nullptr;
        }
        if (poly1 != nullptr) curr->next = poly1;
        if (poly2 != nullptr) curr->next = poly2;
        return sentinel->next;
    }
};
class Solution {
    ListNode* reverseList(ListNode* head) {
        ListNode *prev=nullptr, *trav=head, *next;
        while (trav) {
            next = trav->next;
            trav->next = prev;
            prev = trav;
            trav = next;
        }
        return prev;
    }    
public:
    ListNode* plusOne(ListNode* head) {
        head = reverseList(head);
        ListNode *trav=head;
        int carry = 0;
        trav->val++; // change to other values if problem changes
        while (trav) {
            carry += trav->val;
            trav->val = carry % 10;
            carry /= 10;
            if (not trav->next and carry) trav->next = new ListNode(0);
            trav = trav->next;
        }
        return reverseList(head);
    }
};
class Solution {
public:
    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
        ListNode *sentinel = new ListNode(), *curr = head;
        sentinel->next = head;
        
        unordered_map<int, int> freq_count;
        while (curr) {
            if (!freq_count.count(curr->val)) freq_count[curr->val] = 0;
            freq_count[curr->val]++;
            curr = curr->next;
        }
        
        ListNode *prev = sentinel; 
        curr = head;
        while (curr) {
            while (curr and freq_count[curr->val] > 1) curr = curr->next;
            prev->next = curr;
            prev = curr;
            if (curr) curr = curr->next;
        }
        return sentinel->next;
    }
};
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        Node *curr = root, *head = nullptr, *prev = nullptr;
        stack<Node*> stack;
        while (curr or stack.size()) {
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top(); stack.pop();
            
            if (!prev) head = curr;
            else  prev->right = curr, curr->left = prev;   
            
            prev = curr, curr = curr->right;
        }
        prev->right = head, head->left = prev;
        
        return head;
    }
};
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int max_len = 0, accum = 0;
        unordered_map<int, int> prefix_sum = 0;
        for (int r=0; r < nums.size(); ++r) {
            accum += nums[r];
            if (prefix_sum.count(accum - k)) 
                max_len = max(max_len, r - prefix_sum[accum - k]);
            if (!prefix_sum.count(accum))
                prefix_sum[accum] = r;
        }
        return max_len;
    }
};
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l = 0, window_sum = 0, min_size = INT_MAX;
        for (int r=0; r < nums.size(); ++r) {
            window_sum += nums[r];
            while (l <= r and window_sum >= target) {
                min_size = min(min_size, r - l + 1);
                window_sum -= nums[l++];
            }
        }
        return min_size != INT_MAX ? min_size : 0;
    }
};
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> m = 0;
        int r=0, max_length=0;
        for (int i=0; i<nums.size(); i++){
            r += (nums[i]) ? 1 : -1;
            if (m.count(r)) max_length = max(max_length, i-m[r]);
            else m[r] = i;
        }
        return max_length;
    }
};
class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int accum = 1;
        for (int coin: coins) {
            if (coin > accum) break;
            accum += coin;
        }
        return accum;
    }        
};
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> stack;
        int lower = INT_MIN;
        for (auto x: preorder) {
            if (x < lower) return false;
            
            while (!stack.empty() and stack.top() < x) {
                lower = stack.top(); stack.pop();
            }
            stack.push(x);
        }
        return true;
    }
};
class Solution {
private:
    int operation(char op, int first, int second) {
        if (op == '+') return first + second;
        if (op == '-') return first - second;
        return 0;
    }
    
public:
    int calculate(string s) {
        stack<pair<char, int>> stack;
        char op = '+';
        int partial = 0, operand = 0;
        
        for (char c: s) {
            if (isdigit(c)) {
                operand = operand * 10 + (c - '0');
            } else if (c == '+' or c == '-') {
                partial = operation(op, partial, operand);
                op = c;
                operand = 0;
            } else if (c == ')') {
                operand = operation(op, partial, operand);
                auto item = stack.top(); stack.pop();
                op = item.first;
                partial = item.second;
                partial = operation(op, partial, operand);
                operand = 0;
            } else if (c == '(') {
                stack.push({op, partial});
                op = '+';
                partial = 0;
            }
        }
        return operation(op, partial, operand);
    }
};
class StockSpanner {
private:
    vector<pair<int, int>> spanner;
public:
    StockSpanner() {
        spanner = {};
    }
    
    int next(int price) {
        int span = 1;
        while (not spanner.empty() and spanner.back().first <= price) {
            span += spanner.back().second;
            spanner.pop_back();
        }
        spanner.push_back({price, span});
        return span;
    }
};
class Solution {
private:
    unordered_map<string, vector<int>> memo;
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> result, nums;
        vector<char> ops;
        
        auto to_key = [](char a, char b) {
            string s;
            return s + a + '-' + b;
        };
        
        auto eval = [](int a, int b, char op) {
            if (op == '+') return a + b;
            if (op == '*') return a * b;
            if (op == '-') return a - b;
            return 0;
        };
        
        int num = 0;
        for (char c: expression) {
            if (isdigit(c)) {
                num = 10 * num + (c - '0');
            } else {
                ops.push_back(c);
                nums.push_back(num);
                num = 0;
            }
        }
        nums.push_back(num);                        
       
        function<vector<int>(int, int)> dfs = [&](int l, int r) {
            string key = to_key(l, r);
            
            if (memo.count(key)) return memo[key];

            if (l == r) {
                memo[key] = vector<int> {nums[l]};
            } else {
                vector<int> res = {};
                for (int k = l; k < r; ++k) {
                    vector<int> ls = dfs(l, k), rs = dfs(k+1, r);
                    for (auto l_val: ls) {
                        for (auto r_val: rs) {
                            res.push_back(eval(l_val, r_val, ops[k]));
                        }
                    }
                }
                memo[key] = res;
            }
            return memo[key];
        };
        return dfs(0, nums.size() - 1);
    }
};
class Codec {
private:
    int encode_flag(TreeNode* node) {
        int flag = 0;
        if (node) {
            flag |= 1;
            if (node->left) flag |= 2;
            if (node->right) flag |= 4;
        }
        return flag;
    }

    void serialize(TreeNode* node, string& s) {
        char flag = encode_flag(node);
        s.push_back(flag);
        if (!node) return;
        s.append(reinterpret_cast<char*>(&node->val), sizeof(node->val));
        if (node->left) serialize(node->left, s);
        if (node->right) serialize(node->right, s);
    }

    TreeNode* deserialize(const string& s, int& pos) {
        char flag = s[pos++];
        if (!flag) return nullptr;
        TreeNode* root = new TreeNode(0);
        memcpy(&root->val, s.data() + pos, sizeof(root->val));
        pos += sizeof(root->val);
        root->left = (flag & 2) ? deserialize(s, pos) : nullptr;
        root->right = (flag & 4) ? deserialize(s, pos) : nullptr;
        return root;
    }
    
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        serialize(root, s);
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int pos = 0;
        return deserialize(data, pos);
    }
};
class Solution {
public:
    int myAtoi(string s) {
        long res = 0;
        int sign = 1, i = 0, n = s.size();
        
        while (i < n && s[i] == ' ') ++i;
        
        if (i < n && ( s[i] == '-' || s[i] == '+')) {
            if (s[i] == '-') sign = -1;
            ++i;
        }
        
        while (i < n && isdigit(s[i])) {
            if (res > INT_MAX / 10 || 
                (res == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)
               ) 
                return (sign == 1) ? INT_MAX : INT_MIN;
            res = res * 10 + s[i] - '0';
            ++i;
        }
        res *= sign;
        return res;
    }
};
class Solution {
private:
    int count_nodes(ListNode* head) {
        int total = 0;
        while (head) {
            head = head->next;
            total++;
        }
        return total;
    }
    
    ListNode* split(ListNode* node, int length) {
        while (length > 1 and node) {
            length--;
            node = node->next;
        }
        if (!node) return nullptr;
        ListNode* temp = node->next;
        node->next = nullptr;
        return temp;
    }
    
    ListNode* merge(ListNode* l, ListNode* r, ListNode* node) {
        while (l and r) {
            if (l->val < r->val) {
                node->next = l;
                l = l->next;
            } else {
                node->next = r;
                r = r->next;
            }
            node = node->next;
        }
        node->next = l != nullptr ? l : r;
        while (node->next) node = node->next;
        return node;
    }
    
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) return nullptr;
        
        int size = count_nodes(head);
        ListNode* sentinel = new ListNode(0, head);
        ListNode *l, *r, *node, *tail;
        int length = 1;
        while (length < size) {
            node = sentinel->next; 
            tail = sentinel;
            while (node) {
                l = node; 
                r = split(node, length);
                node = split(r, length);
                tail = merge(l, r, tail);
            }
            length <<=1;
        }
        return sentinel->next;
    }
};
class Solution {
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode ret(0);
        ListNode* trav = &ret;
        while (l1 and l2){
            if (l1->val < l2->val) {
                trav->next = l1;
                l1 = l1->next;
            } else {
                trav->next = l2;
                l2 = l2->next;                
            }
            trav = trav->next;
        }
        trav->next = l1 ? l1 : l2;
        return ret.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        queue<ListNode*> q;
        for (auto node:lists) q.push(node);
        while (q.size() > 1) {
            ListNode* l1 = q.front(); q.pop();
            ListNode* l2 = q.front(); q.pop();
            ListNode* l3 = mergeTwoLists(l1, l2);
            q.push(l3);
        }
        return q.empty() ? nullptr: q.front();
    }
};
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (not head) {
            Node *node = new Node(insertVal);
            node->next = node;
            return node;
        }

        Node *prev=head, *trav=head->next;
        while (trav != head) {
            if (prev->val <= insertVal and insertVal <= trav->val) break;
            if (prev->val > trav->val and insertVal >= prev->val) break;
            if (prev->val > trav->val and insertVal <= trav->val) break;
            prev = trav;
            trav = trav->next;
        }
        prev->next = new Node(insertVal, trav);
        return head;
    }
};
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> result;
        function<void(string, int, long, long)> dfs = [&](string candidate, int i, long total, long prev) {
            if (i == num.size() and total == target) {
                result.push_back(candidate);
                return;
            }
            for (int l = 1; i + l <= num.size(); l++) {
                string s = num.substr(i, l);
                long d = stoll(s);
                int j = i + l;
                if (num[i] == '0' and s != "0") continue;
                if (candidate.size() == 0) {
                    dfs(s, j, d, d);
                } else {
                    dfs(candidate + '+' + s, j, total + d,  d);
                    dfs(candidate + '-' + s, j, total - d, -d);
                    dfs(candidate + '*' + s, j, total - prev + prev * d, prev * d);
                }
            }
        };
        dfs("", 0, 0, 0);
        return result;
    }
};
class Solution {
public:
    int calculate(string s) {
        unordered_set<char> ops = {'+', '-', '*', '/'};
        char opr = '+';
        int opd = 0;
        stack<int> stack;
        
        auto operation = [&]() {
            if (opr == '+') stack.push(opd);
            if (opr == '-') stack.push(-opd);
            if (opr == '*') {
                int prev = stack.top(); stack.pop();
                stack.push(prev * opd);
            }
            if (opr == '/') {
                int prev = stack.top(); stack.pop();
                stack.push(prev / opd);
            }
        };
        
        for (char c: s) {
            if (isdigit(c)) opd = opd * 10 + (c - '0');
            if (ops.count(c)) {
                operation();
                opd = 0;
                opr = c;
            }
        }
        operation();
        int total = 0;
        while (!stack.empty()) {
            total += stack.top();
            stack.pop();
        }
        return total;
    }
};
class Solution {
public:
    int calculate(string s) {
        if (s.size() == 0) return 0;

        stack<int> stack;
        char sign = '+'; // sign only indicaite next element attribute
        long number = 0;
        
        for (int i = 0; i< s.size(); i++) {
		    // Step 1. calculate the current number you meet. have a recursive call the func encounter a parenthese
            if (isdigit(s[i])) {
                number = number*10 + long(s[i]-'0');
            } else if (s[i] == '(') {
                int j = i + 1; 
                int braces = 1;
                while (braces > 0) {
                    if (s[j] == '(')
                        braces++;
                    else if (s[j] ==')')
                        braces--;
                    j++;
                }
                
                int length = (j-1) -i ;
                number = calculate(s.substr(i + 1, length));
                i = j-1; // adjust cursor to the last calculated character
            }
            
			// Step 2.  push the current number inside your stack based on the **last sign** you meet
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size() - 1) {
                switch (sign) {
                    case '+':
                        stack.push(number);
                        break;
                    case '-':
                        stack.push(-number);
                        break;
                    case '*': {
                        int top = stack.top();
                        stack.pop();
                        stack.push(top*number);
                        break;                        
                    }
                    case '/': {
                        int top = stack.top();
                        stack.pop();
                        stack.push(top/number);
                        break;                        
                    }
                }

                sign = s[i]; // assign new operator 
                number = 0; // reset the current number 
            }
        }
        
		// Step 3.  sum up all the numbers you have meet by poping elements from the stack
        int sum = 0;
        while(!stack.empty()) {
            sum += stack.top();
            stack.pop();
        }
        return sum;
    }
};
class MyCircularDeque {
private:
    int K, n, first, last;
    int* deque;
    
public:
    MyCircularDeque(int k) {
        K=k, n=0, first=0, last=K-1;
        deque = new int[K]{0};
    }
    
    bool insertFront(int value) {
        if (isFull()) return false;
        first = (first + K - 1) % K;
        deque[first] = value;
        n++;
        return true;
    }
    
    bool insertLast(int value) {
        if (isFull()) return false;
        last = (last + 1) % K;
        deque[last] = value;
        n++;
        return true;
    }
    
    bool deleteFront() {
        if (isEmpty()) return false;
        deque[first] = 0;
        first = (first + 1) % K;
        n--;
        return true;
    }
    
    bool deleteLast() {
        if (isEmpty()) return false;
        deque[last] = 0;
        last = (last + K - 1) % K;
        n--;
        return true;
    }
    
    int getFront() { return isEmpty() ? -1 : deque[first]; }
    
    int getRear() { return isEmpty() ? -1 : deque[last]; }
    
    bool isEmpty() { return n == 0; }
    
    bool isFull() { return n == K; }
};
class ProductOfNumbers {
private:
    vector<int> prefix_prods;
public:
    ProductOfNumbers() { prefix_prods = {1}; }
    
    void add(int num) {
        if (num == 0) prefix_prods = {1};
        else prefix_prods.push_back(prefix_prods.back() * num);
    }
    
    int getProduct(int k) { 
        if (k >= prefix_prods.size()) return 0; 
        return prefix_prods.back() / prefix_prods[prefix_prods.size() - k - 1]; 
    }
};
class Solution {
private:
    vector<int> kmp_table(string s) {
        int m = s.size();
        vector<int> table = {0, 0};
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 and s[i] != s[j]) j = table[j];
            if (s[i] == s[j]) j++;
            table.push_back(j);
        }
        return table;
    }    
public:
    string shortestPalindrome(string s) {
        string ss = s + "+" + string(s.rbegin(), s.rend());
        vector<int> table = kmp_table(ss);
        string first, second, third;
        
        first = s.substr(table.back());
        reverse(first.begin(), first.end());
        
        second = s.substr(0, table.back());
        
        third = s.substr(table.back());
        
        return first + second + third;
    }
};
class Solution {
public:
    Node* expTree(string s) {
       //M2: define a BNF
        //exp := s
        //s := term | term {[+, -] term}
        //term := factor | factor {[*, /] factor}
        //factor := digit | '(' exp ')'
        int pos = 0;
        return parseExp(s, pos);
    }

private:    
    Node* parseExp(string &s, int &pos) {
        Node *lhs = parseTerm(s, pos);
        while (pos < s.size() && (s[pos] == '+' || s[pos] == '-')) {
            char op = s[pos];
            ++pos;
            Node* rhs = parseTerm(s, pos);
            lhs = new Node(op, lhs, rhs);
        }
        return lhs;
    }
    
    Node* parseTerm(string &s, int &pos) {
        Node* lhs = parseFactor(s, pos);
        while (pos < s.size() && (s[pos] == '*' || s[pos] == '/')) {
            char op = s[pos];
            ++pos;
            Node* rhs = parseFactor(s, pos);
            lhs = new Node(op, lhs, rhs);
        }
        return lhs;
    }
    
    Node* parseFactor(string &s, int &pos) {
        if (s[pos] == '(') {
            ++pos; //consume '('
            Node* exp = parseExp(s, pos);
            ++pos; //consume ')'
            return exp;   
        }
        
        //is a digit
        Node* digit = new Node(s[pos]);
        ++pos;
        return digit;
    }
};
class Solution {
private:
    int delta[10][6] = {
        {0,1,2,3,9,9}, 
        {9,9,2,3,9,9},
        {8,9,2,4,5,9},
        {9,9,4,9,9,9},
        {8,9,4,9,5,9},
        {9,6,7,9,9,9},
        {9,9,7,9,9,9},
        {8,9,7,9,9,9},
        {8,9,9,9,9,9},
        {9,9,9,9,9,9}
    };

    int char_to_input(char c) {
        if (c == ' ') return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        if (c == '.') return 3;
        if (c == 'e' or c == 'E') return 4;
        return 5;
    }
public:
    bool isNumber(string s) {
        int state = 0;
        for (char c: s) {
            int input = char_to_input(c);
            state = delta[state][input];
            if (state == 9) return false;
        }
        state = delta[state][0];
        return state == 8;
    }
};
class TrieNode {
public:
    bool flag;
    unordered_map<char, TrieNode*> children;
    TrieNode() {
        flag=false; 
        children={};
    }
};

class Trie {
private:
    TrieNode* root;
    TrieNode* find(string term){
        TrieNode* node = root;
        for (char c:term){
            if (!node->children.count(c)) return nullptr;
            node = node->children[c];
        }
        return node;
    }
public:
    Trie() {root = new TrieNode();}
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c:word){
            if (!node->children.count(c)) node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->flag = true;
    }
    
    bool search(string word) {
        TrieNode* node = find(word);
        return node ? node->flag : false;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = find(prefix);
        return node ? true : false;
    }
};
class TrieNode {
public:
    int count;
    unordered_map<char, TrieNode*> children;
    TrieNode() {
        count = 0; 
        children = {};
    }
};
    
class Trie {
private:
    TrieNode* root;
    TrieNode* find(string term){
        TrieNode* node = root;
        for (char c:term){
            if (!node->children.count(c)) return nullptr;
            node = node->children[c];
        }
        return node;
    }    
public:
    Trie() {root = new TrieNode();}
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c:word){
            if (!node->children.count(c)) node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->count++;
    }
    
    int countWordsEqualTo(string word) {
        TrieNode* node = find(word);
        if (node and node->count > 0) return node->count;
        return 0;
    }
    
    int countWordsStartingWith(string prefix) {
        int total = 0;
        TrieNode* node = find(prefix);
        stack<TrieNode*> stack;
        stack.push(node);
        while (!stack.empty()) {
            node = stack.top(); stack.pop();
            if (node == nullptr) continue;
            if (node->count > 0) total += node->count;
            for (auto child: node->children) {
                stack.push(child.second);
            }
        }
        return total;
    }
    
    void erase(string word) {
        TrieNode* node = find(word);
        if (node) node->count--;
    }
};
class TrieNode {    
public:
    unordered_set<int> indices;
    unordered_map<char, TrieNode*> children;
    TrieNode() {
        indices.clear();
        children.clear();
    };
};

class AutocompleteSystem {
private:
    TrieNode *root, *curr, *node;
    string query;
    unordered_map<string, pair<int, int>> statistics;
    unordered_map<int, string> idx_to_sentence;
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        root = new TrieNode();
        init_query();
        statistics.clear();
        
        for (int i = 0; i < sentences.size(); i++) insert(sentences[i], times[i]);
    }
    
    void init_query() {
        query.clear();
        curr = root;        
    }
    
    void insert(string sentence, int time) {
        if (statistics.count(sentence)) statistics[sentence].first += time;
        else statistics[sentence] = {time, statistics.size()};
        
        int i = statistics[sentence].second;
        idx_to_sentence[i] = sentence;
        
        node = root;
        for (char c: sentence) {
            if (!node->children.count(c)) node->children[c] = new TrieNode();
            node = node->children[c];
            node->indices.insert(i);
        }
    }
    
    vector<string> auto_complete(char c, int k=3) {
        node = curr;
        vector<string> result = {};
        vector<pair<string, int>> matched = {};
        if (!node || !node->children.count(c)) {
            curr = nullptr;
            return result;
        }
        
        node = node->children[c];
        curr = node;
        
        for (auto i: node->indices) {
            string sentence = idx_to_sentence[i];
            int freq = statistics[sentence].first;
            matched.push_back({sentence, freq});
        }
        
        auto compare = [](pair<string, int> lhs, pair<string, int> rhs) -> bool {
            if (lhs.second > rhs.second) return true; 
            if (lhs.second == rhs.second) return lhs.first < rhs.first; 
            return false;
        };
        sort(matched.begin(), matched.end(), compare);
        for (int i = 0; i < k and i < matched.size(); i++) {
            if (matched[i].first != "") result.push_back(matched[i].first);
        }
        return result;
    }    
    
    vector<string> input(char c) {
        if (c == '#') {
            insert(query, 1);
            init_query();
            return {};
        }
        query += c;
        return auto_complete(c);
    }
};
class MedianFinder {
public:
    priority_queue<int> max_q;
    priority_queue<int, vector<int>, greater<int>> min_q; 

    MedianFinder() {}
    
    void addNum(int num) {
      if(min_q.empty() || num >= min_q.top()){
        min_q.push(num);
        if (min_q.size() > max_q.size() + 1) {
          max_q.push(min_q.top());
          min_q.pop();
        }
      } else {
        max_q.push(num);
        if (max_q.size() > min_q.size()) {
          min_q.push(max_q.top());
          max_q.pop();
        }
      }
    }
    
    double findMedian() {
      if ((max_q.size() + min_q.size()) % 2 == 0) return (min_q.top() + max_q.top()) / 2.;
    return min_q.top();
    }
};
class FreqStack {
public:
    unordered_map<int, int> freq;
    unordered_map<int, vector<int>> buckets;
    int max_freq = 0;
    
    FreqStack() {}
    
    void push(int val) {
        freq[val]++;
        max_freq = max(max_freq, freq[val]);
        buckets[freq[val]].push_back(val);
    }
    
    int pop() {
        int val = buckets[max_freq].back();
        buckets[max_freq].pop_back();
        if (buckets[max_freq].size() == 0) max_freq--;
        freq[val]--;
        return val;
    }
};
class LRUCache {
private:
    int _capacity;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
public:
    LRUCache(int capacity) { _capacity = capacity; }
    
    int get(int key) {
        if (not m.count(key)) return -1;
        l.splice(l.begin(), l, m[key]);
        return m[key]->second;
    }
    
    void put(int key, int value) {
        if (l.size() == _capacity and not m.count(key)) {
            m.erase(l.back().first);
            l.pop_back();            
        }
        if (m.count(key)) l.erase(m[key]);
        l.push_front({key, value});
        m[key] = l.begin();
    }
};
class Vector2D {
private:
    int li, el, n;
public:
    vector<vector<int>> v;
    
    Vector2D(vector<vector<int>>& vec) {
        for (auto vv: vec) {
            if (!vv.empty()) v.push_back(vv);
        }
        n = v.size();
        li = 0;
        el =  0;
    }
    
    int next() {
        int val;
        val = v[li][el];
        if (li < n - 1) {
            if (el < v[li].size() - 1) el++;
            else li++, el = 0;
        } else {
            if (el <= v[li].size() - 1) el++;
        }
        return val;
    }
    
    bool hasNext() {
        if (n == 0) return false;
        if (li < n - 1) return true;
        else if (el <= v[li].size() - 1) return true;
        return false;
    }
};
struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

class SnakeGame {
private:
    int _w, _h, _i;
    vector<vector<int>> _f;
    queue<pair<int, int>> body;
    unordered_set<pair<int, int>, pair_hash> lkp;
    bool gameover = false;
public:
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        _w = width, _h = height, _i = 0;
        _f = food;
        body.push({0, 0});
        lkp.insert({0, 0});
    }
    
    pair<int, int> next_loc(pair<int, int> loc, string d) {
        auto [r, c] = loc;
        if (d == "U") return {r-1, c};
        if (d == "D") return {r+1, c};
        if (d == "L") return {r, c-1};
        if (d == "R") return {r, c+1};
        return {0, 0};
    }
    
    int move(string direction) {
        auto [nr, nc] = next_loc(body.back(), direction);
        if (nr < 0 or nr == _h or nc < 0 or nc == _w) {
            gameover = true;
            return -1;
        }
        
        if (_i < _f.size() and nr == _f[_i][0] and nc == _f[_i][1]) {
            _i++;
        } else {
            auto old_tail = body.front(); body.pop();
            lkp.erase(old_tail);
        }
        
        if (lkp.count({nr, nc})) {
            gameover = true;
            return -1;
        } 
        
        lkp.insert({nr, nc});
        body.push({nr, nc});
        return body.size() - 1;
    }
};
class Fancy {
private:
    vector<array<int, 3>> num;    
public:
    Fancy() {}

    int r_mul = 1, r_inc = 0, mod = 1000000007;

    int modPow(int n, int p) {
        if (p == 1)
            return n;
        long p2 = modPow(n, p / 2);
        return (p2 * p2 % mod * (p % 2 ? n : 1)) % mod;
    }

    void append(int val) { num.push_back({val, r_mul, r_inc}); }

    void addAll(int inc) { r_inc += inc; }

    void multAll(int m) {
        r_mul = (long)r_mul * m % mod;
        r_inc = (long)r_inc * m % mod;
    }

    int getIndex(int idx) {
        if (idx >= num.size())
            return -1;
        auto &[val, mul, inc] = num[idx];
        auto ratio = (long)r_mul * modPow(mul, mod - 2) % mod;
        return (ratio * (mod + val - inc) + r_inc) % mod;
    }
};
class ExamRoom {
private:
    int _n;
    vector<int> seats;
public:
    ExamRoom(int n) {
        _n = n;
        seats.clear();
    }
    
    int seat() {
        int s = 0, dist, new_dist;
        if (!seats.empty()) {
            dist = seats[0];
            for (int l = 0, r = 1; r < seats.size(); ++l, ++r) {
                new_dist = (seats[r] - seats[l]) / 2;
                if (new_dist > dist) {
                    dist = new_dist;
                    s = seats[l] + new_dist;
                }
            }
            if (_n - 1 - seats.back() > dist) { s = _n - 1;}
        }
        seats.insert(upper_bound(seats.begin(), seats.end(), s), s);
        return s;
    }
    
    void leave(int p) {
        int i = 0;
        for (; i < seats.size(); ++i) {
            if (seats[i] == p) break;
        }
        seats.erase(seats.begin() + i);
    }
};
class Excel {
private:
    int n, m;
    vector <unordered_map<int, int>> edges;
    vector<int> grid;
public:
    Excel(int _height, char _width) { // O(N*M) time/cur_space init
        auto [height, width] = getCell(_height, _width);
        n = height + 1;
        m = width + 1;
        edges.resize(n * m);
        grid.resize(n * m, 0);
    }
    
    pair<int, int> getCell(int r, char c) { return {r - 1, c - 'A'};}

    void set(int row, char column, int val) { // O(N*M) clear
        auto [xx, yy] = getCell(row, column);
        int x = xx * m + yy; //id
        edges[x].clear();
        grid[x] = val;
    }
    int dfs(int x) { // O(N*M)
        int ret = grid[x];
        for (auto &[y, z] : edges[x]) // O(N*M)
            ret += dfs(y) * z;
        return ret;
    }
    int get(int row, char column) { // O(N^2*M^2)
        auto [x, y] = getCell(row, column);
        return dfs(x * m + y);
    }
    void add(int row, char column, string &s) { // O(N*M)
        auto [xx, yy] = getCell(row, column);
        int x = xx * m + yy; // id of the cell
        if (s.size() < 5) // streamline
            s = s + ":" + s;
        stringstream ss(s);
        int r1, r2;
        char c1, c2, q;
        ss >> c1 >> r1 >> q >> c2 >> r2;
        auto [i1, j1] = getCell(r1, c1);
        auto [i2, j2] = getCell(r2, c2);
        for (int i = i1; i <= i2; i++) {
            for (int j = j1; j <= j2; j++) {
                int y = i * m + j; // y is prereq to x
                edges[x][y]++; // 
            }
        }
    }
    int sum(int row, char column, vector<string> numbers) { // O(N^2*M^2)
        set(row, column, 0); // O(N*M) reset the cell
        for (auto &s : numbers) // 5
            add(row, column, s); // O(N*M)
        return get(row, column); // O(N^2*M^2)
    }
};