[Facebook] Products of all elements

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]

Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]

      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

[Thoughts]

An explaination of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.
Then multiplying the two arrays element by element gives the required result
My code would look something like this:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i)
{
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i)
{
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i)
{
  products[i]=products_below[i]*products_above[i];
}

If you need to be O(1) in space too you can do this (which is less clear IMHO)

int a[N] // This is the input
int products[N];

// Get the products below the curent index
p=1;
for(int i=0;i<N;++i)
{
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i)
{
  products[i]*=p;
  p*=a[i];
}

[FaceBook] Hanoi Moves, Solution

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5


Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.

Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

2 3
1 1
2 2
Sample Output #00:

3
1 3
1 2
3 2


Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"


[Thoughts]
No good idea, only brute-force can hit my mind now. seems a simple question, but the implementation really costs me some time.

Update: some people talk about using tree to do the BFS (http://comments.gmane.org/gmane.comp.programming.algogeeks/30920) or A* search (http://en.wikipedia.org/wiki/A*_search_algorithm). But I would say this is a bit over engineering.


[Code]

1:  /*  
2:  Please write complete compilable code.  
3:  Read input from standard input (STDIN) and print output to standard output(STDOUT).  
4:  For more details, please check https://www.interviewstreet.com/recruit/challenges/faq/view#stdio  
5:  */  
6:  #include <climits>  
7:  #include <iostream>  
8:  using namespace std;   
9:  int initial[9];  
10:  int expected[9];  
11:  int CurDiscInPeg[9];  
12:  int n, k;  
13:  int moveSeq[9][2];  
14:  int minSteps = 7;  
15:  int minMoveSeq[9][2];  
16:  void refreshPeg()  
17:  {  
18:    for(int i =1; i<= k; i++)  
19:    {  
20:      CurDiscInPeg[i] = INT_MAX; //no disk on it.  
21:      for(int j =1; j<=n; j++)  
22:      {  
23:        if(initial[j] == i)  
24:        {  
25:          CurDiscInPeg[i] =j;  
26:          break;  
27:        }  
28:      }  
29:    }  
30:  }  
31:  bool verify(int depth)  
32:  {  
33:    int z = 1;  
34:    for(; z<=n; z++)  
35:    {  
36:      if(initial[z]!=expected[z])  
37:        return false;  
38:    }  
39:    minSteps = depth;  
40:    for(int z = 1; z<=minSteps; z++)  
41:    {  
42:      minMoveSeq[z][0] = moveSeq[z][0];  
43:      minMoveSeq[z][1] = moveSeq[z][1];  
44:    }       
45:    return true;        
46:  }  
47:  void Move(int depth)  
48:  {  
49:    if(depth > minSteps) return;  
50:    for(int i =1; i<=k; i++)  
51:    {  
52:      for(int j=1; j<=k; j++)  
53:      {  
54:        if(CurDiscInPeg[i] >= CurDiscInPeg[j])  
55:          continue;  
56:        int disc = CurDiscInPeg[i];  
57:        initial[disc] = j;  
58:        moveSeq[depth][0] = i;  
59:        moveSeq[depth][1] = j;  
60:        if(verify(depth)) return;  
61:        refreshPeg();  
62:        Move(depth+1);  
63:        initial[disc] = i;  
64:        refreshPeg();  
65:      }  
66:    }  
67:  }  
68:  int main()  
69:  {  
70:    cin>>n;  
71:    cin>>k;  
72:    for(int i =1; i<=n; i++)  
73:    {  
74:      cin>>initial[i];  
75:    }  
76:    for(int i =1; i<=n; i++)  
77:    {  
78:      cin>>expected[i];  
79:    }  
80:    refreshPeg();  
81:    Move(1);  
82:    cout<<minSteps<<endl;  
83:    for(int i =1; i<=minSteps; i++)  
84:    {      
85:      cout<<minMoveSeq[i][0]<<" "<<minMoveSeq[i][1]<<endl;  
86:    }  
87:  }  

[LeetCode] Decode Ways, Solution

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

» Solve this problem

[Thoughts]

Similar as "[LeetCode] Climbing Stairs, Solution". DP. Just add some logic to compare character.

Transformation function as:
Count[i] = Count[i-1]  if S[i-1] is a valid char
       or   = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char.

[Code]

1:    int numDecodings(string s) {  
2:      if(s.empty() || s[0] =='0') return 0;      
3:      if(s.size() ==1) return check(s[0]);  
4:      int fn=0, fn_1=0, fn_2=1;      
5:      fn_1 = (check(s[0]) * check(s[1]))+check(s[0], s[1]);       
6:      for(int i=2; i< s.size(); i++)  
7:      {    
8:        if(check(s[i])) fn+= fn_1;         
9:        if(check(s[i-1], s[i])) fn+=fn_2;  
10:        if(fn ==0)   
11:          return 0;  
12:        fn_2 = fn_1;  
13:        fn_1 = fn;  
14:        fn=0;     
15:      }  
16:      return fn_1;  
17:    }  
18:    int check(char one)   
19:    {  
20:      return (one != '0') ? 1 : 0;      
21:    }  
22:    int check(char one, char two)  
23:    {  
24:      return (one == '1' || (one == '2' && two <= '6'))  
25:      ? 1 : 0;      
26:    }   

[LeetCode] Count and Say, Solution

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

» Solve this problem

[Thoughts]
string-operation. The only trick thing is Line11. seq[seq.size()] always '\0'. It will help to save an "if" statement.


[Code]

1:    string countAndSay(int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string seq = "1";  
5:      int it = 1;  
6:      while(it<n)  
7:      {  
8:        stringstream newSeq;  
9:        char last = seq[0];  
10:        int count =0;  
11:        for(int i =0; i<= seq.size();i++)  
12:        {  
13:          if(seq[i] ==last)  
14:          {  
15:            count ++;  
16:            continue;  
17:          }  
18:          else  
19:          {  
20:            newSeq<<count<<last;  
21:            last = seq[i];   
22:            count =1;  
23:          }  
24:        }  
25:        seq = newSeq.str();  
26:        it++;  
27:      }  
28:      return seq;  
29:    }  

[LeetCode] Convert Sorted List to Binary Search Tree, Solution

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

[Thoughts]
It is similar with "Convert Sorted Array to Binary Search Tree". But the difference here is we have no way to random access item in O(1).

If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST
3. build right sub BST
4. do this recursively.

But for linked list, we can't do that because Top-To-Bottom are heavily relied on the index operation.
There is a smart solution to provide an Bottom-TO-Top as an alternative way, http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

With this, we can insert nodes following the list’s order. So, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

[Code]

1:    TreeNode *sortedListToBST(ListNode *head) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int len =0;  
5:      ListNode *p = head;  
6:      while(p)  
7:      {  
8:        len++;  
9:        p = p->next;  
10:      }  
11:      return BuildBST(head, 0, len-1);  
12:    }  
13:    TreeNode* BuildBST(ListNode*& list, int start, int end)  
14:    {  
15:      if (start > end) return NULL;  
16:      int mid = (start+end)/2;   //if use start + (end - start) >> 1, test case will break, strange!
17:      TreeNode *leftChild = BuildBST(list, start, mid-1);  
18:      TreeNode *parent = new TreeNode(list->val);  
19:      parent->left = leftChild;  
20:      list = list->next;  
21:      parent->right = BuildBST(list, mid+1, end);  
22:      return parent;  
23:    }  

[LeetCode] Container With Most Water, Solution

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

» Solve this problem

[Thoughts]
For any container, its volume depends on the shortest board.
Two-pointer scan. And always move with shorter board index.


[Code]

1:    int maxArea(vector<int> &height) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start =0;  
5:      int end = height.size()-1;  
6:      int maxV = INT_MIN;  
7:      while(start<end)  
8:      {  
9:        int contain = min(height[end], height[start]) * (end-start);  
10:        maxV = max(maxV, contain);  
11:        if(height[start]<= height[end])  
12:        {  
13:          start++;  
14:        }  
15:        else  
16:        {  
17:          end--;  
18:        }  
19:      }  
20:      return maxV;  
21:    }  

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal, Solution

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

[Thoughts]

There is an example.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

The preorder and inorder traversals for the binary tree above is:

preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}

The first node in preorder alwasy the root of the tree. We can break the tree like:
1st round:
preorder:  {7}, {10,4,3,1}, {2,8,11}
inorder:     {4,10,3,1}, {7}, {11, 8,2}

        _______7______
       /              \
    {4,10,3,1}       {11,8,2}

Since we alreay find that {7} will be the root, and in "inorder" sert, all the data in the left of {7} will construct the left sub-tree. And the right part will construct a right sub-tree. We can the left and right part agin based on the preorder.

2nd round
left part                                                                            right part
preorder: {10}, {4}, {3,1}                                              {2}, {8,11}
inorder:  {4}, {10}, {3,1}                                                {11,8}, {2}

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4      {3,1}   {11,8}

see that, {10} will be the root of left-sub-tree and {2} will be the root of right-sub-tree.

Same way to split {3,1} and {11,8}, yo will get the complete tree now.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

So, simulate this process from bottom to top with recursion as following code.

[Code]

1:    TreeNode *buildTree(  
2:      vector<int> &preorder,   
3:      vector<int> &inorder) {  
4:      // Start typing your C/C++ solution below  
5:      // DO NOT write int main() function  
6:      return BuildTreePI(  
7:        preorder, inorder, 0, preorder.size()-1, 0, preorder.size());  
8:    }    
9:    TreeNode* BuildTreePI(  
10:      vector<int> &preorder,  
11:      vector<int> &inorder,  
12:      int p_s, int p_e,  
13:      int i_s, int i_e)  
14:    {  
15:      if(p_s > p_e)  
16:        return NULL;  
17:      int pivot = preorder[i_s];  
18:      int i =p_s;  
19:      for(;i< p_e; i++)  
20:      {  
21:        if(inorder[i] == pivot)  
22:          break;  
23:      }  
24:      TreeNode* node = new TreeNode(pivot);  
25:      node->left = BuildTreePI(preorder, inorder, p_s, i-1, i_s+1, i-p_s+i_s);  
26:      node->right = BuildTreePI(preorder, inorder, i+1, p_e, i-p_s+i_s+1, i_e);  
27:      return node;      
28:    }  

[LeetCode] Combinations, Solution

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],
]

» Solve this problem

[Thoughts]
Similar as "Conbination Sum". But here the terminate condition is "k", not sum.

[Code]

1:    vector<vector<int> > combine(int n, int k) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<vector<int> > result;  
5:      vector<int> solution;  
6:      GetCombine(n,k,1, solution, result);  
7:      return result;  
8:    }  
9:    void GetCombine(  
10:      int n,   
11:      int k,   
12:      int level,  
13:      vector<int>& solution,  
14:      vector<vector<int> >& result)  
15:    {      
16:      if(solution.size() == k)  
17:      {  
18:        result.push_back(solution);  
19:        return;  
20:      }  
21:      for(int i =level; i<= n; i++)  
22:      {  
23:        solution.push_back(i);  
24:        GetCombine(n,k,i+1, solution, result);  
25:        solution.pop_back();  
26:      }  
27:    }  

[LeetCode] Combination Sum II, Solution

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

» Solve this problem

[Thoughts]
Very similar with previous "Combination Sum". The only difference is marked as red in Code part. Need to handle the index and skip duplicate candidate.


[Code]

1:    vector<vector<int> > combinationSum2(vector<int> &num, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      // Start typing your C/C++ solution below  
5:      // DO NOT write int main() function  
6:      vector<vector<int> > result;  
7:      vector<int> solution;  
8:      int sum=0;  
9:      std::sort(num.begin(), num.end());  
10:      GetCombinations(num,sum, 0, target, solution, result);  
11:      return result;  
12:    }  
13:    void GetCombinations(  
14:      vector<int>& candidates,  
15:      int& sum,  
16:      int level,  
17:      int target,  
18:      vector<int>& solution,  
19:      vector<vector<int> >& result)  
20:    {  
21:      if(sum > target) return;  
22:      if(sum == target)  
23:      {  
24:        result.push_back(solution);  
25:        return;  
26:      }  
27:      for(int i =level; i< candidates.size(); i++)  
28:      {  
29:        sum+=candidates[i];  
30:        solution.push_back(candidates[i]);  
31:        GetCombinations(candidates, sum, i+1, target, solution, result);  
32:        solution.pop_back();  
33:        sum-=candidates[i];    
34:        while(i<candidates.size()-1 && candidates[i] == candidates[i+1]) i++;  
35:      }  
36:    }  

[LeetCode] Combination Sum, Solution

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

» Solve this problem

[Thoughts]

This is a normal recursion question. For each candidate, add and verify the target. If it hit, add it as a part of solution.

[Code]

1:    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<vector<int> > result;  
5:      vector<int> solution;  
6:      int sum=0;  
7:      std::sort(candidates.begin(), candidates.end());  
8:      GetCombinations(candidates,sum, 0, target, solution, result);  
9:      return result;  
10:    }  
11:    void GetCombinations(  
12:      vector<int>& candidates,  
13:      int& sum,  
14:      int level,  
15:      int target,  
16:      vector<int>& solution,  
17:      vector<vector<int> >& result)  
18:    {  
19:      if(sum > target) return;  
20:      if(sum == target)  
21:      {  
22:        result.push_back(solution);  
23:        return;  
24:      }  
25:      for(int i =level; i< candidates.size(); i++)  
26:      {  
27:        sum+=candidates[i];  
28:        solution.push_back(candidates[i]);  
29:        GetCombinations(candidates, sum, i, target, solution, result);  
30:        solution.pop_back();  
31:        sum-=candidates[i];        
32:      }  
33:    }  

[LeetCode] Climbing Stairs, Solution

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

» Solve this problem

[Thoughts]
DP. The transition function should be:
 f(n) = f(n-1) + f(n-2)  n>2;
     or = 1   n=1
    or  = 2   n=2


[Code]

1:    int climbStairs(int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int fn_2 =1, fn_1=2;  
5:      if(n==1) return fn_2;  
6:      if(n ==2) return fn_1;  
7:      int fn;  
8:      for(int i =3; i<=n; i++)  
9:      {  
10:        fn = fn_2+fn_1;  
11:        fn_2 = fn_1;  
12:        fn_1= fn;  
13:      }  
14:      return fn;  
15:    }  

[LeetCode] Add Two Numbers, Solution

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

» Solve this problem

[Thoughts]
Similar as "Add Binary". The only difference is the pointer operation.


[Code]

1:    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
2:            ListNode* result = new ListNode(-1);  
3:            ListNode* pre = result;  
4:            ListNode *pa = l1, *pb = l2;  
5:            int carry =0;  
6:            while(pa!=NULL || pb!=NULL)  
7:            {  
8:                 int av = pa == NULL? 0:pa->val;  
9:                 int bv = pb == NULL? 0:pb->val;  
10:                 ListNode* node = new ListNode((av+bv+carry)%10);  
11:                 carry = (av+bv+carry)/10;  
12:                 pre->next = node;  
13:                 pre = pre->next;  
14:                 pa = pa==NULL? NULL:pa->next;  
15:                 pb = pb==NULL? NULL:pb->next;  
16:            }            
17:            if(carry >0)  
18:                 pre->next = new ListNode(1);  
19:            pre = result->next;  
20:            delete result;  
21:            return pre;  
22:       }  

[LeetCode] 3Sum Closest, Solution

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

» Solve this problem

[Thoughts]
Similar as 3Sum. Only need to add a new variable to track the minimum history.

[Code]

1:    int threeSumClosest(vector<int> &num, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      std::sort(num.begin(), num.end());  
5:      int len = num.size();  
6:      int minV = INT_MAX, record;  
7:      for(int i =0; i< len; i++)  
8:      {        
9:        int start = i+1, end =len-1;             
10:        while(start<end)  
11:        {  
12:          int sum = num[i] + num[start] + num[end];  
13:          if(sum == target)  
14:          {   
15:            minV = 0;  
16:            record = sum;  
17:            break;  
18:          }  
19:          if(sum < target)  
20:          {  
21:            if(target-sum < minV)  
22:            {  
23:              minV = target-sum;  
24:              record = sum;  
25:            }  
26:            start++;            
27:          }  
28:          else  
29:          {  
30:            if(sum-target < minV)  
31:            {  
32:              minV = sum - target;  
33:              record = sum;  
34:            }  
35:            end--;  
36:          }  
37:        }        
38:        while(i<len-1 && num[i] == num[i+1]) i++;  
39:      }  
40:      return record;  
41:    }  

[LeetCode] 3 Sum, Solution

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

» Solve this problem

[Thoughts]
Two-pointer scan.

[Code]

1:    vector<vector<int> > threeSum(vector<int> &num) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      std::sort(num.begin(), num.end());  
5:      vector<vector<int> > result;  
6:      int len = num.size();  
7:      for(int i =0; i< len; i++)  
8:      {  
9:        int target = 0-num[i];  
10:        int start = i+1, end =len-1;  
11:        while(start<end)  
12:        {  
13:          if(num[start] + num[end] == target)  
14:          {  
15:            vector<int> solution;  
16:            solution.push_back(num[i]);  
17:            solution.push_back(num[start]);  
18:            solution.push_back(num[end]);  
19:            result.push_back(solution);  
20:            start++; end--;  
21:            while(start<end && num[start] == num[start-1]) start++;  
22:            while(start<end && num[end] == num[end+1]) end--;  
23:          }  
24:          else if(num[start] + num[end] < target)  
25:          {  
26:            start++;  
27:          }  
28:          else  
29:          {  
30:            end--;  
31:          }  
32:        }  
33:        if(i<len-1)  
34:        {  
35:          while(num[i] == num[i+1]) i++;  
36:        }  
37:      }  
38:      return result;  
39:    }  

[Some tricks]
1. Line 21 and Line 22.
    filter the duplicate during two-pointer scan. For example [-2, 0, 0, 2,2], the expected output should be [-2,0,2]. If no filter here, the output will be duplicate as [-2,0,2] and [-2,0,2]
2. Line 35
   filter the duplicate for outside iteration. For example [-2, -2, -2, 0,2].

[LeetCode] Binary Tree Maximum Path Sum Solution

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.

» Solve this problem

[Thoughts]
For each node like following, there should be four ways existing for max path:

1. Node only
2. L-sub + Node
3. R-sub + Node
4. L-sub + Node + R-sub

Keep trace the four path and pick up the max one in the end.

[Code]

1:    int maxPathSum(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int maxAcrossRoot=INT_MIN;  
5:      int maxEndByRoot = GetMax(root, maxAcrossRoot);  
6:      return std::max(maxAcrossRoot, maxEndByRoot);  
7:    }  
8:    int GetMax(TreeNode *node, int& maxAcrossRoot)  
9:    {  
10:      if(node == NULL) return 0;  
11:      int left = GetMax(node->left, maxAcrossRoot);  
12:      int right = GetMax(node->right, maxAcrossRoot);  
13:      int cMax = node->val;  
14:      if(left>0)  
15:        cMax+=left;  
16:      if(rifht>0)  
17:        cMax+=right;  
18:      maxAcrossRoot = std::max(maxAcrossRoot, cMax);  
19:      return std::max(  
20:        node->val,   
21:        std::max(node->val+left, node->val+right));  
22:    }  

[LeetCode] Binary Tree Level Order Traversal Solution

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

[Thoughts]
Two ways to resolve this problem:
1. Breadth first search
Initial an int variable to track the node count in each level and print level by level. And here need a QUEUE as a helper.
2. Depth first search
Rely on the recursion. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level and output them.
The cons is, DFS will revisit the node, which make it less efficient than BFS.

[Code]
BFS solution

1:    vector<vector<int> > levelOrder(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<vector<int> > result;  
5:      vector<TreeNode*> sta;  
6:      if(root == NULL) return result;  
7:      sta.push_back(root);  
8:      int nextLevCou=1;  
9:      int index=0;  
10:      while(index < sta.size())  
11:      {  
12:        int curLevCou = nextLevCou;  
13:        nextLevCou =0;  
14:        vector<int> level;  
15:        for(int i =index; i< index+curLevCou; i++)  
16:        {  
17:          root = sta[i];          
18:          level.push_back(root->val);  
19:          if(root->left!=NULL)  
20:          {  
21:            sta.push_back(root->left);  
22:            nextLevCou++;  
23:          }  
24:          if(root->right!=NULL)  
25:          {  
26:            sta.push_back(root->right);  
27:            nextLevCou++;  
28:          }  
29:        }  
30:        result.push_back(level);  
31:        index = index +curLevCou;  
32:      }  
33:      return result;  
34:    }  

DFS solution

1:    vector<vector<int> > levelOrder(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function      
4:      vector<vector<int> > output;  
5:      if(!root) return output;  
6:      vector<int> oneLine;  
7:      bool hasNextLevel=true;  
8:      int currentLevel =1;  
9:      while(hasNextLevel)  
10:      {  
11:        hasNextLevel = false;  
12:        LevelTravel(root, currentLevel, hasNextLevel, oneLine);  
13:        output.push_back(oneLine);  
14:        currentLevel ++;  
15:        oneLine.clear();  
16:      }  
17:      return output;  
18:    }  
19:    void LevelTravel(  
20:      TreeNode* node,   
21:      int level,  
22:      bool& hasNextLevel,  
23:      vector<int>& result)  
24:    {  
25:      if(!node) return;  
26:      if(level ==1)  
27:      {  
28:        result.push_back(node->val);  
29:        if(node->left || node->right)  
30:          hasNextLevel = true;  
31:        return;  
32:      }  
33:      else  
34:      {  
35:        LevelTravel(node->left, level-1, hasNextLevel, result);  
36:        LevelTravel(node->right, level-1, hasNextLevel, result);  
37:      }  
38:    }  

Update 1/12/2014 
BFS的code太啰嗦，用两个循环虽然看着清楚了，但是code不够漂亮，改一下。

1:    vector<vector<int> > levelOrder(TreeNode *root) {  
2:      vector<vector<int> > result;  
3:      if(root == NULL) return result;  
4:      queue<TreeNode*> nodeQ;  
5:      nodeQ.push(root);  
6:      int nextLevelCnt=0, currentLevelCnt=1;  
7:      vector<int> layer;  
8:      int visitedCnt=0;  
9:      while(nodeQ.size() != 0)  
10:      {  
11:        TreeNode* node = nodeQ.front();  
12:        nodeQ.pop();  
13:        visitedCnt++;  
14:        layer.push_back(node->val);  
15:        if(node->left != NULL)  
16:        {  
17:          nodeQ.push(node->left);  
18:          nextLevelCnt++;  
19:        }  
20:        if(node->right != NULL)  
21:        {  
22:          nodeQ.push(node->right);  
23:          nextLevelCnt++;  
24:        }  
25:        if(visitedCnt == currentLevelCnt)  
26:        {  
27:          visitedCnt =0;  
28:          currentLevelCnt = nextLevelCnt;  
29:          nextLevelCnt=0;  
30:          result.push_back(layer);  
31:          layer.clear();  
32:        }  
33:      }  
34:      return result;  
35:    }  

[LeetCode] Binary Tree Inorder Traversal Solution

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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

[Thoughts]
For recursion version, it's very easy to write.

But for iterative version, we need a stack to help.


[Code]
Recursion version

1:    vector<int> inorderTraversal(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<int> result;  
5:      inorderTra(root, result);  
6:      return result;  
7:    }  
8:    void inorderTra(TreeNode* node, vector<int> &result)  
9:    {  
10:      if(node == NULL)  
11:      {        
12:        return;  
13:      }  
14:      inorderTra(node->left, result);  
15:      result.push_back(node->val);      
16:      inorderTra(node->right, result);  
17:    }  

Iteration version

1:    vector<int> inorderTraversal(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<TreeNode*> sta;  
5:      vector<int> result;  
6:      if(root == NULL) return result;  
7:      TreeNode* node =root;  
8:      while(sta.size()>0 || node!=NULL)  
9:      {  
10:        while(node!=NULL)  
11:        {  
12:          sta.push_back(node);  
13:          node = node->left;  
14:        }  
15:        node= sta.back();  
16:        sta.pop_back();  
17:        result.push_back(node->val);  
18:        node =node->right;  
19:      }  
20:      return result;  
21:    }  

[LeetCode] Balanced Binary Tree Solution

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.

» Solve this problem

[Thoughts]
recursion. For each node, check the left branch and right branch.

[Code]

1:    bool isBalanced(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(root == NULL) return true;  
5:      int val = GetBalance(root);  
6:      if(val ==-1) return false;  
7:      return true;      
8:    }    
9:    int GetBalance(TreeNode* node)  
10:    {  
11:      if(node == NULL)  
12:        return 0;  
13:      int left = GetBalance(node->left);  
14:      if(left == -1) return -1;  
15:      int right = GetBalance(node->right);  
16:      if(right == -1) return -1;  
17:      if(left-right>1 || right-left>1)  
18:        return -1;  
19:      return left>right? left+1:right+1;  
20:    }   

[LeetCode] Best Time to Buy and Sell Stock III Solution

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

» Solve this problem

[Thoughts]
One dimensional dynamic planning.
Given an i, split the whole array into two parts:
[0,i] and [i+1, n], it generates two max value based on i, Max(0,i) and Max(i+1,n)
So, we can define the transformation function as:
Maxprofix = max(Max(0,i) + Max(i+1, n))  0<=i<n
Pre-processing Max(0,i) might be easy, but I didn't figure an efficient way to generate Max(i+1,n) in one pass.

[Code]

1:    int maxProfit(vector<int> &prices) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int index =0;  
5:      int max1, max2;  
6:      int max =0;  
7:      for(int i =0; i< prices.size(); i++)  
8:      {  
9:        max1=SearchMax(prices,0,i);  
10:        max2 = SearchMax(prices,i+1, prices.size()-1);  
11:        if(max < max1+max2)  
12:          max = max1+max2;  
13:      }  
14:      return max;  
15:    }  
16:    int SearchMax(vector<int>& prices, int start, int end)  
17:    {  
18:      int max=0;  
19:      int min=INT_MAX;  
20:      for(int i =start; i<= end; i++)  
21:      {  
22:        if(min> prices[i]) min = prices[i];  
23:        int diff = prices[i] -min;  
24:        if(diff> max)  
25:        {  
26:          max = diff;          
27:        }  
28:      }  
29:      return max;  
30:    }  

Update 03/12/2014
Just see the comments. Looks I didn't post the right code.
Line 6~12 and Line 15~21 can be merged into one pass. But keep it for readability.

1:  int maxProfit(vector<int> &prices) {   
2:       if(prices.size() <= 1) return 0;  
3:       vector<int> maxFromLeft(prices.size(), 0);  
4:       vector<int> maxFromRight(prices.size(), 0);  
5:       int minV = INT_MAX, maxP = INT_MIN;  
6:       for(int i =0; i< prices.size(); i++)  
7:       {  
8:            if(minV > prices[i]) minV = prices[i];  
9:            int temp = prices[i] - minV;  
10:            if(temp > maxP) maxP = temp;  
11:            maxFromLeft[i] = maxP;  
12:       }  
13:       int maxV = INT_MIN;  
14:       maxP = INT_MIN;  
15:       for(int i =prices.size()-1; i>=0; i--)  
16:       {  
17:            if(maxV < prices[i]) maxV = prices[i];  
18:            int temp = maxV - prices[i];  
19:            if(temp > maxP) maxP = temp;  
20:            maxFromRight[i] = maxP;  
21:       }  
22:       int maxProfit = INT_MIN;  
23:       for(int i =0; i< prices.size()-1; i++)  
24:       {  
25:            int sum = maxFromLeft[i] + maxFromRight[i+1];  
26:            if(sum > maxProfit) maxProfit = sum;  
27:       }  
28:       if(maxProfit < maxFromRight[0])  
29:            maxProfit = maxFromRight[0];  
30:       return maxProfit;   
31:  }