Palindrome Number

/*

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

*/
class Solution {
public:
    bool isPalindrome(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(x<0) return false;
       
        if(x==0) return true;
       
        int maxValue = 2147483647;
       
        int reversed = 0;
       
        int curr = x;
       
        while(curr!=0){
          reversed = reversed*10 + curr%10;
          if(reversed > maxValue) return false;
          curr = curr/10;
        }
       
        if(x==reversed) return true;
        else return false;
    }
};

Longest Palindromic Substring

/*

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

*/
class Solution {
public:
    string findLongestPalindrome(string s, int n){
        int length= s.length();
       
        if(s.substr(n).length()==1) return s.substr(n);
       
        string prep = findLongestPalindrome(s, n+1);
       
        bool isPalindrome;

        for(int i=length-1; i>n && ((i-n+1)>prep.length()); i--){
            isPalindrome = true;
            for(int j=0; (i-j)>=(n+j); j++){
                if(s[n+j]!=s[i-j]){
                    isPalindrome = false;
                    break;
                }
            }
            if(isPalindrome){
                return s.substr(n, i-n+1);
            }
        }
       
        return prep;
    }
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return findLongestPalindrome(s, 0);
    }
};

Pascal's Triangle II

/*

Pascal's Triangle II

Given an index k, return the k^th row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

*/
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        if(rowIndex==0){
            result.push_back(1);
        }
       
        int k=0;
        vector<int> temp;
        while(k < rowIndex){
            temp.clear();
            temp.push_back(1);
            for(int i=1; i<result.size(); i++){
                temp.push_back(result[i]+result[i-1]);
            }
            temp.push_back(1);
            result.clear();
            result = temp;
            k++;
        }
       
        return result;
    }
};

Pascal's Triangle

/*

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

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

*/
class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
        vector<int> line;
        if(numRows <= 0) return result;
       
        if(numRows == 1) {
            line.push_back(1);
            result.push_back(line);
            return result;
        }
       
        result = generate(numRows-1);
        line = result.back();
        vector<int> temp;
        temp.push_back(1);
        int i;
        for(i=1; i<line.size(); i++){
            temp.push_back(line[i]+line[i-1]);
        }
        temp.push_back(1);
        result.push_back(temp);
       
        return result;
    }
};

Validate Binary Search Tree

/*

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

*/
/**
 * 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 isValidBST(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int currValue = -200000;
        TreeNode *node = root;
        stack<TreeNode*> s;
       
        while(node!=NULL || !s.empty()){
            if(node!=NULL){
                s.push(node);
                node = node->left;
            }
            else{
                node = s.top();
                s.pop();
                if(node->val <= currValue) return false;
                currValue = node->val;
                node = node->right;
            }
        }
       
        return true;
    }
};

Maximum Depth of Binary Tree

/*

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

*/
/**
 * 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 maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root==NULL) return 0;
        return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

/*

Construct Binary Tree from Inorder and Postorder Traversal

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

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

*/
/**
 * 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 searchTree(vector<int> inorder, int value){
        for(int i=0; i<inorder.size(); i++){
            if(inorder[i]==value){
                return i;
            }
        }
       
        return -1;
    }
    TreeNode *buildSubTree(vector<int> inorder, vector<int> postorder, int & n, int lowIdx, int highIdx){
        if(lowIdx > highIdx) return NULL;
        if(n<0) return NULL;
       
        TreeNode *node;
        node = new TreeNode(postorder[n]);
        n--;
       
        if(lowIdx == highIdx) return node;
       
        int index = searchTree(inorder, node->val);
       
        node->right = buildSubTree(inorder, postorder, n, index+1, highIdx);
       
        node->left = buildSubTree(inorder, postorder, n, lowIdx, index-1);
       
        return node;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = inorder.size();
        if (size != postorder.size()) return NULL;
        if (size == 0) return NULL;
       
        int n = size-1;
        return buildSubTree(inorder, postorder, n, 0, size-1);
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

/*

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode *BuildSubTree(vector<int> preorder, int & n, map<int,int> hashMap, int lowIdx, int highIdx){
      if(lowIdx>highIdx) return NULL;
      if(n>(preorder.size()-1)) return NULL;
     
      TreeNode *node;
   node = new TreeNode(preorder[n]);
   n++;
      if(lowIdx==highIdx){
         return node;
      }
     
      int index = hashMap[node->val];
     
      node->left = BuildSubTree(preorder, n, hashMap, lowIdx, index-1);
      node->right = BuildSubTree(preorder, n, hashMap, index+1, highIdx);
     
      return node;
    }
   
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = preorder.size();
        if(size==0) return NULL;
        if(size!=inorder.size()) return NULL;
       
        map<int,int> hashMap;
        int i;
        for(i=0;i<size;i++){
          hashMap[inorder[i]] = i;
        }
       
        int n = 0;
        return BuildSubTree(preorder, n, hashMap, 0, size-1);
    }
};

//another solution:
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
     TreeNode *BuildSubTree(vector<int> preorder, map<int,int> hashMap, int lowIdx, int highIdx){
      static int n = 0;
        
      if(lowIdx>highIdx) return NULL;
      //if(n>(preorder.size()-1)) return NULL;
     
      TreeNode *node;
      node = new TreeNode(preorder[n]);
      n++;
     
      if(lowIdx==highIdx){
         return node;
      }
     
      int index = hashMap[node->val];
     
      node->left = BuildSubTree(preorder, hashMap, lowIdx, index-1);
      node->right = BuildSubTree(preorder, hashMap, index+1, highIdx);
     
      return node;
    }
   
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = preorder.size();
        if(size==0) return NULL;
        if(size!=inorder.size()) return NULL;
       
        map<int,int> hashMap;
        int i;
        for(i=0;i<size;i++){
          hashMap[inorder[i]] = i;
        }
       
        return BuildSubTree(preorder, hashMap, 0, size-1);
    }
};

Binary Tree Zigzag Level Order Traversal

/*

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

*/
/**
 * 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> > zigzagLevelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
        vector<int> line;
        if (root==NULL) return result;
        queue<TreeNode*> q;
        int leftValue = 2000;
        TreeNode *leftFirst= new TreeNode(leftValue);
        int rightValue = -2000;
        TreeNode *rightFirst = new TreeNode(rightValue);
       
        TreeNode *curr;
        q.push(root);
        q.push(leftFirst);
        bool fromLeft = true;
       
        while(!q.empty()){
          curr=q.front();
          q.pop();
          if(curr!=leftFirst && curr!=rightFirst){
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(fromLeft) line.push_back(curr->val);
            else line.insert(line.begin(),curr->val);
          }
          if(curr==rightFirst){
            fromLeft = !fromLeft;
            result.push_back(line);
            line.clear();
            if((!q.empty()) && q.front()!=rightFirst && q.front()!=leftFirst){
            q.push(leftFirst);
            }
          }
          if(curr==leftFirst){
            fromLeft = !fromLeft;
            result.push_back(line);
            line.clear();
            if((!q.empty()) && q.front()!=rightFirst && q.front()!=leftFirst){
            q.push(rightFirst);
            }
          }
        }
       
        return result;
    }
};

Symmetric Tree

/*

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

*/
/**
 * 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 isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root==NULL) return true;
        TreeNode *curr = root;
        stack<TreeNode*> s;
        vector<int> num;
        bool reachRoot = false;
        bool isSymetric = true;
        int i = 0;
        int size;
       
        while(curr!=NULL || (!s.empty())){
          if(curr!=NULL){
            s.push(curr);
            curr=curr->left;
          }
          else{
            curr = s.top();
            s.pop();
            if(!reachRoot && curr!=root){
              num.push_back(curr->val);
            }
            if(!reachRoot && curr==root){
              reachRoot = true;
              size = num.size();
            }
            if(reachRoot && curr!=root){
              i++;
              if(size-i<0 || curr->val!=num[size-i]){
               isSymetric = false;
               break;
              }
            }
            curr = curr->right;
          }
        }
       
        if(i!=size){
         isSymetric = false;
        }
       
        return isSymetric;
    }
};

Get All Possible Binary Trees Given n

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void copyTree(TreeNode * & newTree, TreeNode *oldTree){
      if(oldTree==NULL) newTree=NULL;
      else {
        newTree = new TreeNode(oldTree->val);
        copyTree(newTree->left, oldTree->left);
        copyTree(newTree->right, oldTree->right);
      }
    }
    void GetNewTrees(TreeNode *node, TreeNode *curr, int n, vector<TreeNode *> &result){
       if(node==NULL || curr==NULL) return;
      
       TreeNode *newNode;
       TreeNode *newTree;
      
       if(curr==node){
   newNode = new TreeNode(n);
         newNode->left = node;
         //newTree = new TreeNode(0);
         //copyTree(newTree, newNode);
         result.push_back(newNode);
         newNode = new TreeNode(n);
         newNode->right = node;
         //newTree = new TreeNode(0);
         //copyTree(newTree, newNode);
         result.push_back(newNode);
       }
      
       if(curr->left==NULL){
   newNode = new TreeNode(n);
         curr->left = newNode;
         copyTree(newTree, node);
         result.push_back(newTree);
         curr->left = NULL; 
       }
       if(curr->right==NULL){
   newNode = new TreeNode(n);
         curr->right = newNode;
         copyTree(newTree, node);
         result.push_back(newTree);
         curr->right = NULL;
       }
      
       GetNewTrees(node, curr->left, n, result);
       GetNewTrees(node, curr->right, n, result);
    }
   
    void generate(int n, vector<TreeNode *> &result){
       TreeNode *root;
       if(n==1){
         root = new TreeNode(n);
         result.push_back(root);
         return;
       }
      
       generate(n-1, result);
       int size=result.size();
       TreeNode *subTree;
       for(int i=0;i<size;i++){
         subTree = result[i];
         GetNewTrees(subTree, subTree, n, result);
       }
      
       result.erase(result.begin(),result.begin()+size);
    }
   
    vector<TreeNode *> generateTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<TreeNode *> result;
        if(n<1) return result;
        generate(n, result);
    }
  };

Binary Tree Inorder Traversal

/*

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

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void inorderTraversal(TreeNode *node, vector<int> & result){
      if(node==NULL) return;
      inorderTraversal(node->left, result);
      result.push_back(node->val);
      inorderTraversal(node->right, result);
    }
    vector<int> inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        inorderTraversal(root, result);
        return result;
    }
};

//Non-recursive one
/**
 * 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> inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        if(root==NULL) return result;
        stack<TreeNode*> s;
        TreeNode *curr = root;
        while((curr!=NULL) || (!s.empty())){
         if(curr!=NULL){
          s.push(curr);
          curr=curr->left;
         }
         else{
          curr = s.top();
          result.push_back(curr->val);
          s.pop();
          curr=curr->right;
         }
        }
        return result;
    }
};

Binary Tree Level Order Traversal II

/*

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

*/
/**
 * 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> > levelOrderBottom(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int impossibleVal = 20000;
        vector<vector<int>> result;
        if(root==NULL) return result;
        TreeNode *divider = new TreeNode(impossibleVal);
        vector<int> line;
        TreeNode *curr;
        queue<TreeNode*> q;
        q.push(root);
        q.push(divider);
        while(!q.empty()){
         curr = q.front();
         q.pop();
         if(curr->val==impossibleVal){
          if(line.size()!=0) result.insert(result.begin(), line);
          line.clear();
          if((!q.empty()) && q.front()->val!=impossibleVal){
            divider = new TreeNode(impossibleVal);
            q.push(divider);
          }
         }
         else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            line.push_back(curr->val);
         }
        }
        return result;
    }
};

Convert Sorted Array to Binary Search Tree

/*

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *convertBinaryTree(vector<int> num, int low, int upper){
       TreeNode *node;
       int mid = (low+upper)/2;
       node = new TreeNode(num[mid]);
       if(low>upper) return NULL;
       if(low==upper) return node;
       else{
         node->left = convertBinaryTree(num, low, mid-1);
         node->right = convertBinaryTree(num, mid+1, upper);
       }
       return node;
    }
    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        TreeNode *node;
        if(size==0) return NULL;
        int low = 0;
        int upper = size-1;
        return convertBinaryTree(num, low, upper);  
    }
};

Balanced Binary Tree

/*

Balanced Binary Tree

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 every node never differ by more than 1.

*/
/**
 * 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 abs(int value){
      if(value<0) return (-1)*value;
      return value;
    }
    int height(TreeNode *node, bool & isBalance){
       if(node==NULL) return 0;
       if(((abs(height(node->left,isBalance)-height(node->right, isBalance)))>1) && isBalance==true){
          isBalance = false;
       }
       if (isBalance) return max(height(node->left, isBalance), height(node->right, isBalance))+1; 
       else return 0;
    }
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool isBalance = true;
        height(root, isBalance);
        return isBalance;
    }
};

Remove Duplicates from Sorted List II

/*

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode * & head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int,int> hashMap;
        if(head==NULL) return head;
        ListNode *curr = head;
        ListNode *prep;
       
        while(curr!=NULL){
           if(hashMap.find(curr->val)==hashMap.end()){
            hashMap[curr->val]=1;
          } else hashMap[curr->val] = hashMap[curr->val]+1;
          curr = curr->next;
        }
       
        while(head!=NULL && hashMap[head->val]>1){
          head = head->next;
        }
       
        if (head==NULL) return head;
       
        prep = head;
        curr = head->next;
       
        while(curr!=NULL){
          if(hashMap[curr->val]==1){
            prep = curr;
            curr = curr->next;
            } else {
              curr = curr->next;
              prep->next = curr;
            }    
        }
       
        return head;
    }
};

Remove Duplicates from Sorted List

/*

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode * & head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int,int> hashMap;
        if(head==NULL) return head;
       
        ListNode *prep = head;
        ListNode *curr = head->next;
        hashMap[prep->val]=1;
        while(curr!=NULL){
          if(hashMap.find(curr->val)==hashMap.end()){
            hashMap[curr->val]=1;
            prep = curr;
            curr = curr->next;
            } else {
              curr = curr->next;
              prep->next = curr;
            }    
        }
        return head;
    }
};

Plus One

/*

Plus One

Given a number represented as an array of digits, plus one to the number.

*/
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = digits.size();
        if(size==0) {
          digits.push_back(1);
          return digits;
        }
       
        bool plus = false;
        vector<int>::reverse_iterator rit = digits.rbegin();
        *rit = *rit+1;
       
        if(*rit==10) {
           *rit = 0;
           plus = true;
        }
       
        rit++;
        
        while(rit!=digits.rend()&&plus){
          *rit = *rit+1;
          if(*rit==10){
           *rit = 0;
           plus = true;
          } else{
            plus = false;
          }
          rit++;
        }
       
        if(plus) digits.insert(digits.begin(), 1);
       
        return digits;
    }
};

Best Time to Buy and Sell Stock II

/*

Best Time to Buy and Sell Stock II

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

*/
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      int size = prices.size();
      if (size<2) return 0;
      int start = 0;
      int end = 0;
      int prep = 0;
      int curr = prep+1;
      int result = 0;
      if (prices.at(prep)<prices.at(curr)){
        start = prep;
        end = curr;
      }
      while(curr<size){
         while(curr<size&&prices.at(prep)<prices.at(curr)){
           prep++;
           curr++;
         }
         end = prep;
         if(end>start && prices.at(end)>prices.at(start))
         result = prices.at(end)-prices.at(start)+result;
        
         while(curr<size&&prices.at(prep)>=prices.at(curr)){
           prep++;
           curr++;
         }
         start = prep;
      }
     
      return result; 
    }
};

Populating Next Right Pointers in Each Node II

/*

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

*/
/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int const impossibleValue = 50000;
        if(root==NULL) return;
        TreeLinkNode* divider= new TreeLinkNode(impossibleValue);
        queue<TreeLinkNode*> q;
        q.push(root);
        q.push(divider);
       
        TreeLinkNode* curr;
        TreeLinkNode* next;
        while(!q.empty()){
          curr = q.front();
          q.pop();
          if(!q.empty()) {
          next = q.front();
          if(curr->val==impossibleValue&&next->val!=impossibleValue) {
              divider= new TreeLinkNode(impossibleValue);
              q.push(divider);
          }
          if(curr->val!=impossibleValue){
             if(curr->left!=NULL) q.push(curr->left);
             if(curr->right!=NULL) q.push(curr->right);
          }
          if(next->val!=impossibleValue) curr->next = next;
          }
        }
    }
};

Populating Next Right Pointers in Each Node

/*
Populating Next Right Pointers in Each Node
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

*/
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  bool visited;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL), visited(false) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root==NULL) return;
        root->next = NULL;
        TreeLinkNode *leftMost;
        leftMost = root;
        TreeLinkNode *node;
        node = root;
        while(leftMost!=NULL && node!=NULL){
           if(node->left!=NULL && node->right!=NULL){
              node->left->next = node->right;
              if(node->next!=NULL)
              node->right->next = node->next->left;
           }
           if(node->next!=NULL) node=node->next;
           else {
              leftMost = leftMost->left;
              node = leftMost;
           }
        }
    }
};

Path Sum II

/*

Path Sum II

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

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void findSum(TreeNode *node, int currSum, int const sum, bool &found, vector<int> path, vector<vector<int>> &result){
       if(node==NULL) return ;
      
       currSum = currSum+node->val;
       path.push_back(node->val);
       if(sum==currSum&&node->left==NULL&&node->right==NULL){
          found = true;
          result.push_back(path);
       }
       findSum(node->left,currSum,sum,found,path,result);
       findSum(node->right,currSum,sum,found,path,result);
    }
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int currSum = 0;
        bool found = false;
        vector<int> path;
        vector<vector<int>> result;
        findSum(root,currSum,sum,found,path,result);
        return result;
    }
};

Path Sum

/*

Path Sum

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

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void findSum(TreeNode *node, int currSum, int const sum, bool &found){
       if(node==NULL) return ;
      
       currSum = currSum+node->val;
       if(found==false&&sum==currSum&&node->left==NULL&&node->right==NULL){
          found = true;
          return;
       }
       findSum(node->left,currSum,sum,found);
       findSum(node->right,currSum,sum,found);
    }
    bool hasPathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int currSum = 0;
        bool found = false;
        findSum(root,currSum,sum,found);
        return found;
    }
};

Minimum Depth of Binary Tree

/*

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

*/
/**
 * 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 minDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root==NULL) return 0;
        if(root->left==NULL && root->right==NULL) return 1;
        if (root->left==NULL) return minDepth(root->right)+1;
        else if (root->right==NULL) return minDepth(root->left)+1;
        else return min(minDepth(root->left)+1,minDepth(root->right)+1);
    }
};

Search Insert Position

/*

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

*/
class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return 0;
        if(target <= A[0]) return 0;
        if(target == A[n-1]) return n-1;
        if(target > A[n-1]) return n;
       
        int lowIdx = 0;
        int highIdx = n-1;
        int mid = (lowIdx+highIdx)/2;
        while(lowIdx!=(highIdx-1) && target!=A[mid]){
           if(target<A[mid]){
             highIdx = mid;
           } else lowIdx = mid;
           mid = (lowIdx+highIdx)/2;
        }
        if(target==A[mid]) return mid;
        else return lowIdx+1;
    }
};

Substring with Concatenation of All Words

/*

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
--O(n) not optimized

*/
class Solution {
public:
    vector<string>::iterator findWord(vector<string> L, string input){
      vector<string>::iterator it;
      for(it=L.begin();it<L.end();it++){
        if(*it==input){
          return it;
        }
      }
      return L.end();
    }
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        int numOfWord = L.size();
        if(numOfWord==0) return result;
        int wordSize = L.at(0).length();
        int pos = 0;
        int size = S.length();
        int currStart;
        vector<string>::iterator found;
        vector<string> temp;
  bool wordExist = false;
        while(pos<size-numOfWord*wordSize+1){
          temp.clear();
          temp.insert(temp.begin(),L.begin(),L.end());
          currStart = pos;
          while(temp.size()!=0 && currStart<size-wordSize+1){
            //found = findWord(L, S.substr(currStart,wordSize));
   wordExist = false;
   for(found=temp.begin();found<temp.end();found++){
    if(found!=temp.end()&&*found==S.substr(currStart,wordSize)){
     temp.erase(found);
     wordExist = true;
     break;
    }
   }
            if(wordExist){
            currStart = currStart+wordSize;
            }
   else break;
          }
          if(temp.size()==0){
           result.push_back(pos);
          }
          pos++;
        }
        return result;
    }
};

3Sum Closest

/*

3Sum Closest

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).

*/
class Solution {
public:
    int abs(int value){
      if(value<0) return (-1)*value;
      return value;
    }
    int distance(int src, int target){
      return abs(src-target);
    }
    int getClosest(vector<int> num, int end, int target){
        if(end==2) return num.at(2)+num.at(1)+num.at(0);
        int result;
        result = getClosest(num,end-1,target);
        int i,j;
        int sum;
        for(i=0;i<end;i++){
          for(j=0;j<end&&j!=i;j++){
             sum = num.at(i)+num.at(j)+num.at(end);
             if (distance(sum, target)<distance(result, target)){
               result = sum;
             }
          }
        }
        return result;
    }
    int threeSumClosest(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size<3) return 0;
        return getClosest(num, size-1, target);
    }
};

Sum Root to Leaf Numbers

/*

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void getSum(TreeNode *curr, int pathSum, int & sum){
       if(curr == NULL){
          return;
       }
       pathSum = pathSum*10 + curr->val;
       if(curr->left==NULL && curr->right==NULL) sum = sum + pathSum;
       getSum(curr->left, pathSum, sum);
       getSum(curr->right, pathSum, sum);
    }
   
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int pathSum = 0;
        int sum = 0;
        getSum(root,pathSum,sum);
        return sum;
    }
};

Longest Consecutive Sequence (Incomplete)

/*

Longest Consecutive SequenceFeb 14

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.   */

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if (size==0) return 0;
       
        int const MAX = 4000;
        vector<bool> bitMap;
        int i;
       
        for(i=0; i<MAX; i++){
            bitMap.push_back(false);
        }
       
        for(i=0; i<size; i++){
            //--todo how to deal with overflow
            if(num.at(i)>MAX) return 0;
            bitMap.at(2000+num.at(i)) = true;
        }
       
        int result = 0;
        int currentLength;
        i = 0;
        while(i<MAX){
            currentLength = 0;
            while(bitMap.at(i)==true && i<MAX){
                currentLength++;
                i++;
            }
            if(currentLength > result) result = currentLength;
            i++;
        }
       
        return result;
    }
};

First Missing Positive

/*

First Missing PositiveMar 8 '12

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

*/
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int const MAX = 9000;
        //parameter check
        if(n<0) return 0;
        //bounary check
        if(n==0) return 1;
       
        vector<int> bitMap;
        int i;
        for(i=0; i<MAX; i++){
            bitMap.push_back(0);
        }
       
        for(i=0; i<n; i++){
            if(A[i] > 0) {
                bitMap.at(A[i]) = 1;
            }
        }
       
        for(i=1; i<MAX; i++){
            if(bitMap.at(i) == 0) return i;
        }
       
        return 0;    
    }
};