leetcode Question: Summary Ranges

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Analysis:

This is an easy question. Since the ranges are all continuous integers, we just need scan the whole array, compare each element with its previous one, if they are not continuous numbers, the current number must belong a new range. In my code, the start and end of the current range is kept in each iteration, don't forget the case that only one number can become a range and the output format is slight different required in this question.

Code(C++):

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        if (nums.size()==0){
            return res;
        }
        int st = nums[0];
        int ed = nums[0];
        for (int i=1;i<nums.size();i++){
            if ( ed + 1 != nums[i] ){
                if (st == ed){
                    res.push_back( to_string(st) );
                }else{
                    res.push_back( to_string(st) + "->" + to_string(ed) );
                }
                st = nums[i];
                ed = nums[i];
            }else{
                ed = nums[i];
            }
        }
         if (st == ed){
            res.push_back( to_string(st) );
        }else{
            res.push_back( to_string(st) + "->" + to_string(ed) );
        }
        
        return res;
    }
};

Code(Python):

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        if len(nums) == 0:
            return []
            
        res = []
        
        st = nums[0]
        ed = nums[0]
        
        for num in nums[1::]:
            if ed + 1 != num:
                if st == ed:
                    res.append(str(st))
                else:
                    res.append(str(st) + "->" + str(ed))
                st = num
                ed = num
            else:
                ed = num
        if st == ed:
            res.append(str(st))
        else:
            res.append(str(st) + "->" + str(ed))
            
        return res

leetcode Question: Basic Calculator II

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Analysis:

This is a straightforward question that only requires basic string operations.
Note that, there is no brackets "(" or ")" in the string, there is no negative numbers in the string. All we have is a string with +, -, *, / and numbers, and spaces.

Note that, the numbers in the string is not constrained to be 0 to 9, in other words, the first step is to split those numbers and operators from the string.  We can keep every digits of the number in a temporary string, until meet one of the operators. Then convert the number string into int and save it, don't forget to reset the tmp string.

Now we have a list of numbers as well as a list of operators. Since * and / operations have higher priorities, and there is no "( )", we can first compute those operations using the two adjacent numbers. After all the * and / operations are "removed" from the list, the last step is to compute all the remaining + and - in its original order.

Finally, the first number in the number list is the result.  


Misc. In python, remove element from list is pretty easy by using .pop(index) method. In C++, this can be done by using the vec.erase(vec.begin() + index) method, where vec is of type stl vector.  In python, string to int can be easily done by call the constructor of int: int(str). In C++, I choose to use a stringstream variable to do this convention. Remember to clear the string stream for new numbers.

Code(C++):

class Solution {
public:
    int calculate(string s) {
        
        vector<int> num;  //vector of ints
        vector<char> ops; //vector of operators
        
        //Convert string into ints and operators
        string n = ""; // string to store digits
        stringstream ss;
        for (int i=0;i<s.size();i++){
            if (s[i] == ' '){
                continue; //remove spaces
            }else{
                if (s[i]>='0' && s[i]<='9'){
                    n = n + s[i];
                } else{
                    ss.clear();
                    ss << n;
                    int tmp;
                    ss >> tmp;
                    num.push_back(tmp);
                    n = "";
                    ops.push_back(s[i]);
                }
            }
        }
        //don't forget the last number
        if (n.size()!=0){
            ss.clear();
            ss << n;
            int tmp;
            ss >> tmp;
            num.push_back(tmp);
        }
        
        
        //compute all the * and / operations
        int i = 0;
        while (i<ops.size()){
            if (ops[i] == '*'){
                num[i] = num[i] * num[i+1];
                num.erase(num.begin()+i+1);
                ops.erase(ops.begin()+i);
            }else if (ops[i] == '/'){
                num[i] = num[i] / num[i+1];
                num.erase(num.begin()+i+1);
                ops.erase(ops.begin()+i);
            }else{
                i++;
            }
        }
        
        //compute all the + and - operations
        i = 0;
        while (i<ops.size()){
            if (ops[i] == '+'){
                num[i] = num[i] + num[i+1];
                num.erase(num.begin()+i+1);
                ops.erase(ops.begin()+i);
            }else if (ops[i] == '-'){
                num[i] = num[i] - num[i+1];
                num.erase(num.begin()+i+1);
                ops.erase(ops.begin()+i);
            }else{
                i++;
            }
        }
        
        return num[0];
    }
};

Code(Python):

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        # remove spaces
        s = s.replace(" ","")
        
        num = [] # list of numbers 
        ops = [] # list of operators
        
        # read numbers and operators from string
        i = 0
        n = ""
        while i < len(s):
            if '9'>= s[i] >= '0':
                n = n + s[i]
            else:
                num.append(int(n))
                n = ""
                ops.append(s[i])
            i+=1
        if len(n) != 0:
            num.append(int(n))
        
        # compute all the * and / operations
        i = 0
        while i < len(ops):
            if ops[i] == '*':
                num[i] = num[i] * num[i+1]
                num.pop(i+1)
                ops.pop(i)
            elif ops[i] == '/':
                num[i] = num[i] / num[i+1]
                num.pop(i+1)
                ops.pop(i)
            else:
                i += 1
        
        # compute all the + and - operations
        i = 0
        while i < len(ops):
            if ops[i] == '+':
                num[i] = num[i] + num[i+1]
                num.pop(i+1)
                ops.pop(i)
            elif ops[i] == '-':
                num[i] = num[i] - num[i+1]
                num.pop(i+1)
                ops.pop(i)
                
        
        return num[0]

leetcode Question: Shortest Palindrome

Shortest Palindrome

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:

Although the logic of this question is not complicated, it is not easy to pass the OJ.
If you are familiar with famous string matching KMP algorithm, it would help a lot to solve the problem.

Let's first see the basic logic of this question. Given a string, out aim is to add a string in the front to make the new string a palindrome. Say the given string is \(S\), the string we add in the front is denoted as \(P\), so the result string is \(PS\), which needs to be a palindrome.  According to the definition of palindrome, we can rewrite string \(PS\) into:
$$ PS = PQP' $$, where \(QP' = S\) and \(P'\) is the reverse of string \(P\).
Note that, if \(PQP'\) is palindrome, \(Q\) must also be a palindrome. E.g., given a string "acecabcd", if we add a string "dcb",  the new string becomes  "dcbacecabcd", which is a palindrome. This string "dcbacecabcd" = "dcb" + "acecabcd", which can be rewritten as:
"dcb" + "acecabcd" = "dcb" + "aceca" + "bcd" = "dcb" + "aceca" + reverse("dcb"). Seen from this expression, string "aceca" is also a palindrome.

Let's see back to the question, now we have the string:
$$ PS = PQP' $$, we want \(P\) as short as possible, in other words, we want \(Q\) as long as possible. Thus, the question is now to compute the longest \(Q\)in string \(S\), subject to \(Q\) is a palindrome.


Next step is to compute longest palindrome start from the given string.  Brute-force is one way to solve it but it cannot pass the OJ. Recall the famous KMP algorithm, the failure function is to compute the longest suffix before current position that is also a prefix of the string. (more details see this post, which provides a very good explanation). In this question, we can easily convert the string to fit the the KMP failure function.

Say, we have string  $$ S = QP $$, we can append the reverse of \(S\) to \(S\): $$ SS' = QPP'Q' $$, remember that \(Q\)is a palindrome, \(Q=Q'\), therefore, we have: $$ SS' = QPP'Q $$, now we want to find the longest \(Q\), where \(Q\) is the prefix of \(SS'\), also a suffix of last position of \(SS\).

By applying to the failure function of KMP, we can get the result, but we have to pay attention that, the length of \(Q\) must less than \(S\) (half of \(SS'\)). In other words, we are only interested in the matching start from the second half of \(SS'\), that's why in line 19, 20 of my code, I keep the value as 0, so that the previous matching results will not effect the current matching.

Code(C++):

class Solution {
public:
    string reverse(string s){
        string res = "";
        for (int i=s.size()-1;i>=0;i--){
            res = res + s[i];
        }
        return res;
    }

    int failfunc(string s){
        int cnd = 0;
        int pos = 2;
        vector<int> t(s.size()+1,0);
        t[0] = -1;
        t[1] = 0;

        while (pos <= s.size()){
            if (pos ==s.size()/2){
                pos++;
            }else if (s[pos-1] == s[cnd]){
                cnd++;
                t[pos] = cnd;
                pos++;
            }else if (cnd > 0){
                cnd = t[cnd];
            }else{
                t[pos] = 0;
                pos++;
                cnd = 0;
            }
        }
        return t[s.size()];
    }

    string shortestPalindrome(string s) {
        int n = s.size();
        int m = failfunc(s + reverse(s));
        if (m >= s.size()){
            return s;
        }else{
            string q = s.substr(m);
            return reverse(q) + s;
        }
    }
};

Code(Python):

class Solution(object):
    
    def failfunc(self, s):
        ss = s + s[::-1]
        cnd = 0
        pos = 2
        t = [0 for x in range(len(ss)+1)]
        print t
        t[0] = -1
        
        while pos <= len(ss):
            if pos == len(s):
                pos += 1
            elif ss[pos-1] == ss[cnd]:
                cnd+=1
                t[pos] = cnd
                pos+=1
            elif cnd > 0:
                cnd = t[cnd]
            else:
                t[pos] = 0
                pos += 1
                cnd = 0
        return t[-1]
        
        
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return s
        m = self.failfunc(s)
        if m >= len(s):
            return s
        else:
            return s[m:][::-1]+s
        
         

leetcode Question: Basic Calculator

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Analysis:

In this question is not difficult but needs to pay more attention on the output order of a stack.
As there might be multiple round brackets (  and  ) in the string, it is natural to use stack to store the chars in the string. Here it doesn't matter to use either one or two stacks. For two stacks, one stores the operators and the other stores the numbers. From the start of the string, we can keep pushing each char into the stack(s),  only when we met the right bracket ")", compute the value of the expression inside "("  and ")", push the value into stack and continue.  When all the chars have been pushed into stack. Check the stacks, we have to continue compute the values according to the operators in stack, until no operators are there.

There are two important points:

1. Number in the string may not be of length 1, e.g., "123+456".
2. The output from stack is reverse to the operation order. e.g. for expression 1-2+3, the output from stack is 3, 2, 1 and + , -,   3+2-1 is NOT equal to 1-2+3. 

To handle these issues:

1. Keep counting the number and push it into stack once we meet operators. Don't forget to push the number when the string ends.
2. Use temporary stacks to revers the order of expression, then compute the value using correct order.

Let's take an example:

" (1+ (4+5+2)-3)+(6+8)"

1. Keep push the numbers and operators into stacks.

2. When meet the ')', compute the value inside "( )", which is 5+2 = 7, push this value back and continue.

3. Continue the above two steps for the whole string. Compute the rest operations according to the operators inside stack. 

4. The result is the top value in the number stack after all the operations. In this example, after computing 9 + 14 = 23, 23 is the result.

Note that, there might be multiple spaces in the string, an easy way is to get rid of the spaces at the beginning, since spaces is not useful for either operator or numbers.

Code(C++):

class Solution {
public:

    int compute(stack<int> num, stack<char> ops){
        //compute value
        while (!ops.empty()){
            char op = ops.top();
            ops.pop();
            int a = num.top();
            num.pop();
            int b = num.top();
            num.pop();
            if (op == '+'){
                num.push(a+b);
            }else if (op == '-'){
                num.push(a-b);
            }
        }
        return num.top();
    }

    string rmsp(string s){
        string ss = "";
        for (int i=0;i<s.size();i++){
            if (s[i]!=' '){
                ss += s[i];
            }
        }
        return ss;
    }


    int calculate(string s) {
        stack<int> num;
        stack<char> ops;
        
        s = rmsp(s); //remove spaces
        
        int i=0;
        int n = -1;
        while (i<s.size()){
            //current position is a (part of) number
            if (s[i]>='0' && s[i]<='9'){
                if (n==-1){n = 0;}
                n = n * 10 + s[i]-'0';
                i++;
            }else{
                if (n != -1){
                    num.push(n); //push number to stack    
                    n = -1; // set n to zero for new number
                }
                // ) compute value inside round brackets
                if (s[i] == ')'){
                    stack<int> tmp_num;
                    stack<char> tmp_ops;
                    while (ops.top()!='('){
                        tmp_ops.push(ops.top());
                        ops.pop();
                        tmp_num.push(num.top());
                        num.pop();
                    }
                    tmp_num.push(num.top());
                    num.pop();
                    
                    num.push(compute(tmp_num, tmp_ops));
                    ops.pop(); //pop ')' from stack
                    
                } else {
                    ops.push(s[i]);
                }
                i++;
            }
        }
        
        if (n!=-1){
            num.push(n);
        }
        
        stack<int> tmp_num;
        stack<char> tmp_ops;
        while (!ops.empty()){
            tmp_ops.push(ops.top());
            ops.pop();
            tmp_num.push(num.top());
            num.pop();
        }
        tmp_num.push(num.top());
        num.pop();
        
        return compute(tmp_num, tmp_ops);
    }
};

Code(Python):

class Solution(object):
    
    def compute(self, num, ops):
        while len(ops) != 0:
            op = ops.pop()
            if op == '+':
                num.append(num.pop() + num.pop())
            else:
                num.append(num.pop() - num.pop())
        return num[-1]
    
    
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        #remove spaces
        s = s.replace(' ', '') 
        
        num = []
        ops = []
        
        i = 0
        n = ''
        while i < len(s):
            if s[i] >= '0' and s[i] <='9':
                n = n + s[i]
                i += 1
            else:
                if n != '':
                    num.append(int(n))
                    n = ''
                
                if s[i] == ')':
                    tmp_num = []
                    tmp_ops = []
                    while ops[-1]!= '(':
                        tmp_ops.append(ops.pop())
                        tmp_num.append(num.pop())
                    tmp_num.append(num.pop())
                    ops.pop()
                    
                    num.append( self.compute(tmp_num, tmp_ops) )
                    
                else:
                    ops.append(s[i])
                    
                i += 1
                
        if n!= '':
            num.append(int(n))

        tmp_num = []
        tmp_ops = []
        while len(ops) != 0:
            tmp_ops.append(ops.pop())
            tmp_num.append(num.pop())
        tmp_num.append(num.pop())
        
                    
        return self.compute(tmp_num, tmp_ops)
            
        

leetcode Question: Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Analysis:

This is an easy question if you are familiar with recursion or DFS.
At the first glance, it is very natural to think this as an BFS problem, where we can search the tree level by level. However, if the binary tree is not a full tree, there might be many problems.
So, let's do it in simple recursion.

In my word, recursion always requires two things to consider, one is condition, the other is sub-problem. Condition mean stop/termination condition, e.g., in this question, when we meets the NULL node, we have to stop. When the left tree is NULL, the after converting, right is NULL, and vice versa.  Sub-problem is to find out how the program (the recursion function) can iterate many times. In this question, for each node, we just do the same process, find the left node,  find the right node, and swap them. But before this process, (this is the key part in recursion) we have to make sure that the left node and right node are already converted. See line 20 and line 26 in the C++ code below.  Getting clear that how those two things, writing program only requires some minor considerations such as the return value and null pointers, etc. 



Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root){
            return NULL;
        }
        
        TreeNode* res = new TreeNode(root->val); 
        
        if (root->right){
            res->left = invertTree(root->right);
        }else{
            res->left = NULL;
        }
        
        if (root->left){
            res->right = invertTree(root->left);
        }else{
            res->right = NULL;
        }
        
        return res;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        
        res = TreeNode(root.val)
        if root.right:
            res.left = self.invertTree(root.right)
        else:
            res.left = None
        
        if root.left:
            res.right = self.invertTree(root.left)
        else:
            res.right = None
            
        return res

leetcode Question: Implement Stack using Queues

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Analysis:

This is a classic question related to queue and stack. Let's review the stack and queue data structure, it is very easy to remember the properties of those two data structures that:

1. Queue:  FIFO (First In First Out)
2. Stack: LIFO (Last In First Out)

This question asks to use queue to simulate stack. There are several ways to do so, here I just provide one of the solutions that utilizing two queues. The basic idea is to swap the two queues every time when popping the element from stack. Queue 1 stores the stack top element, Queue 2 stores the previous elements. Every time when pushing one element into stack, push queue 1's top in queue 2, and push the new element in queue 1. Every time when popping the top element in stack, push the queue 1's top (only one element in this queue). Then push n-1 elements from queue 2 to queue 1, where n is the total number of elements in queue 2. In other words, we left one element in queue 2 (this is the top element in the current stack), and push all the other elements into the empty queue (queue 1). Finally we swap queue 1 and queue 2. The stack is empty iff queue 1 and queue 2 are all empty. The top element is always the only element in queue 1.

It is much clear and easier to understand the whole process by reading the code directly. See below for the code in C++ and python.

Code(C++):

class Stack {
private: 
queue<int> q1;
queue<int> q2;

public:
    Stack() {
        queue<int> q1;
        queue<int> q2;
    }
    
    // Push element x onto stack.
    void push(int x) {
        q1.push(x);
        if (q1.size()==1){return;}
        int tmp = q1.front();
        q1.pop();
        q2.push(tmp);
    }

    // Removes the element on top of the stack.
    void pop() {
        q1.pop();
        if (q2.size()==0){return;}
        for (int i=0;i<q2.size()-1; i++){
            q1.push(q2.front());
            q2.pop();
        }
        queue<int> tmp; 
        tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    // Get the top element.
    int top() {
        return q1.front();
    }

    // Return whether the stack is empty.
    bool empty() {
        if (q1.size()==0 && q2.size()==0){
            return true;
        }else{
            return false;
        }
    }
};

Code(Python):

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q1 = []
        self.q2 = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.q1.append(x)
        if len(self.q1) == 1:
            return
        else:
            self.q2.append(self.q1.pop(0))
        

    def pop(self):
        """
        :rtype: nothing
        """
        self.q1.pop(0)
        for i in range(len(self.q2)-1):
            self.q1.append(self.q2.pop(0))
        self.q1, self.q2 =  self.q2, self.q1
        

    def top(self):
        """
        :rtype: int
        """
        return self.q1[0]

    def empty(self):
        """
        :rtype: bool
        """
        if len(self.q1)==0 and len(self.q2)==0:
            return True
        else:
            return False

leetcode Question: Rectangle Area

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Analysis:

There are two step for solving this problem:
1. Check if the two rectangles are overlap or not.
2. Compute the overlap area. The overall area is \(area_1 + area_2 - area_{overlap}\).

To check the overlap of two rectangles, consider the non-overlap conditions:
1. A is on the left of B.  (A's right edge is on the left of B's left edge)
2. A is on the right of B.  (A's left edge is on the right of B's right edge)
3. A is on top of B.  (A's bottom edge is on top of B's top edge)
4. A is on the bottom of B.  (A's top edge is on the bottom of B's bottom edge)
In this problem:
Conditions A>G, C<E, D<F, B>H are corresponding to the above 4 conditions to check if the two rectangles are overlap.

To compute the overlap area, according to the figure in the question, it is not hard to derive the area is: \((\min(D, H) - \max(B,F)) \times (\min(C,G)-\max(A,E))\).

Code(C++):

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int area = (C-A)*(D-B) + (G-E)*(H-F);
        if (A>G || C < E || D < F || B > H){
            return area;
        } else{
            return area - (min(D, H)- max(B, F))*(min(C,G)- max(A,E));
        }
    }
};

Code(Python):

class Solution(object):
    def computeArea(self, A, B, C, D, E, F, G, H):
        """
        :type A: int
        :type B: int
        :type C: int
        :type D: int
        :type E: int
        :type F: int
        :type G: int
        :type H: int
        :rtype: int
        """
        area = (C-A)*(D-B) + (G-E)*(H-F)
        if A > G or C < E or D < F or B > H: 
            return area
        else:
            return area - (min(D, H)- max(B, F))*(min(C,G)- max(A,E))

leetcode Question: Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Analysis:

This is an DP problem. Usually in DP, all we need is to find out or define the transition function. Implementation part is then straightforward. For a DP problem, define the transition function is to find "how the solution of current state can be derived from only the previous state but not other states".   Now, let's see this problem.

The problem requires the square contains all 1's to be largest. Any square in this matrix is defined with three parameters:  x (row), y (column) and w (width).  To find the largest matrix, at least we will search every (x, y), to see if the square starts/ends in (x, y) are the target we need. One of the key point in this problem is the starts/ends. Let's see the figure below:

1	1	0	0	0
1	1	1	1	1
1	0	1	1	1
1	1	1	1	1
1	0	1	1	1

For the colored square, we may say

1. This square starts from (0, 0) (top-left) with width 2, 

2. This square ends at (1, 1) with width 2.

In DP, we need to keep the result in every state, an matrix state[][] is needed.

We initialize the state[][] :   for each position (x, y) in state, if matrix[x][y] == '1', state[x][y] = 1

Because 1*1 the element itself is also a square if its value is '1'. state[x][y] is recording the largest square width that ends at (x, y).  Why using ends? Because we have to utilize the previous states (here you can imagine the states is the largest width that were computed in previous positions.). If we use the position as the starting point, it's hard to get the previous states because we will checking the 'future' states which are not available. See the figure below, we are search from top-left to bottom-right,  

For position (3,3) which is marked red 1, we can derive the largest square that ends at this point by checking its previous positions. The square with width 3 that ends at (3, 3) is a combination of four squares:
1. Square that ends at (2,2) with width 2  (green square)
2. Square that ends at (3,2) with width 2  (orange square)
3. Square that ends at (2,3) with width 2  (blue square)
4. (3, 3) itself. (red 1)

If all the squares are all 1's, state[3][3] is then become 2+1 = 3. However in the above figure, condition 1 is an all 1's square, condition 2  and 3 are not. So the largest square the ends at (3, 3) cannot be 2 + 1 = 3.  Also it cannot be 1+1 = 2 because condition 1,2,3 with with 1 are not true (see green 1, blue 1, orange 0 and red 1 in the figure).  In short, we derive the transition function:

state[x][y] = 1 + min{state[x-1][y], state[x][y-1], state[x-1][y-1]}

Given this function, the implementation is now pretty straightforward.

Code(C++):

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if (row == 0) {return 0;}
        int col = matrix[0].size();
        
        vector<vector<int> > state (row, vector<int>(col));
        
        int res = 0;
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (matrix[i][j] == '1'){
                    state[i][j] = 1;
                    res = 1;
                }
            }
        }

        for (int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if (state[i][j] != 0){
                    state[i][j] = 1 + min(state[i-1][j], min(state[i][j-1],state[i-1][j-1]));
                    if (res<state[i][j]){ res = state[i][j]; }
                }
            }
        }
        return res*res;
    }
};

Code(Python):

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res = 0
        row = len(matrix)
        if row == 0:
            return res
        col = len(matrix[0])
        state = [[0 for y in range(col)] for z in range(row)]
        
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == '1':
                    state[i][j] = 1
                    res = 1
                    
        for i in range(1, row):
            for j in range(1,col):
                if state[i][j] != 0:
                    state[i][j] = 1+ min(min(state[i-1][j],state[i-1][j-1]),state[i][j-1])
                    if res < state[i][j]:
                        res = state[i][j]
        return res*res

leetcode Question Question: Count Complete Tree Nodes

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

Analysis:

In this problem, directly traverse the binary tree will not pass the OJ. We have to narrow the searching space. Looking at the problem we know that the input binary tree is a complete tree.
It is easier to understand what a complete tree is by drawing some, e.g.,


These are all complete binary trees. Now the problem is how to calculate the nodes as many as possible by computing them rather than counting them one by one.

Firstly we know that, besides the last layer, it is a full tree, which means the number of nodes is computed by \(2^h -1 \), where \(h\) is the depth of tree.

Secondly we have to find out how many node are there in the last layer. It is not difficult to observe that for every leaf node in a complete tree, there is no missing node on its left side.  Consider the last layer of nodes is an array of 0s and 1s and we know the length of the array, e.g. [1,1,1,1...,1,1,0,0,0,...0,0], we want to know how many 1s are there, in an efficient way. What do we have?  Yes, binary search. The basic idea is to locate the middle position of the array and check if it is a 1, if so, search the right half, if not, search the left half, until we find the exact position.

Now it is a little different from the single array, we have a binary tree, but the idea is the same.
Let's see, for the array, we know that the middle position is usually computed by \(st+ (ed-st)/2 \). For the last layer of binary tree, the left-most node in right sub-tree is a good option to represent it!
E.g., for the whole leaf layer, its middle point (left-most node in right sub-tree) is the green dashed node in the figure below, it is an empty node (imagine a 0 in an array [11..100..0]):

In this case, we met an empty node, according to the idea of binary search, we have to search the left half in the same way. Now, where is the middle position?

It's still the left-most node in right sub-tree, but this time the root node is no longer the root node of the whole binary tree, but the left child of the root because we are now dealing with the left part of the tree. (see the blue nodes in the figure above). In this scenario, we find the node, it is not empty, which means, we can easily compute how many leaf nodes are there on the left:  \(2^{h_{sub}-1}\), where \(h_{sub}\) is the depth of the sub-tree (root node in blue color in above figure), -1 is because we only have half of the nodes in last layer.  In this way, we keep the binary searching and finally we can have the number of leaf nodes in this compete tree, the final result is the number of leaf nodes + number of full tree.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // find the depth of left most node in right subtree of current node
    int findSplit(TreeNode* root){
        if (!root || !root->right){
            return 0;
        }else{
            TreeNode* tmp = root->right;
            int dep = 0;
            while (tmp){
                dep += 1;
                tmp = tmp->left;
            }
            return dep;
        }
    }

    int countNodes(TreeNode* root) {
        if (!root){return 0;}
        int res = 0;
        int dep_l = 1;
        int dep_r = 1;
        
        //find left most depth
        TreeNode* tmp = root;
        while (tmp->left){
            dep_l+=1;
            tmp = tmp->left;
        }

        TreeNode* cur_root = root;
        int cur_dep = 1;
        while (cur_dep < dep_l){
            int dep_split = findSplit(cur_root);
            if (dep_split + cur_dep == dep_l){
                cur_root = cur_root->right;
                cur_dep +=1;
                res += pow(2,dep_split-1);
            }else{
                cur_root= cur_root->left;
                cur_dep +=1;
            }
        }
        return pow(2,dep_l-1)+res;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    
    def findSplitDepth(self, root):
        if not root:
            return 0
        else:
            root = root.right
            dep = 0
            while root:
                root = root.left
                dep += 1
            return dep
    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        dep = 1
        tmp = root
        while tmp.left:
            dep += 1
            tmp = tmp.left
        
        cur_root = root
        cur_dep = 1
        res = 0
        while cur_dep < dep:
            dd = self.findSplitDepth(cur_root)
            if dd + cur_dep == dep:
                cur_root = cur_root.right
                res += pow(2, dd-1)
                cur_dep += 1
            else:
                cur_root = cur_root.left
                cur_dep += 1
        
        return pow(2, dep-1) + res
        

leetcode Question: Factorial Trailing Zeroes

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Analysis:

Zeros can only generated on prime factors of 5s and 2s.
Lets' say 5s = {5*1, 5*2 ... 5*n}, 2s = {2*1, 2*2 ... 2*n}

So in this problem we need to count how many 5s and 2s.
Note that in n!, the 2s are always more than 5s, so we simplify the problem into counting the 5s.
There are several cases on 5s.  They are 5, 5^2, 5^3 ...
First let's see how to count 5s,  all we need is to compute floor (n/5) .
Then let's deal with 5^n.
E.g., n = 28,  it has 5s =  [5, 10, 15, 20, 25]
When we count 5s using floor(n/5), we have the length 5, but 25 = 5*5, there should be another 5 and the length is 6.  To count this, we can continue counting 5s using n divide by 5, 5^2, 5^3 ... In this way, all the 5s can be found.

Code(C++):

class Solution {
public:
    int trailingZeroes(int n) {
        long p = 5;
        int res = 0;
        while (p <= n){
            res += n/p;
            p = p*5;
        }
        return res;
    }
};

Code(Python):

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        p = 5
        res = 0
        while p <= n :
            res += n/p
            p = p *5
        return res
            

leetcode Question: Contains Duplicate III

Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Analysis:

At the first glance, it is natural to think that "using two loops to search every two elements within distance k" to solve this problem. However, the O(n^2) time complexity is not accepted for OJ.

Here is how I think of the problem, since it is asking for whether two indices exists ... , we have to search the array in some way.  There are two constrains:  one is related to element values in the array, the other is related to indices.  So, we have to consider the two at the same time when checking one pair of elements. In other words, we have to know the element value and the element index at the same, and using some strategy, to scan the array and find if there is any pair satisfy the constrains.


Let's take an example, say the array is A = [3,6,0,4], and we set t = 2, k =2.
Let's sort the array according to the value,
the values of the array becomes:  A' = [0, 3, 4, 6]
the indices of the array becomes:  I' = [2, 0, 3, 1]
We rewrite them into one array:
P = [(0,2), (3,0), (4,3), (6,1)]

Now we are searching the pairs, starting from the first pair:
(0, 2) where 0 is the value 2 is the index.

Now we have pair  P[i] = (0,2), i = 0, we need P[j] to check if  P[i] and P[j] satisfy the constrains that
abs(P[i][0] - P[j][0]) < = t and abs(P[i][1] - P[j][1]) < = k.


When compare current pair P[0] = (0,2) and next pair P[1] = (3,0),  abs(0-3) > t. It seems natural to keep the first pair P[0] and search the rest of array after P[1], but in fact it is not an efficient way, especially when k is a large number.

Since we have already sorted the array, if the value difference between P[0] and P[1] is greater than t, the value difference between P[0] and P[2], P[3] ... P[end] must also greater than t. If current comparison is not satisfied, all the other comparisons are not even necessary. We can move P[0] to next element.

While on the other hand, if the value difference <= t, but the index difference > k, we still have to  keep the current P[i] and move P[j] until meets the above scenario or the end of the array.

In this example:
1. Compare (0,2) and (3,0),   abs(0-3) >t
2. Compare (3,0) and (4,3),   abs(3-4) <=t , abs(0-3) > k
3. Compare (3,0) and (6,1),   abs(6-3) > t
4..Compare (4,3) and (6,1),   abs(4-6) <=t, abs(3-1)<=k, satisfied. Return True.

Code(C++):

class Solution {
public:
    static bool pcomp(pair<int,int> a, pair<int,int> b) {
        return a.first < b.first ;
    }
    
    bool search(vector<pair<int,int> > l, int t, int k){
        int po = 0;
        while (po < l.size()){
            int i = po + 1;
            while (i < l.size()){
                if ((abs(long(l[i].first) - long(l[po].first)) <= t)&&(abs(l[i].second - l[po].second)<= k)){
                    return true;
                }else{
                    if (abs(long(l[i].first) - long(l[po].first)) > t){
                        break;
                    }else{
                        i+=1;
                    }
                }
            }
            po += 1;
        }
        return false;
    }
    
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (nums.size() == 0 ){
            return false;
        }
        vector<pair<int,int> > pp;
        for (int i=0;i<nums.size();i++){
            pp.push_back(make_pair(nums[i], i));
        }
        sort(pp.begin(),pp.end(),pcomp);
        return search(pp, t, k);
    }
};

Code(Python):

class Solution(object):
    def search(self, l, t, k):
        po = 0
        while po < len(l):
            i = po + 1
            while i < len(l):
                if abs(l[i][0] - l[po][0]) <= t and abs(l[i][1] - l[po][1]) <= k:
                    return True
                else:
                    if abs(l[i][0] - l[po][0]) > t:
                        break
                    else:
                        i +=1
            po += 1
        return False     
        
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        pp = sorted(zip(nums, range(len(nums))), key= lambda x:x[0])
        return self.search(pp,t ,k )
        
        

leetcode Question: Contains Duplicate II

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.

Analysis:

Same idea as previous question that Hash table is used. The only difference if the requirement of minimum distance between the same elements is at most k.

Remember that previous question, we set the value of hash table True/False, in this question, we change that to the index of element. Therefore we can keep tracking the distance between the two elements. A simple check can solve the problem.

Code(C++):

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (nums.size() == 0 ){
            return false;
        }
        map<int,int> mp;
        for (int i=0;i<nums.size();i++){
            if (mp.find(nums[i])==mp.end()){
                mp[nums[i]] = i;
            }else{
                if (i - mp[nums[i]] <= k){
                    return true;
                }else{
                    mp[nums[i]] = i; //Update the position
                }
            }
        }
        return false;
    }
};

Code(Python):

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if len(nums) == 0:
            return False
        mp = {}
        for i in range(len(nums)):
            # Note: here you cannot use "if not "
            # because if mp[nums[i]] == 0, if not will also return True
            if mp.get(nums[i]) == None:
                mp[nums[i]] = i
            elif (i - mp[nums[i]]) <= k:
                return True
            else:
                mp[nums[i]] = i
        return False

leetcode Question: Contains Duplicate

Contains Dulplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Analysis:

This is an easy question and there are many ways to do it.

One way is to firstly sort the array, and check each two elements to see if they are equal.

Another way is to utilize the hash map (map in C++ STL), create the map at the same time check if there exists any duplicates.

Code(C++):

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size()==0){
            return false;
        }
        map<int, bool> mp;
        for (int i=0;i<nums.size();i++){
            if (mp.find(nums[i])==mp.end()){
                mp[nums[i]] = true;
            } else{
                return true;
            }
        }
        return false;
    }
};

Code(Python):

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 0:
            return False
        mp = {}
        for num in nums:
            if not mp.get(num):
                mp[num] = True
            else:
                return True
        return False