class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int> > ret;
        unordered_map<int, int> counter;
        for (int i = 0; i < nums.size(); i++) counter[nums[i]] += 1;
        unordered_map<int, int>::iterator iter = counter.begin(); 
        vector<int> current;
        this->getSet(counter, current, iter, ret);
        return ret;
    }
    
    void getSet(unordered_map<int, int>& counter, vector<int>& current, \
        unordered_map<int, int>::iterator iter, vector<vector<int>>& ret) {
        ret.push_back(current);
        if (iter == counter.end()) return;
        for (auto it = iter; it != counter.end(); it++) {
            int count = it->second;
            for (int i = 0; i < count; i++) {
                current.push_back(it->first);
                auto nextIter = next(it, 1);
                this->getSet(counter, current, nextIter, ret);
            }
            for (int i = 0; i < count; i++) current.pop_back();
        }
        return;
    }
};

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> X, Y;
        for (int indexA = 0; indexA < A.size(); indexA++) {
            for (int indexB = 0; indexB < B.size(); indexB++) {
                X[A[indexA] + B[indexB]] += 1;
            }
        }
        for (int indexC = 0; indexC < C.size(); indexC++) {
            for (int indexD = 0; indexD < D.size(); indexD++) {
                Y[C[indexC] + D[indexD]] += 1;
            }
        }
        
        int ret = 0;
        for (auto iter = X.begin(); iter != X.end(); iter++) {
            auto iterD = Y.find(-iter->first);
            if (iterD != Y.end()) 
                ret += iter->second * iterD->second;
        }
        
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Node {
public:
    bool l;
    bool r;
    TreeNode* treeNode; 
    Node(TreeNode* node) {
        this->treeNode = node;
        this->l = false;
        this->r = false;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<Node*> s;
        Node* start = new Node(root);
        if (root == NULL) return ret;
        s.push(start);
        while (s.empty() == false) {
            Node* currentNode = s.top();
            if (currentNode->l == false && currentNode->treeNode->left != NULL) {
                currentNode->l = true;
                TreeNode* traverse = currentNode->treeNode->left;
                while(traverse != NULL) {
                    Node* newNode = new Node(traverse);
                    newNode->l = true;
                    s.push(newNode);
                    traverse = traverse->left;
                }
                continue;
            }
            if (currentNode->r == true || currentNode->treeNode->right == NULL) {
                s.pop();
                ret.push_back(currentNode->treeNode->val);
                continue;
            }
            //Default case, find the node in the right subtree.
            currentNode->r = true;
            s.push(new Node(currentNode->treeNode->right));
        }
        return ret;
    }
};

class RandomizedSet {
public:
    
    /** Initialize your data structure here. */
    RandomizedSet() {
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(this->hash.find(val) != this->hash.end()) return false;
        this->hash[val] = this->nums.size();
        this->nums.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        auto iter = this->hash.find(val);
        if(iter == this->hash.end()) return false;
        int originIndex = iter->second;
        this->swap(nums, originIndex, this->nums.size() - 1);
        this->hash[this->nums[originIndex]] = originIndex;
        this->nums.pop_back();
        this->hash.erase(val);
        return true;
    }
    
    void swap(vector<int>& nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if (this->nums.size() == 0) return -1;
        return this->nums[rand() % (this->nums.size())];
    }
    
private:
    unordered_map<int, int> hash;
    vector<int> nums;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        
        if (nums.size() < 3) return false;
        int lower = INT_MAX; 
        int mid = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            int item = nums[i];
            if (item < lower) {
                lower = item;
                continue;
            }
            if (item < mid && item > lower) {
                mid = item;
                continue;
            }
            if (item > mid) return true;
        }
        
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        return this->build(preorder, inorder, 0, inorder.size() - 1, 0, preorder.size() - 1);
    }
    
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int inLeft, int inRight, int preLeft, int preRight) {
        if (inLeft > inRight || preLeft > preRight) return NULL;
        TreeNode* root = new TreeNode(preorder[preLeft]);
        int preIndex = preLeft;
        int inIndex = inLeft;
        while (inIndex <= inRight) {
            if (inorder[inIndex] == preorder[preLeft]) {
                break;
            }
            preIndex += 1;
            inIndex += 1;
        }
        root->left = this->build(preorder, inorder, inLeft, inIndex - 1, preLeft + 1, preIndex);
        root->right = this->build(preorder, inorder, inIndex + 1, inRight, preIndex + 1, preRight);
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        
        return check(left, right);
    }
    
    bool check(TreeNode* l, TreeNode* r) {
        if (l == NULL && r == NULL) return true;
        if (l == NULL || r == NULL) return false;
        if (l->val != r->val) return false;
        
        return this->check(l->left, r->right) && this->check(l->right, r->left);
    }
};

class Solution {
public:
    int calculate(string s) {
        int index = 0;
        return this->calculateFrom(index, s);
    }
    
    int calculateFrom(int& index, string& s) {
        int ret = 0;
        int sign = 1;
        while(index < s.size()) {
            while(s[index] == ' ') index += 1;
            switch (s[index]) {
                case '-':
                    index += 1;
                    sign = -1;
                    break;
                case '(': 
                    index += 1;
                    ret += sign * this->calculateFrom(index, s);
                    continue;
                case ')':
                    index += 1;
                    return ret;
                case '+':
                    index += 1;
                    sign = 1;
                    continue;
                default:
                //Number
                ret += sign * this->extractNumber(s, index);
            }
        }
        return ret;
    }
    
    int extractNumber(string& s, int& index) {
        int ret = 0;
        while (index < s.size() && s[index] <= '9' && s[index] >= '0') {
            ret = ret * 10 + (s[index] - '0');
            index += 1;
        }
        return ret;
    }
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.size() == 0) return 0;
        
        stack<int> numberStack;
        int index = 0;
        
        while(index < tokens.size()) {
            int left, right;
            string token = tokens[index];
            index += 1;
            
            if (token == "+"){
                left = numberStack.top();
                numberStack.pop();
                right = numberStack.top();
                numberStack.pop();
                numberStack.push(left + right);
                continue;
            }
                    
            if (token == "-" and token.length() == 1) {
                left = numberStack.top();
                numberStack.pop();
                right = numberStack.top();
                numberStack.pop();
                numberStack.push(right - left);
                continue;
            }
                    
            if(token == "/") {
                left = numberStack.top();
                numberStack.pop();
                right = numberStack.top();
                numberStack.pop();
                numberStack.push(right / left);
                continue;
            }
            
            if(token == "*") {
                left = numberStack.top();
                numberStack.pop();
                right = numberStack.top();
                numberStack.pop();
                numberStack.push(right * left);
                continue;
            }
            
            int number = stoi(token);
            numberStack.push(number);
        }
        return numberStack.top();
    }
};