Regular Expression match with * and +

This one was from Facebook Seattle Onsite (asked by an Indian guy :)) Given a source string (doesn't contain '*' or '+') and a pattern string (may contain zero or more '+' or '*'). Check if the source matches the pattern. '*' mean the letter before it can appear 0 or more times '+' mean the letter before it can appear 1 or more times ie: aab matches a+b or a*b abc doesn't match ad+bc but matches ad*bc.

#include "stdafx.h"
#include "assert.h"

 bool isMatch(const char *s, const char *p) {
     if (!*p) return !*s;
     
     if (*(p+1) != '*' && *(p+1) != '+') 
         return (*s == *p) && isMatch(s+1, p+1);

      if ( *(p+1) == '+') {
          if (*s != *p)  return false;
          ++s;
      }

      while( *s == *p) {
           if (isMatch(s, p+2)) return true;
           s++;
       }
       
       return isMatch(s, p+2);
 }

int _tmain(int argc, _TCHAR* argv[])
{
    assert(isMatch("", ""));
    assert(!isMatch("a", ""));
    assert(!isMatch("aa", ""));
    assert(!isMatch("aaa", ""));
    assert(!isMatch("", "a"));
    assert(!isMatch("", "aa"));
    assert(!isMatch("", "aaa"));
    assert(!isMatch("a", "aa"));
    assert(!isMatch("aa", "a"));    
    assert(isMatch("a", "a"));
    assert(isMatch("ab", "ab"));
    assert(isMatch("a", "a*"));
    assert(isMatch("a", "a+"));
    assert(isMatch("aa", "a*"));
    assert(isMatch("aa", "a+"));
    assert(isMatch("aaa", "a+"));
    assert(isMatch("aaa", "a+"));
    assert(!isMatch("aab", "a+"));
    assert(!isMatch("aab", "a+"));
    assert(isMatch("aab", "a*b"));
    assert(isMatch("aab", "a+b"));
    assert(isMatch("aab", "a*b+"));
    assert(isMatch("aab", "a+b*"));
    assert(isMatch("aabbc", "a+b+c"));
    assert(isMatch("aabbc", "a+b*c"));
    assert(isMatch("aabbc", "aa*b*c"));
    assert(isMatch("aabbc", "aa+bb+c"));
 return 0;
}

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

    * The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

// Refer to : http://en.wikipedia.org/wiki/Longest_increasing_subsequence

class Solution {
    int insert(vector<int> &A, int lastIndex, int target) {
        int i = 0, j = lastIndex;
        while(i <= j) {
            int m = (i+j)/2;
            if (A[m] > target) 
               j = m - 1;
            else 
               i = m + 1;
        }
        A[i] = target;
        return i;
    }
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        int n = nums.size();
        if (n < 2) return n;
        
        vector<int> M(n, 0);
        int longest = 0;
        M[0] = nums[0];
        
        for(int i =1; i < n; i++) 
            longest = max(longest, insert(M, longest, nums[i]));
        
        return longest+1;
    }
};

Reverse Linked List

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

ListNode *reverse(ListNode *head) {
        if (!head) return head;
        
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode *p = &dummy;
        while(head->next) {
            ListNode *T = head->next;
            head->next = T->next;
            T->next = p->next;
            p->next = T; 
        }
        
        return dummy.next;
    }

 ListNode *reverse(ListNode *head) {
        ListNode *prev = NULL;
        while(head) {
            ListNode* T = head->next;
            head->next = prev;
            prev = head;
            head = T;
        }
        
        return prev;
    }

Convert Sorted List to Binary Search Tree

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

class Solution {
    TreeNode *sortedListToBST(ListNode *&head, int start, int end)
    {
        if (start > end) return NULL;
        int m = (start + end)/2;
        
        TreeNode *left = sortedListToBST(head, start, m-1);
        TreeNode *root = new TreeNode(head->val);
        root->left = left;
        head = head->next;
        root->right = sortedListToBST(head, m+1, end);
        return root;   
    }
        
public:
   
      TreeNode *sortedListToBST(ListNode *head) {
        int count = 0;
        ListNode *p = head;
        while(p) {
            count++;
            p = p->next;
        }
        
        return sortedListToBST(head, 0, count-1);
    }
};

 TreeNode *sortedListToBST(ListNode *head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        
        ListNode *p = head;
        ListNode *pp = head->next;
        
        while(pp->next && pp->next->next) {
            p = p->next;
            pp = pp->next->next;
        }
        
        pp = p->next;
        p->next = NULL;
        TreeNode *root = new TreeNode(pp->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(pp->next);
        return root;
    }

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.

Example

[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 {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
public:
    int searchInsert(vector<int> &A, int target) {
        int l = 0, r = A.size()-1;
        while(l <= r) {
            int m = (l+r)/2;
            if (A[m] < target)
               l = m + 1;
            else 
               r = m - 1;
        }
        return l;
    }
};

Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

          20

       /        \

    8           22

  /     \

4       12

class Solution {
    void pushLeft(stack<TreeNode *> &st, TreeNode *root, int k1) {
        while(root) {
            st.push(root);
            if (root->val < k1) break;
            
            root = root->left;
        }
    }
public:
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        stack<TreeNode *> st;
        vector<int> output;
        
        pushLeft(st, root, k1);
        
        while(st.size() > 0) {
            TreeNode *t = st.top();
            st.pop();
            
            if (t->val >= k1 && t->val <= k2)
                output.push_back(t->val);
            
            if (t->val <= k2) 
               pushLeft(st, t->right, k1);
        }
        
        return output;
    }
};

Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array:

    - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

class Solution {
    void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    void reverse(vector<int> &num, int i, int j) {
        while(i < j) {
           swap(num, i, j);        
           i++;
           j--;
        }
    }
     
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int i = findMinPoint(nums);
        if (i == 0) return;
        reverse(nums, 0, i-1);
        reverse(nums, i, nums.size()-1);
        reverse(nums, 0, nums.size()-1);
    }
};

class Solution {
     void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int k = findMinPoint(nums);
        if (k == 0) return;
        
        int n = nums.size();
        int i = 0;
        int L = n;
        while(k > 0) {
            while(i+k <n) {
               swap(nums, i, i+k);
               i++;
            }
            
            int t = k;
            k = L%k? k - L%k : 0;
            L = t;
        }
    }
};

Reverse Linked List II

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array:

    - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;
        int i = 1;
        
        ListNode *p = &dummy;
        
        while(i < m && p) {
            p = p->next; 
            i++;
        }
        
        head = p;
        ListNode *tail = p->next;
        
        while(i < n) {
            ListNode *next = tail->next;
            tail->next = next->next;
            next->next = head->next;
            head->next = next; 
            i++;
        }
    
        return dummy.next;    
    }
};

Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = "aabcc" s2 = "dbbca"

    - When s3 = "aadbbcbcac", return true.

    - When s3 = "aadbbbaccc", return false.

Challenge

O(n^2) time or better

class Solution {
    bool helper(string s1, string s2, string s3)
    {
        if (s1.length() == 0) return s2 == s3;
        if (s2.length() == 0) return s1 == s3;
        
        return (s3[0] == s1[0] && helper(s1.substr(1), s2, s3.substr(1))) ||
                (s3[0] == s2[0] && helper(s1, s2.substr(1), s3.substr(1)));
    }
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        char map[256] = {0};
        if (s1.length() + s2.length() != s3.length()) return false;
        for(char c: s1) map[c]++;
        for(char c: s2) map[c]++;
        for(char c: s3) {
            map[c]--;
            if (map[c] < 0) return false;
        }
        return helper(s1, s2, s3);
    }
};

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (k != m + n) return false;
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        
        vector<vector<bool>> map(m+1, vector<bool>(n+1, false));
        map[0][0] = true;
        
        for(int i =1;i<=m; i++) 
            map[i][0] = s1[i-1]== s3[i-1] && map[i-1][0];
        for(int j =1;j<=n; j++) 
            map[0][j] = s2[j-1]== s3[j-1]&& map[0][j-1];            
            
        
        for (int i = 1; i <= m; i++)
           for (int j = 1; j <= n; j++)
               map[i][j]= (s3[i+j-1]==s1[i-1] && map[i-1][j]) ||(s3[i+j-1]==s2[j-1] && map[i][j-1]);
           
        return map[m][n];
    }
};

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (k != m + n) return false;
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        
        vector<bool> map(n+1, false);
   
        map[0] = 1;
        for(int i = 1; i <=n; i++) 
            map[i] = map[i-1] && s2[i-1] == s3[i-1];
        
        for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               map[j]= (s3[i+j-1]==s1[i-1] && map[j]) ||(s3[i+j-1]==s2[j-1] && map[j-1]);
           }
        }
           
        return map[n];
    }
};

Product of Array Exclude Itself

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B without divide operation.

Example

For A=[1, 2, 3], B is [6, 3, 2]

   vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n);
        
        long long left =1;
        for(int i = 0; i < n; i++) {
            output[i] = left; 
            left *= nums[i];
        }
        
        long long right = nums[n-1];
        for(int i = n-2; i >=0; i--){ 
            output[i] *= right; 
            right *= nums[i];
        }
        
        return output;
    }

vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n, 1);
        
        long long left =1, right = 1;
        for(int i = 0; i < n; i++) {
            output[i] *= left; 
            left *= nums[i];
            
            output[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        
        return output;
    }

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.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

class Solution{
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode * deleteDuplicates(ListNode *head) {
        ListNode dummy(0);
        
        dummy.next = head;
        ListNode *p = &dummy;
        
        while(p->next && p->next->next) {
            if (p->next->val == p->next->next->val) {
                int val = p->next->val;
                while(p->next && p->next->val == val) {
                    ListNode *next = p->next->next;
                    delete p->next;
                    p->next = next;
                }
            }
            else
               p = p->next;
        }
        return dummy.next;
    }
};

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

    * Integers in each row are sorted from left to right.

    * Integers in each column are sorted from up to bottom.

    * No duplicate integers in each row or column.

Example

Consider the following matrix:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

Given target = 3, return 2.

Challenge

O(m+n) time and O(1) extra space

class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        if  (n==0) return false;
        int count = 0;
        
        int i = 0, j = n-1;
        while(i < m && j >= 0) {
            if (matrix[i][j] == target) {
                count++;
                i++;j--;
            }
            else if (matrix[i][j] > target)
               j--;
            else 
               i++;
        }
        
        return count;
    }
};

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

    * Integers in each row are sorted from left to right.

    * The first integer of each row is greater than the last integer of the previous row.

Example

Consider the following matrix:

[

    [1, 3, 5, 7],

    [10, 11, 16, 20],

    [23, 30, 34, 50]

]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

class Solution {
public:
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        if  (n==0) return false;
        
        int i = 0, j = m-1;
        while(i < j) {
            int k = (i + j + 1)/2;
            if (matrix[k][0] == target)  return true;
            if(matrix[k][0] > target) j = k - 1;
            else i = k; 
        }
        
        if (matrix[i][n-1] < target) return false;
        
        int row = i;
        i = 0, j = n-1;
        while(i <= j) {
            int m = (i+j)/2;
            if (matrix[row][m] == target) return true;
            if (matrix[row][m] > target) j = m-1;
            else i = m+1;
        }
        return false;
    }
};

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

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

class Solution {
    vector<TreeNode *> generateTrees(int start, int end) {
        vector<TreeNode *> output;
        if (start > end) {
            output.push_back(NULL);
            return output;
        }
        
        for(int i = start; i <=end; i++) {
            vector<TreeNode *> leftSubTrees = generateTrees(start, i-1);
            vector<TreeNode *> rightSubTrees = generateTrees(i+1, end);
            for(TreeNode *left : leftSubTrees)
                for(TreeNode *right : rightSubTrees) {
                     TreeNode *root = new TreeNode(i);
                     root->left = left;
                     root->right = right;
                     output.push_back(root);
                }
             
        }
        return output;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        return generateTrees(1, n);
    }
};

class Solution {
    TreeNode * clone(TreeNode *root, int adjust) {
         TreeNode *newRoot = NULL;
         
         if (root) {
             newRoot = new TreeNode(root->val + adjust);
             newRoot->left = clone(root->left, adjust);
             newRoot->right = clone(root->right, adjust);
         }
         
         return newRoot;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        vector<vector<TreeNode *>> Gens(n+1);
        Gens[0].push_back(NULL);
        
        for(int i = 1; i <=n; i++) {
            for(int j = 1; j <= i; j++) {
                    for(TreeNode *left : Gens[j-1])
                        for(TreeNode *right : Gens[i-j]) {
                            TreeNode *root = new TreeNode(j);
                            root->left = clone(left, 0);
                            root->right = clone(right, j);
                            Gens[i].push_back(root);
                        }
            }
        }
        
        return Gens[n];
    }
};

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

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

 
class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
       if (n < 2) return 1;
       int ret = 0;
       for(int i = 0; i <n; i++)
           ret += numTrees(i)*numTrees(n-i-1);
       return ret;
    }
};



 
class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
        vector<int> count(n+1, 0);
        count[0] = 1;
        for(int i = 1; i <= n; i++) 
            for(int j = 0; j <i; j++)
                count[i] += count[j]*count[i-j-1]; 
        
        return count[n];
    }
};

Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note

m and n will be at most 100.

Example

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         vector<vector<int>> map(m, vector<int>(n, 0));
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[i][j] = 1;
              else if (i == m-1) // special on last row
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i][j+1];
              else if (j == n-1) // special on last column
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i+1][j];
              else
                 map[i][j] = (obstacleGrid[i][j] == 1)? 0:map[i+1][j]+ map[i][j+1];
        
         return map[0][0];
    }
};

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
         vector<int> map(n, 1);
         
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[j] = 1;
              else if (i == m-1) // special on last row
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j+1];
              else if (j == n-1) // special on last column
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j];
              else
                 map[j] = (obstacleGrid[i][j] == 1)? 0:map[j]+ map[j+1];
        
         return map[0];
    }
};

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note

m and n will be at most 100.

Example

1,1	1,2	1,3	1,4	1,5	1,6	1,7
2,1
3,1						3,7

Above is a 3 x 7 grid. How many possible unique paths are there

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        vector<vector<int>> UP(m, vector<int>(n, 1));
        
        for(int i = m-2; i >= 0; i--)
          for(int j = n-2; j >= 0; j--)
              UP[i][j] = UP[i+1][j] + UP[i][j + 1];
        return UP[0][0];
        
    }
};

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        vector<int> UP(n, 1);
        
        for(int i = m-2; i >= 0; i--)
          for(int j = n-2; j >= 0; j--)
              UP[j] = UP[j] + UP[j + 1];
        return UP[0];
        
    }
};

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.

Example

An example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

class Solution {
public:
    
   bool isValidBST(TreeNode *root, TreeNode *&prev)
   {
       if (!root) return true;
       if (!isValidBST(root->left, prev)) return false;
       if (prev && prev->val >= root->val) return false;
       prev = root;
       if (!isValidBST(root->right, prev)) return false;
       return true;
   }
  
   bool isValidBST(TreeNode *root) {
        TreeNode *prev = NULL;
        return isValidBST(root, prev);
   }
};

 
class Solution {
public:
   bool isValidBST(TreeNode *root, long long mn, long long mx)
   {
       if (!root) return true;
       if (root->val <= mn) return false;
       if (root->val >= mx) return false;
       
       return isValidBST(root->left, mn, root->val) &&isValidBST(root->right, root->val, mx);
       
   }
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        return isValidBST(root, (long long)INT_MIN-1, (long long)INT_MAX+1);
    }
};

 
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        pushLeft(root, st); 
        
        TreeNode *prev = NULL;
        while(st.size() > 0)
        {
            root = st.top();
            st.pop();
            if (prev && prev->val >= root->val) return false;
            prev = root;
            pushLeft(root->right, st);
        }
        
        return true;
    }
    void pushLeft(TreeNode *root, stack<TreeNode *> &st)
    {
        while(root)
        {
            st.push(root);
            root = root->left;
        }
    }
};

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        
        TreeNode *prev = NULL;
        while(!st.empty() || root)
        {
            if (!root)
            {
                root =  st.top();
                st.pop();
                
                if (prev && prev->val >= root->val) return false;
                prev = root;
                root = root->right;
            }
            else {
                st.push(root);
               root = root->left;
            }
        }
        return true;
    }
};