czxttkl

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n².

Code

from heapq import *

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        # each element in the heap: (val, x coord, y coord)
        h = []

        for i in xrange(min(len(matrix[0]), k)):
            heappush(h, (matrix[0][i], 0, i))
        
        for i in xrange(k-1):
            val, x, y = heappop(h)
            if x < len(matrix)-1:
                heappush(h, (matrix[x+1][y], x+1, y)) 

        return h[0][0]

Idea

Maintain a min-heap with k element, initialized by the elements of the first row. Since it is a min-heap, and note the property that rows and columns are already sorted in ascending order, the heap root after popping k-1 times is the k-th smallest element of the whole matrix. When popping the heap, we also need to push necessary matrix elements into the heap.

You can imagine that when you traverse the matrix and maintain the heap, actually you are swiping through a sector area of the matrix, starting from the first row:

Space complexity is O(K) (heap size)

Time complexity is O(KlogK) (every heap operation takes O(logK))

Reference: https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code

Pythonically brute-force:

Code

from heaps import *
class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        return list(merge(*matrix))[k-1]

Note that each argument sent to heapq.merge should already be sorted from smallest to largest. (https://docs.python.org/2/library/heapq.html)

Binary Search

Code

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        left, right = matrix[0][0], matrix[n-1][n-1]
        while left < right:
            mid = left + (right - left)/2
            count = 0
            j = n-1
            for i in xrange(n):
                while j >=0 and matrix[i][j] > mid:
                    j -= 1
                count += j + 1
            if count >= k:
                right = mid
            else:
                left = mid + 1
        
        return left            
        

Idea:

We can eventually find the k-th smallest element by shrinking the search range in binary search. Binary search is feasible for this problem since left, right,and mid in binary search are integers and we know that matrix elements are integers. 

The algorithm takes O(nlogN) time (N is the range of matrix[0][0] ~ matrix[n-1][n-1]) and O(1) space.

Time complexity analysis: the outer loop (line 10-21) executes at most O(logN) times. The inner for loop (line 14-17) executes at most O(n) times.

Reference: https://discuss.leetcode.com/topic/52865/my-solution-using-binary-search-in-c/16

Also a much more complicated algorithm taking O(N) time: https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

https://leetcode.com/problems/palindrome-number/

Code

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0 or (x > 0 and x % 10 == 0): 
            return False
        
        sum = 0
        while x > sum:
            sum = sum * 10 + x % 10
            x = x / 10
        
        return x == sum or x == (sum/10)

Idea

Create a variable, sum, that sums the digits reading from the right to left. Note that the while loop stops when x<=sum. Therefore, sum will never be larger than original x. This guarantees that `sum` will never cause overflow issue.  

The final return condition is x==sum or x==(sum/10). However, any number that is multiples of 10 also satisfies this condition. That is why we need to exclude multiples of 10 in line 7-8.

Reference:

https://discuss.leetcode.com/topic/8090/9-line-accepted-java-code-without-the-need-of-handling-overflow

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Code (recursion)

# 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 rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.recursion(root, 1, res)
        return res

    def recursion(self, node, level, res):
        if node is None:
            return res
        if len(res) < level:
            res.append(node.val)
        self.recursion(node.right, level+1, res)
        self.recursion(node.left, level+1, res)

Code

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

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None: 
            return []
        
        res = []
        q = deque([(root, 0)])
        last_v = 0
        last_l = 0
        
        while q:
            n, l = q.popleft()
            if l > last_l:
                res.append(last_v)
            
            last_l = l
            last_v = n.val

            if n.left is not None:
                q.append((n.left, l+1))
            if n.right is not None:
                q.append((n.right, l+1))
        
        res.append(last_v)
        return res
        

Idea

Core idea is to have level recorded during traversal.

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 isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return (p is None and q is None) or (p is not None and q is not None and p. val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

Idea

Recursion is easy to implement for this problem.

Code

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

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        q1,q2 = deque([p]), deque([q])
        
        while stk1 and stk2:
            n1, n2 = q1.popleft(), q2.popleft()
            if (n1 is None and n2 is not None) or \
               (n1 is not None and n2 is None) or \
               (n1 and n2 and n1.val != n2.val):
                return False
                
            if n1 and n2:
                q1.append(n1.left)
                q2.append(n2.left)
                q1.append(n1.right)
                q2.append(n2.right)
            
        return True

Idea

Traverse two trees in same manner. Here I implement a bfs traverse.

Reference: https://discuss.leetcode.com/topic/7513/my-non-recursive-method (The author uses pre-order dfs)

        0
        |
        1
       / \
      2   3

     0  1  2
      \ | /
        3
        |
        4
        |
        5

Code

from collections import defaultdict

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 0: return []
        if n == 1: return [0]
        
        res = []
        adj = defaultdict(set)

        for e in edges:
           adj[e[0]].add(e[1])
           adj[e[1]].add(e[0])

        leaves = self.build_leaves_from_adj(adj)
        
        while n > 2:
            n = n - len(leaves)
            for l in leaves:
                adj[adj[l].pop()].remove(l)
                adj.pop(l)
            leaves = self.build_leaves_from_adj(adj)
        
        return leaves

    def build_leaves_from_adj(self, adj):
        return [k for k, v in adj.iteritems() if len(v) <= 1]
 

Idea

Imagine you are doing BFS from the current leaves. In every iteration, you remove all edges connected with leaves and leaf nodes themselves. Then, you re-identify new leaves. You repeatedly do this until at most two nodes left. The remaining nodes are the rooted nodes for MHT. 

Reference: 

https://discuss.leetcode.com/topic/30572/share-some-thoughts/2

Code

from collections import defaultdict

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 0: return []
        if n == 1: return [0]        

        res = []
        adj = defaultdict(set)

        for e in edges:
           adj[e[0]].add(e[1])
           adj[e[1]].add(e[0])

        max_path = self.maxpath(adj, edges[0][0], None)    
        max_path = self.maxpath(adj, max_path[-1], None)        
        l = len(max_path)

        if l % 2 == 0:
            return max_path[l/2-1:l/2+1]
        else:
            return max_path[l/2:l/2+1]        

    def maxpath(self, adj, cur_node, prev_node):
        max_path = [cur_node]
  
        for n in adj[cur_node]:
            # check whether the next visiting node is not visited before. 
            # use the property that tree has no cycle. just need to check with last visited node.
            if n != prev_node:
                new_max_path = [cur_node] + self.maxpath(adj, n, cur_node)    
                if len(max_path) < len(new_max_path):
                    max_path = new_max_path   
        return max_path
        

Idea (From https://discuss.leetcode.com/topic/30956/two-o-n-solutions)

Longest Path

It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree.
Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).

Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs).
The following is some thought of the latter.

Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.
Then y must be one of the endpoints on some longest path.
Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.

Now, the path from y to z is the longest one, and thus its middle point(s) is the answer. 

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Code (Bit manipulation)

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ss_num = 2 ** len(nums)
        ss = [[] for i in xrange(ss_num)]

        for i in xrange(ss_num):
            k = i
            for j in xrange(len(nums)):
                if k & 1:
                    ss[i].append(nums[j])
                k = k >> 1
        return ss
                

Idea

There should be $latex 2^len(nums)$ subsets. So you can construct binary numbers from 0…0 to 1…1. For each binary number, its every bit indicates whether to includes a number in `nums`. 

Code (DFS)

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, 0, [], res)
        return res
    
    def dfs(self, nums, start_idx, path, res):
        res.append(path)
        for i in xrange(start_idx, len(nums)):
            self.dfs(nums, i+1, path + [nums[i]], res)                

Idea

Try to build a directed graph in which node x connects to node y (y > x). For example, if the given set is [0,1,2,3,4], then:
node 0 is connected to node 1, 2, 3, 4
node 1 is connected to node 2,3,4
node 2 is connected to node 3,4
node 3 is connected to node 4

Then you do dfs. At the moment of visiting each node, you add the traced path to result.

   1
    \
     2
    /
   3

Code (recursive)

# 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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

Code (Iterative)

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        
        stk = []
        res = []        

        while stk or root:
            while root:
                stk.append(root)
                root = root.left
            
            root = stk.pop()
            res.append(root.val)
            root = root.right

        return res

Idea

At first, I was not sure whether to use a queue or a stack to store the nodes to be traversed. But do remember that it is an in-order traversal therefore you need to always start from the leftmost leaf. Thinking in this way, you will be easier to come to use stack.

Reference: https://discuss.leetcode.com/topic/6478/iterative-solution-in-java-simple-and-readable

Code

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s[::-1]

Idea

Nothing too much…

Code

import re

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return ' '.join(re.split('\s+', s.strip())[::-1])

Idea

I do not see many advanced methods in discussion that seem better than mine. One interesting method is to reverse the whole string first. Then reverse each word (so that the order within the word becomes normal again). These actions can happen in place so no more space is required.

Code (bitwise operation)

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        res = 0
        for i in xrange(32):
            res = (res << 1) + (n & 1)
            n = n >> 1
         
        return res

Idea

Use n & 1 to get the last bit. Use n >> 1 to shift n to right one bit a time. Use res << 1 to accumulate the result.

Reference: https://discuss.leetcode.com/topic/10298/the-concise-c-solution-9ms

Code (Pythonic Cheating!)

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        b = '{:032b}'.format(n)
        return int(b[::-1], 2)

Reference: https://discuss.leetcode.com/topic/10069/python-ac-with-63ms-3lines