BST's In-order Traversal, No Recursion, No Stack

[Question]
Make BST in-order traversal without using recursive calls nor stack.

[Analysis]
Morris Traversal.

[Code]
/ *
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> v;
        if (root==NULL) return v;
     
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while (cur!=NULL) {
            if (!cur->left) {
                v.push_back(cur->val);
                cur = cur->right;
            }
            else {
                if (pre && pre->right==cur) {
                    pre->right = NULL;
                    v.push_back(cur->val);
                    cur = cur->right;
                } else {
                    pre = cur->left;
                    while (pre->right!=NULL && pre->right!=cur) {
                        pre = pre->right;
                    }
                    if (pre->right==NULL) {
                        pre->right = cur;
                        cur = cur->left;
                    }
                }
            }
        }
        return v;
     
    }
};

Find Ceiling of a Number in BST

[Question]
A binary search tree is given. Find the ceiling value present in the BST of 
a given key. eg-
                        8
               3              12
           2      6       10    15
                4
key - 13 => 15 
key - 4 =>6 
key - 8 =>10

[Analysis]
Using in-order traversal. The time complexity is O(lgN) on average, O(N) at the worst case.

[Code]

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v): val(v), left(NULL), right(NULL) {};
};

//
// return the pointer when a ceiling is found;
// otherwise, NULL;
//
TreeNode* find_ceiling(TreeNode* root, int target)
{
    if (root==NULL) return NULL;

    if (root->val == target) return root;

    if (root->val > target) {
        TreeNode* temp = find_ceiling( root->left, target );
        return (temp==NULL)? root: temp;
    }

    return find_ceiling( root->right, target );
}

Longest Consecutive Sequence

[Question]

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.

[Analysis]
Each element is a consecutive sequence of length 1. Suppose element A, it can be represented as a sequence [A, A+1). If A+1 is in the array, the sequence that starts from A can be represented as [A, A+2). Repeat the finding process, using a hash table which maps A (the starting value) to the ending value (exclusive) of the sequence.

It is equivalent to use mapping between A and "length of consecutive sequence", as shown in 2nd solution code.

[Solution]
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()<2) return num.size();
     
        int max_len = 1;
        unordered_map<int,int> map;    
        for (auto a: num)
            map[a] = a+1;

        for(auto kv: map) {
            int a = kv.first;
            int next = map[a];
            while (map.find(next)!=map.end()) {
                map[a] = map[next];
                map.erase(next);
                next = map[a];
            }
            max_len = max(map[a]-a, max_len);
        }

        return max_len;
    }
};

//Solution 2nd
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.empty()) return 0;
        int max_len = 1;
   
        unordered_map<int,int> map;  
        for (auto& a: num) map[a] = 1;

        for(auto& kv: map) {
            int a = kv.first;
            int next=a+map[a];
            while (map.count(next)) {
                map[a] += map[next];
                map.erase(next);
                next=a+map[a];
            }
            max_len = max(max_len, map[a]);
        }

        return max_len;
    }
};

Power (X, N)

[Question]
    Calculate Power(X, N).

[Analysis]
   Power(X, N) = Power(X, N/2) * Power(X,N/2) if N is even;
   Power(X, N) = Power(X, N/2) * Power(X,N/2) * X if N is odd;
   There are corner cases, when N is negative or X is negative, to consider.

[Solution]
class Solution {
public:
    double power(double x, int n) {
        if (n==0) return 1;
        if (n==1) return x;    
        double tmp = power(x, n/2);
     
        if ( (n & 0x0001) ==0 )
              return (tmp * tmp);
       else
              return (tmp * tmp * x );      
    }
 
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        bool rev=false, neg=false;
        if (n<0) {
            n= -n;
            rev = true;
        }
     
        if (x<0 && n & 0x0001) {
            x = -x;
            neg = true;
        }
     
        double rslt = power(x, n);
        if (rev) rslt = 1/rslt;
        if (neg) rslt = -rslt;
        return rslt;

    }
};

Best Time to Buy and Sell Stocks III -- Leetcode

[Question]
Say you have an array for which the ith 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).

[Analysis]
It is equivalent to make a partition on the given array, and get the best sum of max profit from each of the two sections. Scanning from left to right, we can get the best profit for buying-and-selling the stock between day 0-th and day i-th. Scanning from the right to left, we can get the best profit for buying-and-selling the stock between day i-th and last day. Add two "best profit" at day i-th, and find out the maximum -- that is the maximum profit we can get if two transactions are allowed.

O(N).

[Solution]


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;

        vector<int> left_profit (prices.size(), 0);
        vector<int> right_profit(prices.size(), 0);
        int high=0, low=0;
   
        low = prices[0];
        for (int i=1; i< prices.size(); i++) {
            low = min(low, prices[i]);
            left_profit[i] = max( prices[i]-low, left_profit[i-1] );
        }
   
        high = prices.back();
        for (int i=prices.size()-2; i>=0; i--) {
            high = max(high, prices[i]);
            right_profit[i] = max( high - prices[i],  right_profit[i+1] );
        }
   
        int max_profit=0;
        for (int i=0; i< prices.size(); i++) {
            int sum = left_profit[i] + right_profit[i];
            max_profit = max(sum, max_profit);
        }
       
        return max_profit;
    }
};

Longest Sub-string without repeating characters

[Question]
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

[Analysis]
Dynamic programming. Define L(i) as, the longest sub-string without repeating characters and ending at index i. Go each L(i) and find the maximum L(i).

[Solution]
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
     
        int* count = new int[s.size()];
        int max_len;
        unordered_map<char, int> char_last_index;
     
        char_last_index[s[0]] = 0;
        max_len = count[0]=1;
        for (int i=1; i<s.size(); i++) {
            if (s[i-1]==s[i]) {
                count[i] = 1;
            }
            else {
                if ( char_last_index.find(s[i]) != char_last_index.end() ){
                    count[i] = min( count[i-1]+1, i-char_last_index[s[i]] );
                }
                else {
                    count[i] = count[i-1]+1;
                }
            }
            char_last_index[s[i]] = i;
            if (count[i]>max_len) {
                max_len = count[i];
            }
        }
        delete count;
        return max_len;
    }
};

Binary Tree Maximum Path Sum

[Question]
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

[Analysis]
Define "maximum path to a given node" (MPN) as, the maximum path starts from a node under and ends at the node. The MPN(node) = max (node.val, node.val+MPN(node.left), node.val+MPN(node.right)).

The maximum path (P) via node N and with the sub-tree rooted by N will be,
         P(N) = (MPN( N.left )>0)?MPN(N.left):0 + N.val + (MPN(N.right)>0)?MPN(N.right):0)

So using post-order traversal, we can get all P(N) and find the maximum P(N).
                 

[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:
    int maxPathSumToNode(TreeNode *root, int& cur_max) {
        if (root==NULL) return 0;
        int leftMax = maxPathSumToNode(root->left, cur_max);
        int rightMax= maxPathSumToNode(root->right, cur_max);
     
        int maxPathToRoot = max( max(leftMax+root->val, rightMax+root->val), root->val );
        int maxPathViaRoot = ((leftMax>0)?leftMax:0)
                            + root->val
                            + ((rightMax>0)?rightMax:0);
     
        if (maxPathViaRoot > cur_max) {
            cur_max = maxPathViaRoot;
        }
        return maxPathToRoot;
    }
 
    int maxPathSum(TreeNode *root) {
        if (root==NULL) return 0;
        int max = root->val;
        maxPathSumToNode( root, max );
        return max;
    }
};