czxttkl

Code

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        lp, rp = 0, len(height)-1
        max_area = 0
        while lp < rp:
            max_area = max(max_area, min(height[lp],height[rp]) * (rp-lp))
            if height[lp] < height[rp]:
                lp += 1
            else:
                rp -= 1
        return max_area

Idea

The time complexity is O(N). The idea is that if height[lp] < height[rp], then the bottleneck to determine the container volume is height[lp]. That means the container formed by height[lp] and height[rp'] for any rp' < rp must have smaller volume than that formed by height[lp] and height[rp]. In this case, lp should move to right.

You can easily deduct the other case: height[rp] < height[lp].

Reference: https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm

Code

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lp, rp = 0, len(s)-1
        while lp < rp:
            while lp < rp and not s[lp].isalnum():
                lp += 1
            while lp < rp and not s[rp].isalnum():
                rp -= 1
            if s[lp].lower() != s[rp].lower():
                return False
            lp += 1
            rp -= 1
        
        return True

Idea

Not much to say. First time to use string.isalnum().

[
  ["aa","b"],
  ["a","a","b"]
]

Code

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.recur(0, s, [], res)
        return res

    def recur(self, cur_idx, s, splits, res):
        if cur_idx == len(s):
            res.append(list(splits))
            return

        for i in xrange(cur_idx + 1, len(s)+1):
            if self.isPalindrome(s[cur_idx:i]):
                splits.append(s[cur_idx:i])
                self.recur(i, s, splits, res)
                splits.pop()

    def isPalindrome(self, ss):
        return ss == ss[::-1]

Idea

You progressively try every split position in the string. Check whether substring between the last split position to current split position is palindrome. If so, recursively try the rest of split positions, with the current substring being added to splits.

Reference: https://discuss.leetcode.com/topic/10955/clean-c-backtracking-solution 

https://leetcode.com/problems/pascals-triangle/

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Code

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        
        res = [[1]]
        for i in xrange(2, numRows+1):
            new_row = [0] * i
            for j in xrange(i):
                if j == 0:
                    new_row[j] = 1
                elif j == i-1:
                    new_row[j] = 1
                else: 
                    new_row[j] = res[-1][j-1] + res[-1][j]
            res.append(new_row)
            
        return res   

Idea

Each element is the sum of adjacent elements in the above line. That’s how Pascal’s Triangle is defined: https://en.wikipedia.org/wiki/Pascal%27s_triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Code 

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0:
            return 0
        
        if len(triangle) == 1:
            return triangle[0][0] 
        
        last_level_sum = {0:triangle[0][0]}
        for i in xrange(1, len(triangle)):
            this_level_sum = {}
            for j in xrange(len(triangle[i])):    
                if j == 0:
                     this_level_sum[j] = last_level_sum[0] + triangle[i][j]
                elif j == len(triangle[i])-1:
                     this_level_sum[j] = last_level_sum[j-1] + triangle[i][j]
                else:
                     this_level_sum[j] = min(last_level_sum[j], last_level_sum[j-1]) + triangle[i][j]
        
            last_level_sum = this_level_sum         

        return min(last_level_sum.values())

Idea

You go from top to bottom. Record the minimum sum until every layer. If you use a bottom-up DP, the solution can be more elegant.

Reference:

https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle/2

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

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

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Code

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None: 
            return
        
        pre = root
        while pre.left:
            pre_bakup = pre

            while pre:
                pre.left.next = pre.right
                if pre.next:
                    pre.right.next = pre.next.left
                pre = pre.next

            pre = pre_bakup.left

Idea

You traverse nodes in a zigzag-like path. For every node being visited, you set its left child’s next to right child. If the node itself has next node, then its right child should also point to the node’s next node’s left child.

Below is the traversal path of pre:

The idea uses O(1) space and O(N) time, where N is the number of nodes in the binary tree.

Reference: https://discuss.leetcode.com/topic/2202/a-simple-accepted-solution

Code (Using BFS, space complexity is O(N))

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

from collections import *

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return

        q = deque([(root, 0)])
        while q:
            if len(q) > 1:
                # if two nodes have the same level
                if q[0][1] == q[1][1]:
                    q[0][0].next = q[1][0]
            
            n, lvl = q.popleft()
            
            if n.left and n.right:
                q.append((n.left, lvl+1))
                q.append((n.right, lvl+1))            

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 countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0        

        height_left, height_right = -1, -1
        
        node = root
        while node:
            height_left += 1 
            node = node.left
       
        node = root
        while node:
            height_right += 1
            node = node.right
       
        if height_left == height_right:
            return 2**(height_left+1) - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Idea

height_left is the number of edges between root and its leftmost leaf. height_right is the number of edges between root and its rightmost leaf. If they are the same mean, that means the last level is full. Therefore we can return 2**(height_left+1)-1 by the property of binary tree. If height_left does not equal to height_right, then we have to recursively count the nodes in the left and right subtree.

The time complexity if O((logn)^2). This is because you need O(logn) to calculate height_left/height_right. After that, the worst case is that you need to recursively call self.countNodes(root.left) and self.countNodes(root.right). This happens no more than O(logn) times.

Reference:

https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

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 __init__(self):
        self.prev = None
        
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None: return
        self.flatten(root.right)
        self.flatten(root.left)
        # self.prev is root's left subtree's root
        root.right = self.prev
        root.left = None
        self.prev = root   

Idea

Create a variable self.prev, which records the current node (root)’s left subtree’s root. Overall it utilizes a post-order traversal. The algorithm first traverses right subtree then left subtree and finally adjusts the current root’s left and right subtree.

Reference: https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share/2

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 flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        while root:
            ln = root.left
            if ln is not None:
                # find the right-most element of the left subtree 
                while ln.right:
                    ln = ln.right
                ln.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Idea

Iterative way. Time complexity is O(n) since every node can be set as root and ln no more than once.

Reference: https://discuss.leetcode.com/topic/3995/share-my-simple-non-recursive-solution-o-1-space-complexity

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

Code

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not str: 
            return True

        diff = 1
        for n in preorder.split(','):
            diff -= 1
            if diff < 0:
                return False
            if n != '#':
                diff += 2

        return diff == 0
     

Idea

Calculate the difference between in-degree and out-degree. See https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution 

Code

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not preorder: 
            return True
        
        stk = []
        nodes = preorder.split(',')
        for n in nodes:
            while stk and stk[-1] == '#' and n == '#':
                stk.pop()
                if not stk:
                    return False
                stk.pop()
            stk.append(n)
  
        return len(stk) == 1 and stk[0] == '#'

Idea

When you see two consecutive “#” characters (one on the top of stack and the other as the current node `n`), that means a subtree with two leaves has been scanned. Pop the subtree’s root as well as the ‘#’ on the stack and replace the topmost element on the stack with “#”.

See https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation and https://discuss.leetcode.com/topic/35973/java-intuitive-22ms-solution-with-stack

Code (BFS)

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 maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0

        q = deque([(root, 1)])
        max_lvl = 1

        while q:
            node, lvl = q.popleft()
            max_lvl = max(max_lvl, lvl)
            if node.left is not None: 
                q.append((node.left, lvl+1))
            if node.right is not None:
                q.append((node.right, lvl+1))
            
        return max_lvl

Code (DFS)

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 maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1 if root is not None else 0