[LeetCode] Different ways to add parentheses

Problem statement (link):

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Analysis:

This problem statement is a bit misleading (in a good way) so that my first attempt is to construct the different parenthesesed strings, and compute each string individually. This approach is exponential in both space and time complexity.

Now, the problems that ask for "all possible results" is usually solved using DFS approach. Don't get confused about the * operator as it would be treated equivalently as the + and - because of the parentheses. In the end, all the question asks is to find all possible combinations using parentheses.

With that, we could construct the solutions bottom-up. It's exactly the same as Unique Binary Tree II problem if we think each node as an arithmetic string. For instance,  in Example 2, we have the following ways of constructing the solutions:

Recursion Trees:
1)
                                        2 * 3 - 4 * 5
                                      /                     \
                                   2                   3 - 4 * 5
                                                       /             \
                                                     3             4 * 5
                                                                     /     \
                                                                    4      5
2)
                                        2 * 3 - 4 * 5
                                      /                     \
                                 2 * 3                  4 * 5
                                /       \                 /        \
                              2          3            4           5
3) ...
4) ...
5) ...

You get the idea.

Only extra work we need to do is instead of connecting the nodes, we compute each node (arithmetic string). The time complexity is still exponential but the code looks very clean.

Code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
                for (Integer int1: diffWaysToCompute(input.substring(0, i))) {
                    for (Integer int2: diffWaysToCompute(input.substring(i+1))) { // i+1: to skip the operator char
                        res.add(c=='+' ? int1+int2 : c=='-' ? int1-int2 : int1*int2);
                    }
                }
            }
        }

        if (res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}

[LeetCode] Generate Parentheses

Problem Statement (link):

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
The problem asks for all combinations, this usually indicates it's a DFS problem.

In the recursion function, if we've used up all left and right parentheses, we push the formed string into result vector. Otherwise, we can add either left parentheses or right parentheses. The code for this problem is shown in Sol 1 below.

The extended version of this problem is that instead of only having parentheses, we are given n1 parentheses pairs, n2 bracket pairs, and n3 curly parentheses, and we are asked for the same thing - all combinations.

The idea is pretty similar to the simple version. The only difference is that we can do one of the following:
1) add left parentheses '(';
2) add left bracket '[';
3) add left curly parentheses '{';
4) add the right part, depending on the left situation, we choose either ')', ']', or '}'.

The code is shown in Sol 2 below.

Code:
Sol 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n<1) return res;
        dfs(res, "", "", n);
        return res;
    }
    void dfs(vector<string> &res, string left, string tmp, int n) {
        if (left.size()==0 && n==0) {
            res.push_back(tmp);
            return;
        }
        if (n>0) {
            dfs(res, "("+left, tmp+"(", n-1);
        }
        if (left.size()>0) {
            dfs(res, left.substr(1), tmp+")", n);
        }
    }
};

Sol 2:

string rightPart(string left) {
    if (left=="(") return ")";
    else if (left=="[") return "]";
    else return "}";
}

void dfsParen(vector<string> &res, string leftStack, string str, int n1, int n2, int n3) {
    if (leftStack.empty() && n1==0 && n2==0 && n3==0) {
        res.push_back(str);
        return;
    }

    // add left parentheses
    if (n1>0) {
        dfsParen(res, "("+leftStack, str+"(", n1-1, n2, n3);
    }
    if (n2>0) {
        dfsParen(res, "["+leftStack, str+"[", n1, n2-1, n3);
    }
    if (n3>0) {
        dfsParen(res, "{"+leftStack, str+"{", n1, n2, n3-1);
    }

    // add right parentheses
    if (!leftStack.empty()) {
        dfsParen(res, leftStack.substr(1), str+rightPart(leftStack.substr(0,1)), n1, n2, n3);
    }
}

vector<string> getParen(int n1, int n2, int n3) {
    vector<string> res;
    if (n1==0 && n2==0 && n3==0) return res;
    string leftStack;
    string str="";
    dfsParen(res, leftStack, str, n1, n2, n3);
    return res;
}

[LeetCode] Scramble String

Problem Statement (link):

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Analysis:
The problem nicely defined the scramble string as a node-swapped binary tree. Thus, we want to check any two siblings that if they are swapped.

Consider base cases:
For any string pairs, if they are of different size or consisted of different sets of letters, they are not scramble string. Further:
- If two string are the same, they are scramble string

Consider the recursion. Suppose we have the following two trees:

    node1
   /    \
left1   right1

    node2
   /    \
left2   right2

we will need to check isScramble(left1, left2) && isScramble(right1, right2), or isScramble(left1, right2) && isScramble(right1, left2), make sure the two strings passed in are the same length, as different-length strings are guaranteed to be non-Scramble.

The time complexity of this recursive algorithm is pretty high though in exponential. It gets pass the OJ because the conditions that I check before going to recursions.

In the worst situation, for any recursion f(n), we will check all the combinations twice, i.e., f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)], thus, f(n+1)=3*f(n), we have f(n)=3^n.

Code:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len=s1.size();
        if (s1==s2) return true;
        if (s1.size()!=s2.size()) return false;
        int val1=0, val2=0;
        for (int i=0; i<len; i++) {
            val1+=s1[i]-'a';
            val2+=s2[i]-'a';
        }
        if (val1!=val2) return false;
       
        for (int i=1; i<len; i++) {
            string a1=s1.substr(0,i);
            string b1=s1.substr(i);
            string a2=s2.substr(0,i);
            string b2=s2.substr(i);
            if (isScramble(a1,a2)&&isScramble(b1,b2))
                return true;
            string a3=s2.substr(len-i);
            string b3=s2.substr(0,len-i);
            if (isScramble(a1,a3)&&isScramble(b1,b3))
                return true;
        }
        return false;
    }
};

[LeetCode] Surrounded Regions

Problem Statement (link):

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Analysis:
Rather than recording the 2D positions for any scanned 'O', a trick is to substitute any border 'O's with another character - here in the Code I use 'Y'. And scan the board again to change any rest 'O's to 'X's, and change 'Y's back to 'O's.

We start searching 'O' from the four borders. I tried DFS first, the OJ gives Runtime error on the 250x250 large board; In the Sol 2 below, I implement BFS instead, and passed all tests.

The time complexity is O(n^2), as in the worst case, we may need to scan the entire board.

Code:
1, DFS

class Solution {
public:
    // dfs - Runtime error on large board 250x250
    void dfs(vector<vector<char>> &board, int r, int c) {
        if (r<0||r>board.size()-1||c<0||c>board[0].size()-1||board[r][c]!='O')
            return;
        board[r][c]='Y';
        dfs(board, r-1, c);
        dfs(board, r+1, c);
        dfs(board, r, c-1);
        dfs(board, r, c+1);
    }
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // dfs from boundary to inside
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O')
                dfs(board, 0, i);   // first row
            if (board[c-1][i]=='O')
                dfs(board, c-1, i); // last row
        }
        for (int i=0; i<board.size(); i++) {
            if (board[i][0]=='O')
                dfs(board, i, 0);   // first col
            if (board[i][c-1])
                dfs(board, i, c-1); // last col
        }
        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O')
                    board[i][j]='X';
                else if (board[i][j]=='Y')
                    board[i][j]='O';
            }
        }
    }
};

2, BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // queues to store row and col indices
        queue<int> qr;
        queue<int> qc;
        // start from boundary
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O') { qr.push(0); qc.push(i); }
            if (board[r-1][i]=='O') { qr.push(r-1); qc.push(i); }
        }
        for (int i=0; i<r; i++) {
            if (board[i][0]=='O') { qr.push(i); qc.push(0); }
            if (board[i][c-1]=='O') { qr.push(i); qc.push(c-1); }
        }
        // BFS
        while (!qr.empty()) {
            int rt=qr.front(); qr.pop();
            int ct=qc.front(); qc.pop();
            board[rt][ct]='Y';
            if (rt-1>=0 && board[rt-1][ct]=='O') { qr.push(rt-1); qc.push(ct); } // go left
            if (rt+1<r && board[rt+1][ct]=='O') { qr.push(rt+1); qc.push(ct); } // go right
            if (ct-1>=0 && board[rt][ct-1]=='O') { qr.push(rt); qc.push(ct-1); } // go up
            if (ct+1<c && board[rt][ct+1]=='O') { qr.push(rt); qc.push(ct+1); } // go down
        }

        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O') board[i][j]='X';
                else if (board[i][j]=='Y') board[i][j]='O';
            }
        }
    }
};

[LeetCode] Path Sum I && II

Path Sum I

Problem Statement (link):

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Analysis:
This problem is a variation of tree traversal. We DFS the binary tree to find if any root-to-leaf path has the same value sum. We continue searching until we find a path.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root==NULL) return false;
        return trav(root, 0, sum);
    }

    bool trav(TreeNode *node, int pathSum, int sum) {
        bool result = false;
        pathSum += node->val;
        if (node->left==NULL && node->right==NULL)
            if (pathSum==sum)
                return true;
        if (node->left!=NULL)
            result = trav(node->left, pathSum, sum);
        if (!result && node->right!=NULL)
            result = trav(node->right, pathSum, sum);
        return result;
    }
};

Path Sum II

Problem Statement (link):

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis:
The idea is basically the same as the previous problem. But instead of updating the value sum, we store the nodes as we traverse down the tree. When we reach the leaf, we check if the sum value of all nodes in the path equals the expected sum, if so, we push the path to out vector.

It is important to pop_back the node after we push_back it into path vector. This ensures that the path vector only stores the nodes in the current path, and thus we could reuse the path vector as we traverse. This is a common trick in tree traversal.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > out;
        if (root==NULL) return out;
        vector<int> path;
        path.push_back(root->val);
        recur(root, sum, out, path);
        return out;
    }
    void recur(TreeNode *node, int sum, vector<vector<int>> &out, vector<int> &path) {
        if (node->left==NULL && node->right==NULL) {
            int temp=0;
            for (int i=0; i<path.size(); i++) temp+=path[i];
            if (temp==sum) out.push_back(path);
            return;
        }

        if (node->left!=NULL) {
            path.push_back(node->left->val);
            recur(node->left, sum, out, path);
            path.pop_back();
        }
        if (node->right!=NULL) {
            path.push_back(node->right->val);
            recur(node->right, sum, out, path);
            path.pop_back();
        }
    }
};

[LeetCode] Flatten Binary Tree to Linked List

Problem Statement (link):

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Analysis:
Observe the flattened tree closely, we find that it's basically a pre-order traversal transformation. However, what's more than that is we need to link the tree properly, as in-place transformation is required.

The idea is: before we traverse the left sub-tree of a node, we use a pointer to save the right child, because when we finished left sub-tree traversal, the root node's right child would be the current left child. Additionally, we would need another pointer prev to store the previous visited node, as later when we need to link the node to it's previous node.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // Recursive preorder traversal
    void flatten(TreeNode *root) {
        TreeNode *prev = NULL;
        recur(root, prev);
    }
    void recur(TreeNode *node, TreeNode *&prev) {
        if (node==NULL) return;
        TreeNode *saveRightNode = node->right;

        if (prev!=NULL) {
            prev->right=node;
            prev->left=NULL;
        }
        prev=node;
        recur(node->left, prev);
        recur(saveRightNode, prev);
    }
};

[LeetCode] Unique Binary Search Trees I && II

Unique Binary Search Trees I

Problem Statement (link):

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:
At first sight, this problem seems complicated. We may get some salt if we divide the problem into smaller sub-problems.

If n=0, there is 1 BST, which is the NULL tree.
If n=1, there is 1 BST, which is the single root node.
If n=2, there is 2 BST, which are BST with 1 being the root and 2 being the root.
...

We observe that for a value k, the root node may be any k=[1:n]. Thus, the number of BSTs in total is the number of sub-trees with node k valued from 1 to n.

Suppose the root node is k, then its left sub-tree consists of all nodes less that k, it's right sub-tree consists of all nodes larger than k. Then number of BSTs with root node k is then the product of number of BSTs of left sub-tree and number of BSTs of right sub-tree. Further, The number of BSTs of the left sub-tree is the number of sub-trees with the left root node valued from 1 to k-1, the number of BSTs of the right sub-tree is the number of sub-sub-trees with the right root node valued from k+1 to n. Thus we could model and solve this problem with recursion.

Furthermore, if we think twice about the method, it's sort of similar to the idea of DP - having previous calculated results stored, calculate and update new results.

Code:

class Solution {
public:
    int numTrees(int n) {
        // count[i] - number of unique BST constructed from i nodes
        vector<int> count(n+1);
        count[0] = 1;
        recur(count, n);
        return count[n];
    }

    void recur(vector<int> &count, int n) {
        for (int i=1; i<=n; i++) {
            // k - all possible num of nodes of left subtree
            for (int k=0; k<i; k++) {
                count[i] += count[k]*count[i-k-1];
            }
        }
    }
};

Unique Binary Search Trees II

Problem Statement (link):

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:
This problem is a bit difficult as it's not easy to come up with a clear solution.

First, the problem asks for "all" BSTs, similar to the previous problem, we consider using DFS on every possible node values, i.e., from 1 through n.

The difficulty lies in finding a way to store each BST. The root node's value i of a valid BST must be within 1 and n, the root of its left subtree must be within 1 and i-1, the root of its right subtree must be within i+1 and n. This idea is same as that of the previous problem. Now, suppose we have all the possible nodes stored in two vectors - leftSub and rightSub, in order to construct a tree, we must construct a new root node with value i that points to a member in leftSub and points to a member in rightSub, respectively. Then, we push the node into our result vector.

Codes:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode*> res;
        recur(1, n, res);
        return res;
    }
    void recur(int l, int r, vector<TreeNode*> &res) {
        if (l>r) 
            res.push_back(NULL);
        else {
            for (int i=l; i<=r; i++) {
                // recursively build-up left and right subtree for root node i
                vector<TreeNode*> leftSub, rightSub;
                recur(l, i-1, leftSub);
                recur(i+1, r, rightSub);
                // Choose left and right subtree combinations for root node i
                for (int j=0; j<leftSub.size(); j++) {
                    for (int k=0; k<rightSub.size(); k++) { 
                        TreeNode* node=new TreeNode(i);
                        node->left = leftSub[j];
                        node->right= rightSub[k];
                        res.push_back(node);
                    }
                }
            }
        }
    }
};

[LeetCode] Combinations

Problem Statement (link):

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Analysis:
Another classic DFS problem. Once we see "all possible" key words, we need to consider using DFS idea.

Two things to think about:
1) Avoid duplicates - we use a int st to avoid choosing the same combination again. In other words, we only choose the numbers larger than current numbers.
2) Choose k numbers - we decrease k each time we choose a number.

Code:

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > outv;
        if (k==0 || n<k) return outv;
        vector<int> res;
        recur(outv, res, n, k, 0);
        return outv;
    }

    void recur(vector<vector<int>> &outv, vector<int> &res, int n, int k, int st) {
        if (k==0) {
            outv.push_back(res);
            return;
        }

        for (int i=st; i<n; i++) {
            res.push_back(i+1);
            recur(outv, res, n, k-1, i+1);
            res.pop_back();
        }
        return;
    }
};

[LeetCode] N-Queens I && II

N-Queens I

Problem Statement (link):

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement,
where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Analysis:
Eight queens puzzle is a classic problem in use of DFS backtracking algorithm, it can be generalized to a N-queens puzzle.

The high-level idea of the backtracking algorithm is to choose any location as a start, try all possible positions until no violation to the rule has found. If a violation is found, we immediately abandon current placement and move the next possible position, if all possibilities has been tried for current queen, we go back to the previous queen and move that queen to its next possible position.

As describe in the statement, the rule for this game is: only one queen is placed in each row and column. This rule is used to check whether a position is legal for placing a queen.

Thus, the pseudo code looks like this:

1. Place the first queen in the left upper corner of the table.
2. Save the attacked positions.
3. Move to the next queen (which can only be placed to the next line).
4. Search for a valid position. If there is one go to step 8.
5. There is not a valid position for the queen. Delete it (the x coordinate is 0).
6. Move to the previous queen.
7. Go to step 4.
8. Place it to the first valid position.
9. Save the attacked positions.
10. If the queen processed is the last stop otherwise go to step 3.

The time complexity is exponential, same as all other backtracking algorithms.

A space-saving trick is we use 1-D vector to store the queens' 2-D location, where A[i]=j indicates row i, col j has a queen.

Code:

class Solution {
public:
    vector<vector<string> > out;
    // main function
    vector<vector<string> > solveNQueens(int n) {
        if (n==0) return out;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        placeQueen(A, 0, n);    // starts from row 0
        return out;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) printOut(A, n);
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }

    // Update out to include current solution
    void printOut(vector<int> A, int n) {
        vector<string> v;   // a solution
        for (int i=0; i<n; i++){
            string s(n,'.');    // for each row
            s[A[i]] = 'Q';
            v.push_back(s);
        }

        out.push_back(v);
    }
};

N-Queens II

Problem statement (link):

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:
The algorithm is exactly the same as in N-Queens I. Only difference is that instead of populating the location of each queens when we find a solution, we only need to count the number of solutions.

Code:

class Solution {
public:
    vector<vector<string> > out;
    int num;
    // main function
    int totalNQueens(int n) {
        if (n==0) return 0;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        num = 0;
        placeQueen(A, 0, n);    // starts from row 0
        return num;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) num++;
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }
};

[LeetCode] Populating Next Right Pointers in Each Node I

Populating Next Right Pointers in Each Node I

Problem Statement (link):

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Analysis:
BFS using queue is an obvious solution to this problem. However, as we are asked to solve it without using extra space, we gotta find another way.

There are two types of connections:
1) Connect a node's left child to its right child;
2) Connect a node's right child to the node's sibling's left child, when the node doesn't have a sibling, we set its right child's next pointer to NULL;

A key is to the solution is that we need to connect the nodes while we are at their parent level, since we couldn't go back to the parent's sibling for type 2) connection.

The following code shows both recursive and iterative approaches.

Code:
Sol 1 - Recursive

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        if (root->left)
            root->left->next=root->right;
        if (root->right)
            root->right->next= root->next ? root->next->left:NULL;

        connect(root->left);
        connect(root->right);
    }
};

Sol 2 - Iterative

class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root!=NULL) {
            TreeLinkNode* firstNode=root;
            while(firstNode!=NULL) {
                if (firstNode->left)
                    firstNode->left->next=firstNode->right;
                if (firstNode->right)
                    firstNode->right->next= firstNode->next ? firstNode->next->left:NULL;

                firstNode=firstNode->next;
            }
            root=root->left;
        }
    }
};

Binary Tree Level-order traversal

Problem Statement:
Implement binary tree level-order traversal.

Analysis:
We usually use queue to realize BFS, the implementation is done in Sol 1. This is a standard BFS algorithm. It requires O(n) space and O(n) time, where n is the number of nodes in the tree.

However, recursion can be used to solve this problem as well, this algorithm is implemented in Sol 2. As we could see, we traverse the tree h time in order to print nodes in each level, where h is the tree height. This leads to the in-efficiency of this algorithm. However, it's good to know that recursion could be used in BFS problems. The overall time complexity is O(n^2), where n is the number of nodes in the tree.

Code:
Sol 1:

void levelOrderIter(TreeNode* root) {
    queue<TreeNode*> q;

    q.push(root);
    while (!q.empty()) {
        TreeNode* tmp=q.front();
        q.pop();
        cout<<tmp->val<<endl;

        if (tmp->left!=NULL) q.push(tmp->left);
        if (tmp->right!=NULL) q.push(tmp->right);
    }
    return;
}

Sol 2:

void levelOrder(TreeNode* root) {
    // height of tree
    int height=getHeight(root);
    // traverse each level
    for (int i=0; i<height; i++)
        printLevel(root, i);
    return;
}

void printLevel(TreeNode* node, int level) {
    if (node==NULL) return;

    if (level==0) {
        cout<<node->val<<endl;
        return;
    }

    printLevel(node->left, level-1);
    printLevel(node->right, level-1);
}

int getHeight(TreeNode* node) {
    if (node==NULL) return 0;
    int lHeight=getHeight(node->left);
    int rHeight=getHeight(node->right);
    return (lHeight>rHeight ? lHeight:rHeight)+1;
}

[LeetCode] Binary Tree Maximum Path Sum

Problem Statement (link):

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Analysis:
The idea is to use recursive DFS. For each node, we find the max sum for its left and right sub-tree, adding the node's value, we return a max summation to its parent.

In the following code, the maxSum variable is used to record the maximum summation that we got so far. The maxPath variable is the maximum summation of current node value adding its max left and right sub-tree path values.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = (root==NULL) ? 0:root->val;
        pathSum(root, maxSum);
        return maxSum;
    }

    // maxSum tracks the current max sum via a particular root node
    int pathSum(TreeNode* node, int& maxSum) {
        if (node==NULL) return 0;

        int l = pathSum(node->left, maxSum);
        int r = pathSum(node->right, maxSum);

        int maxPath = max(l>0?l:0, r>0?r:0) + node->val;
        maxSum = max(maxSum, (l>0?l:0) + (r>0?r:0) + node->val);
        return maxPath;
    }
};

[LeetCode] Clone Graph

Problem Statement (link):

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:
It's a standard graph traversal problem. Herein we use DFS to solve this problem.

We keep an unordered_map<int, Node*> visited to maintain the visited nodes - the label and the pointer to it. Note that the pointer is the pointer to nodes in the new graph.

A big difference between graph and tree is that cycles may exist. So whenever we visit a node, we add the node into the visited map. For each of its neighbors, we then check the visited map if the neighbor's label exists. Here we assume the label is unique for each node.

- If the label exists, it means we have visited this neighbor somewhere else - even if it is not currently in the neighbor's vector, we need to add the neighbor's pointer to the vector - by looking up in the visited map (Again, remember the visited map stores the label and new node's pointer).

- If the label doesn't exist, it implies that we haven't traversed the node, we then need to do a DFS recursion on that node.

Additionally, if the label/value of each node is different, we only need to change the visited map to unordered_map<Node*, Node> visited, where the two pointers are the pointer to node in the old graph and that to the corresponding node in the new graph.

Code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
    typedef UndirectedGraphNode Node;

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node==NULL) return NULL;
        unordered_map<int, Node*> visited;
        return recur(node, visited);
    }

    Node *recur(Node *node, unordered_map<int, Node*>& visited) {
        Node *newNode=new Node(node->label);
        visited.emplace(node->label, newNode);

        for (int i=0; i<node->neighbors.size(); i++) {
            if (visited.find(node->neighbors[i]->label)==visited.end())
                newNode->neighbors.push_back(recur(node->neighbors[i], visited));
            else
                newNode->neighbors.push_back(visited[node->neighbors[i]->label]);
        }
        return newNode;
    }
};

[LeetCode] Binary Tree Preorder && Inorder && Postorder Traversal

Tree traversal is quite standard problems. For each of the traversals, both recursive and Iterative methods are described.

Binary Tree Preorder Traversal

Problem Statement (link):

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

Analysis:
Recursive method is trivial as implemented in Sol 1.

In iterative method, a stack is used to store nodes temporarily. In each loop, the current top node in stack is popped and push_back in output vector, then we push its right child and left child in stack if not NULL. The push order is reversed compare to pre-order traversal as stack has the first-in-last-out property. This process continues until the stack is empty.

Code:
Sol 1 - Recursive:

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if (node==NULL) return;
    out.push_back(node->val);
    recur(node->left, out);
    recur(node->right, out);
}

Sol 2 - Iterative:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> nodeS;
        vector<int> valV;
        if (root == NULL) return valV;
        nodeS.push(root);
        while(!nodeS.empty()) {
            TreeNode *node = nodeS.top();
            nodeS.pop();
            valV.push_back(node->val);

            // Note the push order is reversed as the push order is exact reversed of pop order
            if (node->right != NULL) {
                nodeS.push(node->right);
            }
            if (node->left != NULL) {
                nodeS.push(node->left);
            }
        }
        return valV;
    }
};

Binary Tree Inorder Traversal

Problem Statement (link):

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?

Analysis:
A good analysis article about in-order traversal is here.

Recursive method is trivial as implemented in Sol 1.

In the iterative method, a stack is used to store nodes temporarily. We store nodes if it's not NULL, and traverse to its left child; we pop the nodes and store in output vector if current node is NULL, and traverse to its right child. As in Sol 2.

Code:
Sol 1 - Recursive:

vector<int> inorderTraversal(TreeNode *root) {
    vector<int> valV;
    inOrder(root, valV);
    return valV;
}

void inOrder(TreeNode *node, vector<int> &valV) {
    if (node==NULL) return;
    inOrder(node->left, valV);
    valV.push_back(node->val);
    inOrder(node->right, valV);
}

Sol 2 - Iterative:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
using namespace std;
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> output;
        if (root==NULL) return output;
        stack<TreeNode*> nodeS;
        TreeNode* node = root;
        while (node!=NULL || !nodeS.empty()) {
            if(node!=NULL) {
                nodeS.push(node);
                node = node->left;
            }
            else {
                node = nodeS.top();
                nodeS.pop();
                output.push_back(node->val);
                node = node->right;
            }
        }
    }
};

Binary Tree Postorder Traversal

Problem Statement (link):

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?

Analysis:
A very good article about the post-order traversal is here.

The recursive solution is trivial as implemented in Sol 1.

In the iterative method, two stacks are used - one stack method exists but a bit complicated. When traversing the tree from left child to right child, we push nodes into a nodeStack, then pop each node into outputStack. See Sol 2 below.

Code:
Sol 1: Recursive

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if(node==NULL) return;
    recur(node->left, out);
    recur(node->right, out);
    out.push_back(node->val);
}

Sol 2: Iterative

/**
 * Definition for binary tree
 * 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> output;
        if (root==NULL) return output;
        // use two stacks
        stack<TreeNode *> nodeStack;
        stack<TreeNode *> outputStack;
        TreeNode* node = root;
        nodeStack.push(node);
        while(!nodeStack.empty()) {
            node = nodeStack.top();
            outputStack.push(node);
            nodeStack.pop();
            if (node->left != NULL) nodeStack.push(node->left);
            if (node->right != NULL) nodeStack.push(node->right);
        }
        while(!outputStack.empty()) {
            node = outputStack.top();
            output.push_back(node->val);
            outputStack.pop();
        }
    }
};