[Leetcode] Combination sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

This is not a hard problem - it's quite standard to think a recursion solution. However, the recursion solution sometimes doesn't work as I expected - it turns out the "exit" condition is quite important.

One little aspect: when there is repeated elements and order doesn't matter, sort always helps to remove the duplicates.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        res = self.helper(candidates, target)
        return res
    
    def helper(self, candidates, target):
        if len(candidates) == 0: return []
        output = []
        for i, can in enumerate(candidates):
            if can > target: continue
            if i > 0 and can == candidates[i-1]: continue
            tmp_res = self.helper(candidates[i+1: ], target-can)
            if len(tmp_res) > 0:
                for tr in tmp_res:
                    output.append(tr+[can])
            if len(tmp_res) == 0: # important to determine if there is a solution or not
                if can == target:
                    output.append([can])
        return output

[Leetcode] Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

There is nothing tricky in the question. You just need to think it carefully and code it up...It feels overwhelming, but there is two points to think through:

1. What to record?
2. How to reverse a linked list given two ends?

For the first question, think about the example 4 --> 5 --> 3 --> 2 --> 1, k = 2, and the end result will be 5 --> 4 --> 2 --> 3 --> 1. Basically, we need to know when to start reversing, when to end, and in order to connect the previous piece, we also need another pointer from previous piece.

The second question is just some tricky linked list manipulation: we have a p_prev to record the previous node, and p to record the current node. When we sweeping over the p, we just point the p to p_prev and then make p as p_pre.

My code below is kinda ugly --- too long, but idea is there.

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

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k == 1:
            return head
        def reverse(h, t):
            p_prev = h
            p = h.next
            while p != t:
                p_next = p.next
                p.next = p_prev
                p_prev, p = p, p_next
            p.next = p_prev
            
        aux = ListNode(0)
        aux.next = head
        p = head
        i = 0
        prev = aux
        while p:
            if i % k == 0:
                tmp_head = p
                p = p.next
            elif i % k == k -1:
                p_next = p.next
                tmp_tail = p
                reverse(tmp_head, tmp_tail)
                tmp_head.next = p_next
                prev.next = tmp_tail
                prev = tmp_head
                p = p_next
            else:
                p = p.next
            i += 1
        return aux.next

[codeFights] FindProfession

Consider a special family of Engineers and Doctors. This family has the following rules:

• Everybody has two children.
• The first child of an Engineer is an Engineer and the second child is a Doctor.
• The first child of a Doctor is a Doctor and the second child is an Engineer.
• All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

                E
           /         \
          E           D
        /   \        /  \
       E     D      D    E
      / \   / \    / \   / \
     E   D D   E  D   E E   D

Given the level and position of a person in the ancestor tree above, find the profession of the person.
Note: in this tree first child is considered as left child, second - as right.

Example

For level = 3 and pos = 3, the output should be
findProfession(level, pos) = "Doctor".

Input/Output

• [time limit] 4000ms (py)

• [input] integer level
  The level of a person in the ancestor tree, 1-based.
  Guaranteed constraints:
  1 ≤ level ≤ 30.

My first thought is to use BFS. Why? Because when you know the last level, the next level is known. However, given how large the input might be ($2^{30}$) , it is gonna blow up the memory. My next thought is to find the pattern: it should be doable, but it turns out to be overwhelming. 

But another way, the most important way to think about a tree problem, is recursion. There is a nice relationship between last level and current level's professions: last level 1, 2, 3, 4, ... will be copied to the current level position: 1, 3, 5, 7, ... . As for 2, 4, 6, 8 ... positions in my current level, it is just the opposite. Hence the code:

def findProfession(level, pos):
    if level == 1:
        return 'Engineer'
    if level == 2:
        if pos == 1:
            return 'Engineer'
        else:
            return 'Doctor'
    if pos % 2 == 1:
        return findProfession(level - 1, (pos+1)/2)
    else:
        if findProfession(level - 1, pos/2) == 'Doctor':
            return 'Engineer'
        else:
            return 'Doctor'

[Leetcode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Whenever seeing a tree problem, always try to think recursively. However, this problem is not that easy to think a recursive solution. Why? Because, recursion usually comes like a DFS flavor, but here somehow we need to compare level-wisely. My original idea is to do a BFS, recording each level to a list and see if the list is palindrome. I think I still need to digest the following idea a little bit.

# 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 isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.helper(root.left, root.right)
    
    def helper(self, node1, node2):
        if not node1 and not node2:
            return True
        if (not node1 and node2) or (not node2 and node1):
            return False
        if node1.val != node2.val:
            return False
        return self.helper(node1.left, node2.right) and self.helper(node1.right, node2.left)

[CodeFights] firstDuplicate

A google problem.. The problem sounds very simple. The tricky part is the time and space constraint.

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

• For a = [2, 3, 3, 1, 5, 2], the output should be
  firstDuplicate(a) = 3.
  There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.
• For a = [2, 4, 3, 5, 1], the output should be
  firstDuplicate(a) = -1.

The key point is that numbers are in the range from 1 to len(a). This reminds me of another leetcode problem: First missing positive.

In FirstMissingPositive, we take advantage of the same condition "numbers are in the range from 1 to len(a)" and treat the original array as a hashmap. Whenever we encounter a out-of-place number a[i], we swap it with a[a[i]-1]. If this problem only wants to find a duplicate, this method works, However, the tricky part is that we want to find the first duplicate number for which the second occurance has the minimal index. Swapping destroys the order and is hard to recover.

The way to solve this problem is to mark the "proper index" negative. By this, take above array as an example, when we first see a[1] = 3, we mark a[a[1]-1] = a[2] as negative, if later we need to visit this index again, we know we have seen this number before.

def firstDuplicate(a):
    if not a: return -1
    for i in range(len(a)):
        proper_idx = abs(a[i]) - 1
        if a[proper_idx] < 0:
            # visited before
            return abs(a[i])
        else:
            a[proper_idx] = -a[proper_idx]
    return -1

[Leetcode] Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Last time when I attempted at this problem, I tried to find the distance between each empty room to the closest gate. I have a feeling that I re-computed many things. Take above example, when I computed (0,0) to the closest gate, I will for sure go through (1, 0), (2, 0) and then reach (3, 0) which is a gate. But, thinking this way, it's very hard to record the intermediate results and reconcile when there is a conflict. For example, (1,1)'s closest gate is not (3, 0), but (0, 2). How to decide?

It turns out thinking this problem in a flipped way can solve all these confusions in a natural way. Instead of calculating the closest gate for each room, we can start from the gate, and grow the distance field through breadth-first search (BFS). Due to the nice property of BFS, whenever we reach a empty room, then it must be the shortest distance to the gate. For example, a room is 2 steps away from gate 1, and 4 steps away from gate 2. Then when we are in the level 2, this room will be added in the queue through gate 1's path.

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        if not any(rooms): return 
        queue = []
        
        m, n = len(rooms), len(rooms[0])
        
        for i in xrange(m):
            for j in xrange(n):
                if rooms[i][j] == 0:
                    queue.append(((i, j), 0))
        queue = collections.deque(queue)
        
        # lambda function speeds up the program a lot
        is_empty = lambda x, y: 0<=x<m and 0<=y<n and rooms[x][y]>=2147483647 
        
        while queue:
            (x, y), dist = queue.pop()
            
            if is_empty(x-1, y):
                rooms[x-1][y] = dist + 1
                queue.appendleft(((x-1, y), dist+1))
            if is_empty(x+1, y):
                rooms[x+1][y] = dist + 1
                queue.appendleft(((x+1, y), dist+1))
            if is_empty(x, y-1):
                rooms[x][y-1] = dist + 1
                queue.appendleft(((x, y-1), dist+1))
            if is_empty(x, y+1):
                rooms[x][y+1] = dist + 1
                queue.appendleft(((x, y+1), dist+1))                
            

[CodeFights] ClimbingStaircase

You need to climb a staircase that has n steps, and you decide to get some extra exercise by jumping up the steps. You can cover at most k steps in a single jump. Return all the possible sequences of jumps that you could take to climb the staircase, sorted.

Example

For n = 4 and k = 2, the output should be

climbingStaircase(n, k) =
[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

There are 4 steps in the staircase, and you can jump up 2 or fewer steps at a time. There are 5 potential sequences in which you jump up the stairs either 2 or 1 at a time.

This problem is in the section of backtracking. It's very straightforward regarding to the "tree"-construction: we start from step 1 (which is the root), and each parent has k children, which represent 1, 2, ..., k steps. 

To me, I always want to practice the framework of doing backtrack. It should be straightforward, but somehow I got confused of how to frame the program. But I think this one is good:

def climbingStaircase(n, k):
    output = []
    steps = []
    helper(output, steps, k, n)
    return output
        
def helper(output, steps, k, left):
    if left == 0:
        output.append(list(steps)) # notice hard copy here
    else:
        for i in range(1, k+1):
            if i <= left:
                steps.append(i)
                helper(output, steps, k, left-i)
                steps.pop()

[Leetcode] Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Analysis:

The point of the problem is to determine if the fraction is repeating. At any point, if the remnant reappears, then we know the result is repeating. However, the repeating part may not start from the beginning of the floating part, so we used a hashmap to record the remnant and its location.

Another edge case is the negative number. `-50/8 = -7` in python. Therefore, the solution is to change to the absolute values and to add a sign in the end.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution(object): def fractionToDecimal(self, numerator, denominator): """ :type numerator: int :type denominator: int :rtype: str """ if numerator * denominator >= 0: sign = '' else: sign = '-' numerator, denominator = abs(numerator), abs(denominator) integer = sign + str(numerator/denominator) a = numerator % denominator floating, index = '', 0 hmap = {} while a!= 0 and a not in hmap: hmap[a] = index tmp_res = a * 10 / denominator a = a * 10 % denominator floating += str(tmp_res) index += 1 if a == 0: return integer + '.' + floating if floating != '' else integer else: idx = hmap[a] return integer + '.' + floating[:idx] + '(' + floating[idx:] + ')'

[Leetcode] Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

This problem is similar to k-dimensional maximum weight path or house robber problem.

For maximum weight path / house robber problem, the recurrence relationship is:

dp[n] = min {input[n] + dp[n-2], dp[n-1]}

Here, if we define dp[r][c] as minimum cost when room r is painted with color c, then the recurrence relationship will be:

dp[r][c] = min{dp[r-1][l], l!=c} + costs[r][c]

Since we have n * k subproblems, and for each subproblem, we need to calculate min{dp[r-1][l], l!=c} which is a O(k) operation. So, the overall time complexity will be O(nk^2).

However, we really don't need to re-calculate minimum for every c, we only need to know the last two minimum numbers. If the room is not painted with color that comes with the minimum cost from previous rooms, then it should choose that color. In the case that we want to see that color, then the minimum cost up to now would be for previous room, we choose the second minimum cost.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution(object): def minCostII(self, costs): """ :type costs: List[List[int]] :rtype: int """ if not any(costs): return 0 n, k = len(costs), len(costs[0]) dp = [[0 for _ in range(k)] for _ in range(n)] dp[0] = costs[0] def helper(a): return min(a), a.index(min(a)) prev_cost_min, prev_min_color = helper(dp[0]) for r in range(1, n): for c in range(k): if c != prev_min_color: dp[r][c] = prev_cost_min + costs[r][c] else: tmp_cost = [dp[r-1][j] for j in range(c)+range(c+1, k)] dp[r][c] = min(tmp_cost) + costs[r][c] prev_cost_min, prev_min_color = helper(dp[r]) return prev_cost_min

[Leetcode] Subsets

A classical problem.

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

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

And a classical solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [] output = [] self.helper(nums, 0, res, output) return res def helper(self, nums, pos, res, output): if pos == len(nums): res.append(list(output)) else: self.helper(nums, pos+1, res, output) output.append(nums[pos]) self.helper(nums, pos+1, res, output) output.pop()

但我感觉我需要再仔细想想为什么最后一步要pop，为什么append里面需要deepcopy of output list...

[Leetcode] Verify Preorder Sequence in Binary Search Tree

Problem:
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.

我的第一个想法有点类似于quick sort，数组的第一个元素，必然是BST的root，那么我现在只需要去找下一个比这个root大的元素，假设其index为i，那么从1到i-1的元素应该是BST的left subtree，而i以后的元素是right subtree。但是如果i以后的元素有比root还要小的，那么这个preorder的数组必然不是from BST。

This is very similar to quick sort procedure. Therefore, the time complexity on average is O(n log n), too slow for this problem. My code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution(object): def verifyPreorder(self, preorder): """ :type preorder: List[int] :rtype: bool """ if not preorder or len(preorder) == 1: return True first = preorder[0] for i in xrange(1, len(preorder)): if preorder[i] > first: break if i != len(preorder)-1: for j in range(i, len(preorder)): if preorder[j] < first: return False if preorder[i] > first: left = self.verifyPreorder(preorder[1:i]) if not left: return False right = self.verifyPreorder(preorder[i:]) return right elif preorder[i] < first: left = self.verifyPreorder(preorder[1:i+1]) return left

很明显，我们重复看了很多的子问题，比如the first half, we later have to re-look at it in solving self.verifyPreorder(preorder[1:i])

[Leetcode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [1,2,3].

Preorder: root - left - right. When thinking about the stack property (first in, last out), we want to push right child before the left child, so that eventually we will access left child first.

This problem is really neat, letting me see more clearly the difference between BFS (using queue) and DFS (stack). Indeed, the structure of the program below is the same as BFS, except that we used a stack here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

# 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 preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] stack = [root] res = [] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

[Leecode] Convert Sorted List to Binary Search Tree

Problem statement: 
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:
1. Two pointers - fast and slow to find the middle point of linked list (notice the handling at the middle part as well as the fast pointer)
2. Recurse on the left half and the right half of the linked list

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None # 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 sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ # base case if not head: return None if not head.next: return TreeNode(head.val) # find the middle pointer fast = head.next slow = head while fast and fast.next and fast.next.next: slow = slow.next fast = fast.next.next # slow is the end of the left, slow.next is root, slow.next.next is right lroot = slow.next lright = slow.next.next slow.next = None # recursion on the first half and the second half root = TreeNode(lroot.val) right = self.sortedListToBST(lright) left = self.sortedListToBST(head) root.left, root.right = left, right return root