[Leetcode] 253. Meeting Rooms II

This problem is standard. But there are two points to make:

1. sort function, passing key argument
2. heap in python

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if len(intervals) <= 1: return len(intervals)
        
        intervals.sort(key=lambda x: x.start)
        h = []
        heapq.heappush(h, intervals[0].end)
        
        for i in intervals[1:]:
            if i.start >= h[0]:
                # update
                cur_endtime = heapq.heappop(h)
                cur_endtime = i.end
                heapq.heappush(h, cur_endtime)
            else:
                heapq.heappush(h, i.end)
        #print h
        return len(h)
        

[Leetcode] 545. Boundary of Binary Tree

Update: Hmm, I feel more comfortable of doing normal problems now. Seems that keeping doing these problems will soon be limited. Once I become comfortable of doing something, I just don't feel like doing it all the time any more... Luckily, computer science is such a broad subject and it is easy to improve anywhere anytime. But then, improving on new skillsets or working on harder problems will be too hard again.. I will struggle over them for a long time.. Ahh, I guess I will just live this kind of depressed life for the rest of my life...

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

Example 1

Input:
  1
   \
    2
   / \
  3   4

Ouput:
[1, 3, 4, 2]

Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
       
Ouput:
[1,2,4,7,8,9,10,6,3]

Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

Idea is that the boundary is made of left arm, all the leaves, and right arm. Then, just find all of them. 

Here is the code:

# 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 boundaryOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        if not root.right and not root.left: return [root.val]
        
        res = [root.val]
        m = []
        self.find_leaves(root, m)
        l = []
        self.find_left(root.left, l)
        r = []
        self.find_right(root.right, r)
        #print m, l, r
        return res + l + m + r[::-1]
    
    def find_leaves(self, node, m):
        if not node:
            return 
        elif not node.right and not node.left:
            m.append(node.val)
            return
        else:
            self.find_leaves(node.left, m)
            self.find_leaves(node.right, m)
            
    def find_left(self, node, l):
        if not node:
            return
        if not node.left and not node.right:
            return
        l.append(node.val)
        if not node.left:
            self.find_left(node.right, l)
        else: self.find_left(node.left, l)
        
    def find_right(self, node, r):
        if not node:
            return
        if not node.left and not node.right:
            return
        r.append(node.val)
        if not node.right:
            self.find_right(node.left, r)
        else:
            self.find_right(node.right, r)
        

[Leetcode] Course Schedule

This is a classical graph problem - the key is to detect cycle in a directed graph. This is usually done by flagging a node by 0, 1, 2, where 0 represents never visited, 1 in the stack, 2 visited. If at any time, we visited a node which status is 1, that it is in stack yet we visited it again, then it means that there is a cycle.

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Code: 

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
            
        visited = [0 for _ in range(numCourses)]
        
        def dfs(node, visited):
            visited[node] = 1
            for v in g[node]:
                if visited[v] == 1:
                    return False
                elif visited[v] == 0:
                    if not dfs(v, visited):
                        return False
            visited[node] = 2
            return True
            
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i, visited):
                    return False
        return True

[Leetcode] Longest Valid Parentheses

I really enjoyed solving this problem. The debugging process let me see the fallacies my thought has been. 

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

---

We are not unfamiliar with this kind of problems: "longest increasing subsequence", "longest palindrome substring", "max money we can rob". All these questions fall to dynamic programming category. Easy or common dynamic programming isn't hard to understand or even to conceive one compared to greedy problems, IMAO, but it takes practice.

The key to dynamic programming is to have a recurrence formula. When designing it, think about what kind of variables or current we need to know to get the next state. Of course, this variable has to help you get the final answer.

In this problem, a first thought would be devise a DP array that stores the length of longest valid parentheses (LVP).  However, if we know the s[i]'s LVP, it seems not helping me to know s[i+1]'s LVP, because the matching pair would be far back. But we are asking substring, meaning that if s[i] is in a solution, then s[i+1] might be in the solution, and the s[i+1]'s matching pair should be the one back s[i]'s matching pair. Therefore, if we record the s[i] matching pair's position, we would be able to know s[i+1]'s matching pair. If it doesn't match anything, then we just make the index its value.

Okay, now we have an array dp, which stores the index of the matching pair. So far so good. But it can't handle "()()" situation. Yes, I realize it from testing...

So the next step is to integrate the dp array. Here is the code:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 1: return 0
        # first round to get the position of the matching pair
        dp = [i for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == '(':
                continue
            k = i - 1
            while dp[k] != k and k > 0:
                k = dp[k] - 1
            if s[k] == '(' and k >= 0:
                dp[i] = k
            else:
                dp[i] = i
        # second round to get the final answer, basically
        # to connect case like this: "()()"
        i = len(s) - 1
        res = 0
        while i > 0:
            if dp[i] != i:
                tmp_res, k = 0, i
                while dp[k] != k and k > 0:
                    tmp_res += (k - dp[k] + 1)
                    k = dp[k] - 1
                res = max(res, tmp_res)
                i = k
            else:
                i -= 1
        return res

[Leetcode] 127. Word Ladder

Another classical breadth first search problem. The framework should be simple:

    initialize queue
    while queue:
        pop up the cur_word, path
        for all possible nodes (by possible nodes, I mean it only differs one letter with cur_word and is in wordList ):
            if this word is end word: return
            else: enter into the queue

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Here is the code:

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordList = set(wordList)
        queue = collections.deque([(beginWord, 1)])
        
        while queue:
            cur_w, path = queue.pop()
            for i in range(len(cur_w)):
                for l in 'abcdefghijklmnopqrstuvwxyz':
                    trans_w = cur_w[:i] + l + cur_w[i+1:]
                    if trans_w in wordList:
                        if trans_w == endWord:
                            return path + 1
                        else:
                            queue.appendleft((trans_w, path + 1))
                        wordList.remove(trans_w)
        return 0

[Leetcode] 81. Search in Rotated Sorted Array II

This problem doesn't look like a hard problem, but is very tricky. I guess there are two key points:

1. how to handle repeated numbers (I did not think it through)
2. figure out which part of the array to search

So I get the tricks from this solution: https://discuss.leetcode.com/topic/20593/python-easy-to-understand-solution-with-comments

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        start = 0
        end = len(nums) - 1
        while start <= end:
            mid = (start + end) / 2
            if nums[mid] == target: 
                return True
            
            while start < mid and nums[start] == nums[mid]:
                # tricky part, remove the repeatation
                start += 1
                
            if nums[start] == target or nums[end] == target:
                return True
            
            if nums[start] <= nums[mid]:
                # rotation point is behind the mid point
                # first part is in order
                if nums[start] < target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                # rotation point is before the mid point
                # second part is in order
                if nums[mid] < target < nums[end]:
                    start = mid + 1
                else:
                    end = mid -1

        return False

[Leetcode] 549. Binary Tree Longest Consecutive Sequence II

I am quite happy to solve this problem on my own. Let me explain in a little bit more detailed way.

Tl;dr: recursion; construct a function that can pass the information about the subtrees as well as the global result

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

---

This problem reminds me of a famous dynamic programming example, longest increasing sequencing, in which we construct the final result from subproblems. If I have a way to traverse the tree as we scan the array, if we are given a node and its left subtree's longest consecutive sequence length (CSL), right subtree's CSL, of course its left node and right node, we should be able to reason about my current node's longest consecutive sequence. Therefore, this problem can also be framed as dynamic programming problem. However, tree's traversal is way more indirect - we have to be comfortable with recursion.

Here comes the function "design" part, if we only save the local result, i.e., my current node's CSL, since my current node may not involve in the final solution, we won't be able to retrieve the final solution. Hence, we should also save the best result up to current node.

Also, the sequence can increase or decrease, and the path can be children-parent-children, and think about if we have a left_child - parent - right_child path, obviously, parent to left child and parent to right child are not in the same direction (increase-decrease or decrease-increase). Therefore, we also need to pass the increase, decrease information. Why not all then?

Together, the code (longer than most of Leetcode problem. indeed, the final if statements are quite tricky, have to be careful.)

# 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 longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = [0]
        self.helper(root, res)
        return res[0]
    
    def helper(self, node, res):
        if not node:
            return 0, 0
        elif not node.left and not node.right:
            res[0] = max(1, res[0])
            
            return 1, 1
        else:
            l_in, l_de = self.helper(node.left, res)
            r_in, r_de = self.helper(node.right, res)
            
            ret_in, ret_de = 1, 1 # return to next level
            
            tmp_res = 1 # children_parent_children pair
            
            if node.left:
                if node.left.val == node.val - 1:
                    # increase
                    ret_in = max(ret_in, l_in + 1)
                if node.left.val == node.val + 1:
                    # decrase
                    ret_de = max(ret_de, l_de + 1)
            if node.right:
                if node.right.val == node.val - 1:
                    # increase
                    ret_in = max(ret_in, r_in + 1)
                if node.right.val == node.val + 1:
                    # decrase
                    ret_de = max(ret_de, r_de + 1)
            if node.left and node.right:
                if node.left.val == node.val-1 == node.right.val-2:
                    tmp_res = max(tmp_res, l_in + 1 + r_de)
                if node.left.val == node.val + 1 == node.right.val + 2:
                    tmp_res = max(tmp_res, l_de + 1 + r_in)
            res[0] = max(tmp_res, ret_in, ret_de, res[0])
            return ret_in, ret_de