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;
    }
};

The Longest Substring without repeating characters -- LeetCode

[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]
Assume T[i] is the length of longest sub-string, without repeating characters, ending at i, T[0] = 1.
T[i+1]  = min(  T[i]+1,     //when s[i+1] does not appear in last T[i] characters,
                          the distance between the previous appearance of s[i+1] and s[i+1] );

When scanning through, use a map to track the last appearance (index) of each character. The time complexity is O(N).

[Solution]
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size()<2) return s.size();
       
        int len =0;
        vector<int> t(s.size(), 0);
        unordered_map<char, int> c_map;
        t[0] = 1;
        c_map[s[0]] = 0;
       
        for (int i=1; i<s.size(); i++) {
            int dist = (c_map.find(s[i])!=c_map.end())? i-c_map[s[i]] : 0;
            c_map[s[i]] = i;
           
            if (dist==0) t[i]=t[i-1] +1;
            else
                t[i] = min (dist, t[i-1]+1);
               
            len = max (len, t[i]);
        }

        return len;
    }
};

Generate Parenthesis -- LeetCode

[Question]
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

Given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

 

[Analysis]
Generate all combination using recursion. Simply insert "(" as many as possible first, then try to insert ")" as alternative path. When n = 3, the recursion will look like:
  ((()))
  (()())
  (())()
  ()(())
  ()()()
--> recursion depth -->

[Solution]
class Solution {
public:
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    vector<string> generateParenthesis(int n) {
        // Write your code here
        vector<string> res;
        string s;
        helper(s, res, 0, 0, n);
        return res;
    }
    void helper(string s, vector<string> &res, int l, int r,int n){
        if(r==n){
            res.push_back(s);
        }
        else if(l==n){
            helper(s+')', res, l, r+1,n);
        }
        else{
            helper(s+'(', res, l+1, r, n);
            if(l>r)
                helper(s+')',res, l, r+1, n);

        }
    }
};

Surrounded Regions -- LintCode

[Question]
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O''s into 'X''s in that surrounded region.

Example

X X X X
X O O X
X X O X
X O X X

After capture all regions surrounded by 'X', the board should be:

X X X X
X X X X
X X X X
X O X X

[Analysis]
Based on the given example, the 'O's on boundaries of board are not considered as surrounded elements. Therefore, rule out all 'O's on the boundaries and all 'O's adjacent to those, the rest of 'O's will be turned into 'X' -- using BFS.


[Solution]
class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void markNeighbours(pair<int, int> & pos, queue<pair<int,int>> & que, vector<vector<char>>& b) {
        int x = pos.first; int y = pos.second;

        if (y-1>=0 && b[x][y-1]=='O') {b[x][y-1] = 'A'; que.push({x,y-1}); }
        if (x-1>=0 && b[x-1][y]=='O') {b[x-1][y] = 'A'; que.push({x-1,y}); }
        if (y+1<b[0].size() && b[x][y+1]=='O') {b[x][y+1]='A'; que.push({x,y+1});}
        if (x+1<b.size() && b[x+1][y]=='O') {b[x+1][y]='A'; que.push({x+1,y}); }
       
    }
    void surroundedRegions(vector<vector<char>>& board) {
        if (board.empty()) return;
        // Write your code here
        queue<pair<int,int>> que;
       
        int w = board[0].size();
        int h = board.size();
       
        for (int i=0; i<h; i++) {
            if (board[i][0] == 'O') {
                board[i][0] ='A';
                que.push({i,0});
            }
            if (board[i][w-1] == 'O') {
                board[i][w-1] = 'A';
                que.push({i,w-1});
            }
        }
       
        for (int j=1; j<w-1; j++) {
            if (board[0][j] == 'O') {
                board[0][j] = 'A';
                que.push({0,j});
            }
            if (board[h-1][j] == 'O') {
                board[h-1][j] = 'A';
                que.push({h-1,j});
            }
        }
       
        while (!que.empty()) {
            auto p = que.front();
            que.pop();
            markNeighbours(p, que, board);
        }
       
        for (auto& line: board)
            for (auto& c: line)
                if (c=='A') c= 'O';
                else if (c=='O') c='X';
    }
};

Maximal Rectangle -- LeetCode

[Question]
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

[Analysis]
Scanning the matrix line by line, the 1's in scanned portion composed a histogram. Calculating the largest rectangle area in each histogram will give the final answer of the maximum area overall. The time complexity is O(MxN), if the matrix is M rows and N columns.

[References]
1. Largest rectangle area in histogram.
2. Minimum Value in Queue.
3. Container with the most water.

[Solution]
class Solution {
public:
    int maxRect(vector<int> &vec) {
        if (vec.size()==0) return 0;
     
        stack<int> st;
        int max_area = 0;
     
        for(int i=0; i<vec.size()+1; i++) {
            int next = (i<vec.size())? vec[i]:0;
         
            while(!st.empty() && next<vec[st.top()]) {
                int ind = st.top();
                st.pop();
                int area = (st.empty())? i*vec[ind]:(i-st.top()-1)*vec[ind];
                max_area = max(area, max_area);
            }
            st.push(i);
        }
        return max_area;
    }
 
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size()==0) return 0;
     
        vector<int> histogram (matrix[0].size(), 0);
        int max_area = 0;
     
        for(int i=0; i<matrix.size(); i++) {
            //... for each line, generate histogram and count the maximal rect on the histogram
            //...
            for (int j=0; j<matrix[0].size(); j++) {
                histogram[j] = (matrix[i][j]=='0')? 0: histogram[j]+1;
            }
            int area = maxRect(histogram);
            max_area = max(area, max_area);
        }
        return max_area;
    }
};