150. Evaluate Reverse Polish Notation

Difficulty: Medium

Frequency: N/A

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.empty()) return 0;
        int n = tokens.size(), result;
        stack<int> s;
        for (int i = 0; i < n; i++) {
            string tmp = tokens[i];
            if (tmp == "+" || tmp == "-" || tmp == "*" || tmp == "/") {
                int num2 = s.top();
                s.pop();
                int num1 = s.top();
                s.pop();
                if (tmp == "+") {
                    result = num1 + num2;
                } else if (tmp == "-") {
                    result = num1 - num2;
                } else if (tmp == "*") {
                    result = num1 * num2;
                } else {
                    result = num1 / num2;
                }
                s.push(result);
            } else {
                s.push(stoi(tmp));
            }
        }
        return s.top();
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

084. Largest Rectangle in Histogram

Difficulty: Hard

Frequency: N/A

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), area = 0, height, left;
        stack<int> idx;
        for (int i = 0; i <= n; i++) {
            while (i == n || !idx.empty() && heights[idx.top()] > heights[i]) {
                if (i == n && idx.empty()) {
                    height = 0;
                    i++;
                } else {
                    height = heights[idx.top()];
                    idx.pop();
                }
                left = idx.empty() ? -1 : idx.top();
                area = max(area, height * (i - left - 1));
            }
            idx.push(i);
        }
        return area;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

071. Simplify Path

Difficulty: Medium

Frequency: N/A

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> paths;
        string tmp;
        stringstream ss(path);
        while (getline(ss, tmp, '/')) {
            if (tmp == "" || tmp == ".") continue;
            if (tmp == ".." && !paths.empty()) paths.pop_back();
            else if (tmp != "..") paths.push_back(tmp);
        }
        string result;
        for (string s : paths) result += "/" + s;
        return result.empty() ? "/" : result;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

145. Binary Tree Postorder Traversal

Difficulty: Hard

Frequency: N/A

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }
    void dfs(TreeNode* node, vector<int>& result) {
        if (!node) return;
        dfs(node->left, result);
        dfs(node->right, result);
        result.push_back(node->val);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

272. (Locked)Closest Binary Search Tree Value II

Difficulty: Hard

Frequency: N/A

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        priority_queue<pair<double, int>> pq;
        vector<int> result;
        dfs(root, pq, target, k);
        while (!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
    void dfs(TreeNode* node, priority_queue<pair<double, int>>& pq, double target, int k) {
        if (!node) return;
        pq.push(make_pair(abs(target - (double)node->val), node->val));
        if (pq.size() > k) pq.pop();
        dfs(node->left, pq, target, k);
        dfs(node->right, pq, target, k);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?


Questions:
1. Recursive or iteratively

Test Cases:

1. [#] empty
2. [1] root only
3. [1, 2, #, 3, #, 4] all left
4. [1, #, 2, #, #, #, 3] all right
5. [1, #, 2, 3] normal

Solution 1:
Data structure:
vector, tree
Method:
Recursive:
1. helper(node->left)
2. push(node->val)
3. helper(node->right)
Complexity:
Runtime:
worst case: o(n^2)
average: o(nlogn)
Space:
o(n)
Code:
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderTraverse(root, result);
        return result;
    }
    void inorderTraverse(TreeNode *node, vector<int>& result) {
        if (!node) return;
        inorderTraverse(node->left, result);
        result.push_back(node->val);
        inorderTraverse(node->right, result);
    }
};

 Solution 2:
Data structure:
Method:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Tree Traversals:

173. Binary Search Tree Iterator

Difficulty: Medium

Frequency: N/A

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> myStack;
    void pushLeft(TreeNode *node) {
        for (; node != NULL; node = node->left) myStack.push(node);
    }
public:
    BSTIterator(TreeNode *root) {
        pushLeft(root);
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !myStack.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *tmp = myStack.top();
        myStack.pop();
        pushLeft(tmp->right);
        return tmp->val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: