Find the Minimum in a Sorted but Rotated Array

[Question]

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element.
You may assume no duplicate exists in the array.

[Analysis]

Simple solution is to experiment linear search and the time complexity is O(N).

It is noticeable that the pivot at position i must meet the following condition: A[i-1]>A[i] and A[i]<A[i+1] (if rotation happened). For example, "0" in above array. So we can apply binary search in this case. Time complexity is O(lg N).

A follow-up question can be, find a given value in such array. The first step will be find the pivot. Then the second step is to apply binary search again for the given value. 

[Solution]

int findMin(vector<int> &num) {
    if (num.size()==0) return 0;
    if (num.size()==1 || num[0]<num.back()) return num[0];
    if (num.size()==2) return min (num[0], num[1]);

    int mid = num.size()/2;
    if (num[mid]<num[mid+1] && num[mid]<num[mid-1]) return num[mid];
 

    vector<int> split;
    if (num[mid]>num.back()) {
        split = vector<int> (num.begin()+mid, num.end());
    } else {
        split = vector<int> (num.begin(), num.begin()+mid);
    }
    

    return findMin(split);
}

Palindrome Partitioning - LeetCode 131

[Question]

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.

[Analysis]

The minimum cut of the string S at position i is,
     MinimumCuts(i) = MinimumCuts[j-1]+1, while  S[j] ...S[i] is the longest palindrome sub-string ending at position i.  (j<i).

Use a table to calculate the palindrome sub-string at each position. C[i,j] is true when S[j,i]  is a palindrome. C[i,j] is true, when C[i-1, j+1] is true && S[i] == S[j].

Total time complex is O(N^2).

[Solution]

    int minCut(string s) {
        if (s.size()==0) return 0;
     
        int len = s.size();
     
        int dp[len+1];
        for (int i=0; i<len+1; i++)
            dp[i] = i;

        bool c[len+1][len+1];
        for (int i=0; i<=len; i++)
            for (int j=0; j<=len; j++)
            c[i][j] = false;
         
        c[0][0]=true;
        for (int i=1; i<len+1; i++)
            for (int j=i; j>0; j--) {
                if (s[i-1]==s[j-1] && (i-j<2 || c[i-1][j+1]==true)) {
                    c[i][j] = true;
                    dp[i] = min(dp[i], dp[j-1]+1);
                }
            }
     
        return dp[len]-1;
    }

Recover Two Swapped Nodes in BST

[Question]

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

[Analysis]
In-order traversal will reveal the swapped elements. If output the traversal result to an array, the space will be O(N). If using recursive calls, the space will be O(lg N). An in-place traversal will do it.

[Solution]
/////////////////
//Solution 1: Using in-place space
//
void inOrderTraversal(TreeNode* root) {
    TreeNode* pre = NULL;
    TreeNode* p = root;
    while(p! = NULL) {
            while (p->left!=NULL && p->left!=pre) {
                     TreeNode * q = p;
                     while (q->right!=NULL) q = q->right;
                     q->right = pre;
                     pre = p;
                     p = p->left;
            }
            cout<<p->val<<endl;
            pre = p;
            p = p->right;
            if (p->left == pre) {
                pre->right = NULL;
            }
    }

}


///////////////
// Solution 2: Recursive using a stack.
//
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

    void recoverTree(TreeNode *root) {

        if (!root) return;
        stack<TreeNode*> st;
        TreeNode* cur=NULL;
        TreeNode* p1=NULL, *p2=NULL;
     
        st.push(root);
     
        while (!st.empty()) {
            while (st.top()->left) {
                st.push(st.top()->left);
            }

            if (!st.empty() && cur && cur->val > st.top()->val) {
                if (!p1) { p1 = cur; p2 = st.top();}
                else p2 = st.top();
            }

            while (!st.empty()&&st.top()->right==NULL) {
                cur = st.top();
                st.pop();
                if (!st.empty() && cur && cur->val > st.top()->val) {
                    if (!p1) { p1 = cur; p2 = st.top();}
                    else p2 = st.top();
                }
            }
         
            if (!st.empty()) {
                cur = st.top();
                st.pop();
                st.push(cur->right);
            }
        }
        if (p1 && p2 ) swap( p1->val, p2->val);
    }

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;

    }
};