leetcode Question: Lowest Common Ancestor of a Binary Search Tree

 Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

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).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Analysis:

One obvious way to solve this problem is to utilizing the properties of Binary Search Tree:

• It is ordered when you do Tree traversal

However, in this post, we are solving this problem in a more general way. (It is same as the problem here).

The idea is simple: recursion.

Usually when I do recursion problem, I consider:

• What are we looking for?
• What is the termination condition?
• Which direction do we go for the searching?

According to this problem:

• We are looking for the common ancestor. In other words, if the two node are in the current node's left and right child, respectively, current node is thus the lowest common ancestor.
• When do we stop search? 1. Null node. 2. meet either one of the two nodes, the ancestor is this node or above.
• Which direction do we go ? For a binary tree, left and right.  

So, we start the search from the root node, recursively find the common ancestor for root->left and root->right, if both of them are existed, which means root is the lowest common ancestor, otherwise, the existed one is the result.

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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root){
            return NULL;
        }
        if (root == p || root == q){
            return root;
        }else{
            TreeNode* lc = lowestCommonAncestor(root->left, p, q);
            TreeNode* rc = lowestCommonAncestor(root->right, p, q);
            if (lc && rc){
                return root;
            }else{
                if (lc){return lc;}
                if (rc){return rc;}
            }
        }
    }
};

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 lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root == p or root == q:
            return root
        else:
            lc = self.lowestCommonAncestor(root.left, p, q)
            rc = self.lowestCommonAncestor(root.right, p, q)
            if lc and rc:
                return root
            else:
                if lc:
                    return lc
                if rc:
                    return rc
        
            

leetcode Question: Palindrome Linked List

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Analysis:

In order to satisfy the O(n) time and O(1) space requirements, we have to consider in-place check/modify the linked list.  Look at the definition of palindrome, it is easily to find out for a palindrome, if we reverse the second half of the list, the first half and second half are identical.

OK, this is where we start to solve the problem. How about the complexity?
1. First we need to find the middle pointer of the list. It is pretty easy if you remember the slow and fast pointers (similar idea was used in previous leetcode question like here).

2. If we can do the reversing in-place, the space we need are only several temporary pointers. If you remember the previous questions (here), you can easily reverse the list.

The basic idea is shown here by an simple example:
Original list: 1->2->3->4->5
We can have a header pointer: head->1->2->3->4->5
Each time, move current pointer to the first place (which is after head pointer).
head->2->1->3->4->5
head->3->2->1->4->5
head->4->3->2->1->5
head->5->4->3->2->1
Done

3. The reversing step is of O(n) time, then checking two halves will only take O(n), so the overall time complexity is O(n).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    void reverse_list(ListNode** head_ref){
        ListNode* head = *head_ref;
        ListNode* p = head->next;
        while (p && p->next){
            ListNode* tmp = p->next;
            p->next = p->next->next;
            tmp->next = head->next;
            head->next =tmp;
        }
        *head_ref = head;
    }

    bool isPalindrome(ListNode* head) {
        //Get middle pointer: p1
        ListNode* p1 = new ListNode(0);
        p1->next = head;
        ListNode* p2 = p1;
        while(p2 && p2->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        //reverse second half list
        reverse_list(&p1);
        
        //check palindrome
        p1 = p1->next;
        p2 = head;
        while (p1){
            if (p1->val != p2->val){
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    
    def reverse(self, head):
        p = head.next
        while p and p.next:
            tmp = p.next
            p.next = p.next.next
            tmp.next = head.next
            head.next = tmp
            
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        #get middle pointer
        p1 = ListNode(0)
        p1.next = head
        p2 = p1
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        
        # reverse second half of list
        self.reverse(p1)
        
        # check palindrome
        p1 = p1.next
        p2 = head
        while p1:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True
        
        

leetcode Question: Number of Digit One

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Analysis:

It takes me a couple of hours to figure out a easy way to solve this problem. Basically once you get the idea, it would take you less than 10 mins to implement the code, and before that, all you need is a piece of paper and a pencil.

At the first glance, what usually comes up to our mind is different O(n) solutions, however this won't pass the OJ. We must think from another way: from digit to digit.

Lets' first take a look at an easier problem:  how many digits 1 appearing in all non-negative integers less than or equal to n-digits length integer?  In other words, how many "1"s in  0-9 (1-digit), how many "1"s in 0-99, how many "1"s in 0-999...

From 0-9, it is not hard to find out there is only 1 "1" (here "1" indicates the digit 1 in integer), it occurred in integer 1.

From 0-99, counting number of "1" is a procedure as follows:
1. Consider two blank slots which we fill number in them: [ ][ ]

2. Both digits are ranging from 0-9, e.g., [0][2] = 2, [1][3] = 13, denote as [0-9][0-9].

3. There are two cases:  [0,2-9][ 0-9] and [1][0-9]

4. Case 1: [0,2-9][0-9]. There is no "1" in the highest digit. "1" only appears in the rest of digits, here is one digit [0-9]. For each number in [0, 2-9], we have the number of "1" from its lower digit(s) [0-9], which is 1. Now we have 10 different possible highest digits, i.e., 0,2,3,4,5,6,7,8,9, for every one of them, the lower digit(s) can generate 1 "1", in total there are 10 *1 = 10  "1"s in this case.

5. Case 2: [1][0-9]. "1" is in highest digit, which means every possible number in  its lower digits (now is [0-9]) contains one "1".  So there are 1*10  = 10 "1"s in this case.

6. Sum Case 1 and Case 2 up, we have 20 "1"s from 0-99.



Next, let's see how to count "1" from 0-999, similar to previous steps:
1. We have three blank slots [ ][ ][ ].

2. There are two cases: [1][0-9][0-9] , and [0, 2-9][0-9][0-9].

3. Case 1:  [0, 2-9][0-9][0-9]. # of "1" is in this case equal to:  # of "1" in [0-9][0-9]  times 10 =  20*10 = 200.

4. Case 2: [1][0-9][0-9], we have more "1"s since all numbers in form [1][0][0] to [1][9][9] have an additional "1" in their highest digit. Thus, we need to add 100, which is # of integers from 100-199.

5. The total number of "1" from 0-999 is 300.




Getting clear the above procedures, now we are targeting arbitrary number. Let's take an example,
say n = 5746. Denote function C(m,n) as the number of digit "1" appearing from integer m to integer n. We can write down the procedure:

$$
\small\begin{array}{ccccccccccccc}
C(0,5746) & = & C(0,999) & + & C(1000,5746)\\
& = & C(0,999) & + & 4*C(0,999) & + & 1000 & + & C(5000,5746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,99) & + & C(100,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & C(700,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & C(0,46)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & 5*C(0,9) & + & 10\\
& = & 5*300 & + & 1000 & + & 7*20 & + & 100 & + & 5 & + & 10\\
& = & 2755

\end{array}
$$


Although it looks complicated, from the programming view, it is much easier. There are two cases you have to pay attention to, (1). When current digit is 0, there no additional "1" to be added. (1000, and 100 and 10 in the above expression.) (2) When current digit is 1, the additional "1" is not 10,100,or 1000 any more, but the actual number in its lower digits.

In my implementation, I choose to use lower to higher order rather than the higher to lower order when scanning each digit. To get i-th digit, we can use \((n\%10^{i})/(i/10)\). I use bool type to check the current digit to simplify my code.  "m" indicates the number of "1"s  in 0-9, 0-99, 0-999 and so on.

Code(C++):

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        int m = 0;
        for (long i=1;i<=n;i=i*10){
            int d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*(i);
            m = m*10 +i;
        }
        return res;
    }
};

Code(Python):

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        m = 0
        i = 1
        while i <= n:
            d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*i
            m = m*10 +i
            i = i*10
        return res

leetcode Question: Implement Queue using Stacks

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

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

Analysis:

This kind of problem usually requires more than one data structure to implement the other data structure. In this problem, two stacks are enough to implement a queue.

The idea is keep push element into stack 1, then "pop" is called, put all the elements from stack 1 to stack 2. Then pop the top element in stack 2.  If "pop" is called again, not stack 2 is not empty, just pop the top element is enough. If stack 2 is empty, put all the elements in stack 1 to stack 2.  In short, stack 1 is used for "push", stack 2 is used for "pop" and "peek". We do the "move element from stack1 to stack 2" only when stack 2 is empty and "pop" or "peek" is called.


e.g., We call push(1), push(2), push(3), push(4), and push(5), stack 1 is filled all the five elements, then do pop(), since stack 2 is empty, move elements from stack 1 to stack 2, then pop the top element (now is 1) in stack2:

 Then we call push(6), push(7), push(8), push(9), and pop(), pop(), pop(), stack 1 is used for pushing, and stack 2 is used for popping :

Again, we call pop() (now 5 is popped out and no element in stack 2), and a peek() operation is called, stack 2 is empty, so push elements from stack 1 to stack 2, and return the top element as the peek:

Code(C++):

class Queue {

stack<int> st1;
stack<int> st2;

public:
    // Push element x to the back of queue.
    void push(int x) {
        st1.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if (!st2.empty()){
            st2.pop();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
        }
    }

    // Get the front element.
    int peek(void) {
        if (!st2.empty()){
            return st2.top();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            return st2.top();
        }
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return (st1.empty() && st2.empty());
    }
};

Code(Python):

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st1 = []
        self.st2 = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.st1.append(x)
        

    def pop(self):
        """
        :rtype: nothing
        """
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        self.st2.pop()
                

    def peek(self):
        """
        :rtype: int
        """    
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        return self.st2[-1]
        

    def empty(self):
        """
        :rtype: bool
        """
        return not self.st1 and not self.st2

leetcode Question: Power of Two

Power of Two

Given an integer, write a function to determine if it is a power of two.

Analysis:

An straightforward way is to keep doing "divide by 2" for the number and check if current number "mod 2" is zero. However this is pretty slow (it still can pass the OJ).

More efficient way is to use bit manipulation.

If one number is a power of 2, then its binary must starts with 1 and all the lower bits are 0. e.g.,
2 10
4 100
8 1000
16 10000
...

Also, we have to find a "mask" to check this format, what "mask" should we use?
Let's see some examples:
1 01
3 011
7 0111
15 01111
...

Well, it is not hard to see that,  if one number "n" is a power of 2, then "n-1" must have all 1s in its binary format. Therefore, "n & n-1" must be 0.  

Code(C++):

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return ( (n>0) && (n & (n-1))==0 ) || (n==1);
    }
};

Code(Python):

aclass Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n>0 and  n & (n-1)==0 or n==1