Sliding Window Maximum -- LeetCode 239

[Question]
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

[Analysis]
There are a few solutions for this question:
1. For each sliding window, scan and find the maximum number. The time complexity is O(K * (N-K)).
2. For each sliding window. maintain a max heap -- pop() and push() while sliding window moves. The time complexity is ( K + logK * (N-K) );
3. Using the "Max-Queue" (the maximum/minimum value of queue) to track the possible maximum in the sliding window. The time complexity is O(N);

The cold below is for the 3rd solution. A STL "list" is used as a Deque. A STL "queue" (std::queue<int, std::list<int>>) can be used also as long as the underlying container is linked list based, to reduce the cost of memory copying.

[Solution]
class Solution {
    list<int> deque;
    void deque_append(int a) {
        for (int k=deque.size(); k>0; k--) {
            if (deque.back()<a) deque.pop_back();
        }
        deque.push_back(a);
    }
public:  
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size()==0) return vector<int>();
        vector<int> rslt;
       
        for(int i=0; i<k; i++) {
            deque_append(nums[i]);
        }
        rslt.push_back(deque.front());
       
        for (int i=k; i<nums.size(); i++) {
            if (deque.front() == nums[i-k]) deque.pop_front();
            deque_append(nums[i]);
            rslt.push_back(deque.front());           
        }
        return rslt;
    }
};

Lowest Common Ancestor of a Binary Tree -- LeetCode 236

[Question]
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition
[Analysis]
The simple solution is to find a pre-order path to Node A and another pre-order path to Node B. The last Node of common part of the two paths is the LCA. This solution will require extra storage to store path from root to Node A or B. The time complexity is O(N) -- because this is Binary Tree, although three traversals will be needed.

Another solution is to use recursion. The LCA is the lowest visiting node, which either has one target node in left sub tree and the other in right substree, or the visiting node is one of the target node and the other target node is in its sub trees.

A similar question is to find LCA of a Binary Search Tree (BST). Since nodes of BST are placed sequentially, the logic can be simplified using the values of the current node X,  the given Node A and Node B. One regularity that can be used is, in pre-order traversal, the first node X, whose value is between A and B's values is the LCA of A and B.

[Solution]
//
// -- LCA of Binary Tree --
//
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root==p || root==q) return root;
       
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right= lowestCommonAncestor(root->right, p, q);
       
        return !left ? right : right ? root : left;
    }

//
//-- LCA of Binary Search Tree --
//
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root==NULL|| root==p || root==q) return root;
        if (min(p->val,q->val) < root->val && root->val < max( p->val,q->val) )
             return root;
     
        return root->val > p->val ? lowestCommonAncestor(root->left, p, q): lowestCommonAncestor(root->right, p, q);
 
    }
};

Shortest Palindrome -- LeetCode

[Question]

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

[Analysis]
The key is to find the longest palindrome sub-string S', starting from position 0, in S, the solution will be to place the reversed (S - S') in front of S. For example, in "aacecaaa", the longest palindrome sub-string from the beginning is, "aacecaa"; therefore, inserting one "a" is the solution.

The naive way to find the longest sub-string is at O(N^2), in which going through each index of string S and checking whether S[0]...S[i] is a palindrome.

An optimized solution is to apply KMP algorithm. First, reverse S as S" and construct one larger string S+'*'+S" -- '*' serves as a separator. Secondly, apply KMP algorithm and build a table A for the longest repetitive pattern (from the beginning) for the long string. Apparently, the last element of A indicates the length of longest palindrome sub-string of S, starting from index 0.

The time and space complexity both are O(N).

[Solution]

class Solution {
    public:
    void kmpTable(string& p, vector<int>& next) {
        next[0]=0;
        int j=1; int k=0;

        while (j<p.size()) {
            if (p[j]==p[k]) {
                next[j] = k+1;
                j++; k++;
            }
            else {
                if (k!=0) k= next[k-1];
                else ++j;
           }

        }
    }

    string shortestPalindrome(string s) {
        string s1 = s;
        reverse(s1.begin(), s1.end() );
        string str = s+"*"+s1;

        vector<int> v(str.size(), 0);
        kmpTable(str, v);

        string r = s.substr(v.back());
        reverse(r.begin(), r.end());

        return r+s;
    }
};