czxttkl

https://leetcode.com/problems/permutations/

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        res = []
        self.recur(nums, 0, res)
        return res
        
    def recur(self, nums, pos, res):
        if pos == len(nums):
            res.append(nums[:])
            
        for i in xrange(pos, len(nums)):
            nums[i], nums[pos] = nums[pos], nums[i]
            self.recur(nums, pos+1, res)
            nums[i], nums[pos] = nums[pos], nums[i]

Idea

We can observe the following process to obtain permutations:

1’s permutation = 1

{1,2}’s permutation = {1,2} and {2,1}. Essentially, it is 1+{2}’s permutation and 2+{1}’s permutation

{1,2,3}’s permutation = 1+{2,3}’s permutation, 2+{1,3}’s permutation, 3+{2,1}’s permutation.

Therefore we can obtain all the permutations by:

1. swap the first element with any element after it.
2. get the permutation of nums[1:]

We can recursively do this to get the result.

https://leetcode.com/problems/recover-binary-search-tree/

   1
  / \
 2   3
    /
   4
    \
     5

Code

import sys
# 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 __init__(self):
        self.prev = TreeNode(-sys.maxint)
        
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        brk_nodes = []
        self.inorder(root, brk_nodes)
            
        brk_nodes[0].val, brk_nodes[1].val = brk_nodes[1].val, brk_nodes[0].val
        
        
    def inorder(self, root, brk_nodes):
        def add_to_brk(prev):
            if len(brk_nodes)==0:
                brk_nodes.append(prev)
                brk_nodes.append(root)
            else:
                brk_nodes[1] = root
                    
        # traverse left            
        if root.left:
            self.inorder(root.left, brk_nodes)
            
        if self.prev.val > root.val:
            add_to_brk(self.prev)
        
        self.prev = root
        
        # traverse right
        if root.right:
            self.inorder(root.right, brk_nodes)

        

Idea

We use the property that if a BST is valid, its inorder traversal will return the data in ascending order. For example, the top tree in the following plot is a valid binary search tree. Therefore, its inorder traversal should return 13489. All elements are larger than their previous elements.

The three trees on the bottom are all invalid binary search trees, each with exactly two nodes exchanged (marked as red). You may recognize that an inorder traversal of an invalid BST has at most two places where an element is smaller than the element right before it. More specifically:

The bottom left tree: inorder traversal is 93481. 3 is smaller than 9. 1 is smaller than 8.

The bottom middle tree: inorder traversal is 13498. 8 is smaller than 9.

The bottom right tree: inorder traversal is 18439. 4 is smaller than 8. 3 is smaller than 4.

Using this rule, we implement our code whenever we find previous visited node has larger value than the current node’s value. Whenever we find such node and the current broken node list is empty, we add the previous element and the current element together, although the current element may or may not be the broken node. (Line 27-28) But writing in this way will help us deal with the cases when the inorder traversal only contains one misplacement of number (e.g., the bottom middle tree in the plot).

Since we at most call O(N) recursive calls of `self.inorder()` function, the space complexity is O(N). The time complexity is O(N) because in the worst case you need to traverse all elements before you determine the two broken nodes.

Reference

The same idea applied in this post: https://leetcode.com/discuss/13034/no-fancy-algorithm-just-simple-and-powerful-order-traversal
This problem which is more space efficient: https://leetcode.com/discuss/26310/detail-explain-about-morris-traversal-finds-incorrect-pointer

https://leetcode.com/problems/sliding-window-maximum/

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Code

from collections import *
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        # deque of (idx, val)
        q = deque()
        for i,v in enumerate(nums):
            while q and q[0][0] < i-(k-1):
                q.popleft()
            while q and q[-1][1] < v:
                q.pop()
            q.append((i, v))
            if i >= k-1:
                res.append(q[0][1])
        return res

Idea

An O(N) time complexity algorithm. Each element is appended to and popped out of the deque at most one time. Idea can be found here: https://leetcode.com/discuss/46578/java-o-n-solution-using-deque-with-explanation

https://leetcode.com/problems/multiply-strings/

Refer Idea here:

https://leetcode.com/discuss/33951/ac-solution-in-java-with-explanation

Refer Python Code here:

https://leetcode.com/discuss/50707/simple-python-solution-18-lines

Updated 2016-10-31:

Actually this problem can be solved elegantly. 

Code

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        m, n = len(num1), len(num2)
        pos = [0] * (m+n)

        for i in xrange(m-1, -1, -1):
            for j in xrange(n-1, -1, -1):
                d1, d2 = int(num1[i]), int(num2[j])
                sum = d1 * d2 + pos[i+j+1] 
                pos[i+j] += sum/10
                pos[i+j+1] = sum % 10

        res = ''
        for p in pos:
            if not (not res and not p):
                res += str(p)

        return res if res else '0'

Idea

Don’t worry about pos[i+j] += sum/10 (line 15) will become greater than 10. It will ultimately be taken mod when smaller i or j is traversed.

Reference: https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/2

Pow(x, n)

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n==0:
            return 1
        
        tmp = self.myPow(x, abs(n)/2)
        tmp = tmp * x * tmp if n%2 else tmp * tmp
        return tmp if n > 0 else float(1)/tmp 

Idea

Please see similar idea at https://czxttkl.com/?p=1000

Idea

As the plot shows, we have a linked list with a cycle. Suppose it has 1-based index. Head has index `h`. The entry of the cycle has index `e`. We reuse the code from the previous code in which we have a slow pointer and a fast pointer (traversing the list twice as fast as the slow pointer.) The point where the fast and the slow pointer meet has index `m`. We also set the length of the cycle as C.

When the fast and the slow pointers meet:

• the number of the nodes the slow pointer has passed: e + (m-e) + n1*C
• the number of the nodes the fast pointer has passed: e + (m-e) + n2*C
• We also know that 2(e+(m-e)+n1*C) = e+(m-e)+n2*C, because the fast pointer travels twice as fast as the slow pointer.

By canceling same terms on both sides of the equation, we finally get:

e = C-(m-e) + n3*C

where n3 is a non-negative integer unknown and unimportant to us. C-(m-e) is the distance between the meeting point and the cycle entry along the direction of the linked list. (See the red path in the plot below).

Now it becomes easy to find the value of `e`. You now create a new pointer, `p`, starting from head. Let the slow pointer and `p` travel one node by one node until the two meets. The point where they meet should be the entry of the cycle.

Code

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        
        slow = fast = head 
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:       # Find cycle
                p = head
                while p != slow:
                    p = p.next
                    slow = slow.next
                return slow
        
        return None

Reference

https://leetcode.com/discuss/16567/concise-solution-using-with-detailed-alogrithm-description

https://leetcode.com/problems/kth-largest-element-in-an-array/

Code 1 (Using partition idea from quicksort with O(N) / O(N^2) time complexity on average/ worst case and O(1) space. Please see reference on complexity analysis.)

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return -1
        
        left, right = 0, len(nums)-1
        while True:
            pos = self.partition(nums, left, right)
            if pos == k-1:
                return nums[pos]
            elif pos < k-1:
                left = pos+1
            else:
                right = pos-1    

    def partition(self, nums, left, right):
        # always pick nums[left] as pivot
        pivot = nums[left]
        p1, p2 = left+1, right
        while p1 <= p2:
            if nums[p1]<pivot and nums[p2]>pivot:
                nums[p1], nums[p2] = nums[p2], nums[p1]
                p1, p2 = p1+1, p2-1
            if nums[p1] >= pivot:
                p1 += 1
            if nums[p2] <= pivot:
                p2 -= 1
        
        nums[left], nums[p2] = nums[p2], nums[left]
        return p2

s = Solution()
print s.findKthLargest([7,6,5,4,3,2,1], 5)

The function `partition` puts the numbers smaller than `nums[left]` to its left and then returns the new index of `nums[left]`. The returned index is actually telling us how small `nums[left]` ranks in nums. 

Code 2 (Using a heap of size k with O(NlogK) time complexity and O(K) space complexity. ):

from heapq import *
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return -1
        
        h = []
        for i in xrange(len(nums)):
            if len(h) < k:
                heappush(h, nums[i])
            else:
                if h[0] < nums[i]:
                    heappop(h)
                    heappush(h, nums[i])

        return h[0]

Idea

In Python heapq, heap is a min-heap. Therefore, h[0] is always the smallest element in the heap and heappop always pops the smallest element. heappop and heappush takes O(logK) time complexity therefore the total time bound is O(NlogK).

Reference:

https://leetcode.com/discuss/38336/solutions-partition-priority_queue-multiset-respectively

https://leetcode.com/problems/binary-tree-level-order-traversal/

    3
   / \
  9  20
    /  \
   15   7

[
  [3],
  [9,20],
  [15,7]
]

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 levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(root, 0, res)
        return res
    
    def dfs(self, root, level, res):
        if root:
            if len(res)<level+1:
                res.append([])
            res[level].append(root.val)
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level+1, res)
        

Idea

Similar to previous post. 

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

    3
   / \
  9  20
    /  \
   15   7

[
  [15,7],
  [9,20],
  [3]
]

Code (Using dfs 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 levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(root, 0, res)
        return res
    
    def dfs(self, root, level, res):
        if root:
            if len(res) < level+1:
                res.insert(0, [])
            res[~level].append(root.val)
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level+1, res)

Code (Using bfs + deque)

from collections import *
# 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 levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        q = deque([(root, 0)])
        while q:
            node, level = q.popleft()
            if node:
                if len(res) < level+1:
                    res.insert(0, [])
                res[~level].append(node.val)
                q.append((node.left, level+1))
                q.append((node.right, level+1))
                
        return res        

Idea

Either for dfs or bfs, you make sure that the elements more leftmost in the same level will be visited earlier than the elements more rightmost in that level. Here `~level` is equivalent to `-level-1`. (ref: http://stackoverflow.com/questions/8305199/the-tilde-operator-in-python)