[Leetcode] 334. Increasing Triplet Subsequence

This problem reminds me of the fancy version of longest increasing subsequence problem ($O(n\log n)$ solution).

Let's look at an example array: 1, 2, -1, 1, -2, 3. When we go through the first two element, we are all good. Then, we encounter -1, here we face a decision, should we update the current minimum to -1?

Let's see why we should and why we shouldn't. -1 is a safer move than 1, what if later our solution is -1, 0, 1? Then we definitely want to update it. However, you might say, if we update it to -1, then 2 shouldn't be in our solution anymore, according to the "subsequence" rule.

Well, the answer is YES, but we only update the minimum, keeping the second minimum (which is 2 here).The argument is as following: when we keep the second minimum (call it min2), this means that we only count increasing when the next value is greater than min2. You see, by changing min1 to a smaller value, it doesn't really affect the decision we are going to make about adding an increasing element. However, if we see the next value is smaller than min2 but greater than min1, we then want to update min2.

In this way, we always keep track the safest possible value yet maintain the order we have for now.

In actual implementation, I used a stack instead of min1, min2. It turned out to be much easier to handle. Well, who knows such a seeming simple question took me good two hours to think through - this kind of question is very tricky.

---

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

---

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 3: return False
        
        counter = 1
        stack = []
        for i in nums:
            if len(stack) == 0:
                stack.append(i)
            elif i < stack[0]:
                stack[0] = i
            elif len(stack) == 1 and i > stack[0]:
                stack.append(i)
            elif len(stack) == 2 and stack[0] < i < stack[1]:
                stack[1] = i
            elif len(stack) == 2 and i > stack[1]:
                return True
        return False

[Leetcode] 164. Maximum Gap

A really smart solution using pigeon hole principle and bucket sort...

---

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

---

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        min_v, max_v = min(nums), max(nums)
        if min_v == max_v: return 0
        
        buckets = [[] for _ in range(len(nums)+1)]
        for num in nums:
            bkt = (num - min_v) * len(nums) / (max_v - min_v)
            buckets[bkt].append(num)
        
        i = 0
        res = 0
        while i < len(buckets) - 1:
            k = i + 1
            while len(buckets[k]) == 0:
                k = k + 1
            res = max(res, min(buckets[k]) - max(buckets[i]))
            i = k
        return res

[MOOC] Implement TrieMatching

This is the third problem in assignment 1 for this class. It has been a long time since I worked on the first problem. I was confused why we have to model the trie as the graph where node is the number, edge the alphabet. Why can't we model it where node is the alphabet?

An counter-example will be: Consider a pattern 'ATAC', and we want to see if it matches to 'ATAT'. If we model the pattern as the first graph representation, it will be {'A': ['T', 'C'], 'T': ['A'], 'C': ['$']}. Then we will say 'ATAT' matches 'ATAC', which is obviously wrong.

---

Here is the code.

def solve (text, n, patterns):

    result = []
    # write your code here
    trie = build_trie(patterns)
    for i in range(len(text)):
        if match_pattern(text[i:], trie):
            result.append(i)
    return result

def build_trie(patterns):
    """Build trie for patterns"""
    trie = {0: {}}
    counter = 1
    for p in patterns:
        p = p + '$'
        current_node = 0
        for c in p:
            if c in trie[current_node]:
                current_node = trie[current_node][c]
            else:
                trie[current_node][c] = counter
                trie[counter] = {}
                current_node = counter
                counter += 1
    return trie

def match_pattern(text, trie):
    cur_node = 0
    for ch in text:
        if ch in trie[cur_node]:
            cur_node = trie[cur_node][ch]
            if '$' in trie[cur_node]:
                return True
        else:
            return False
    if '$' in trie[cur_node]:
        return True
    else:
        return False

[Leetcode] Sudoku Solver

Okay, this is a pretty classical backtracking problem. There are some details of writing recursion in python that I can't say I fully understand.

---

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

---

I referred to this post to finally get my program running. One thing I did not do is to "return True/False", but handled it like permutation that kind of questions. I do think "return True/False" make sense, but I don't know why I did not think it necessary.

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        
        self.solve(board, 0, 0)
    
    def solve(self, board, i, j):
        
        def candidates(i, j):
            not_available = []
            for x in range(9):
                if board[i][x] != '.':
                    not_available.append(board[i][x])
                if board[x][j] != '.':
                    not_available.append(board[x][j])
            grid_x, grid_y = i / 3, j / 3
            for x in (0, 1, 2):
                for y in (0, 1, 2):
                    if board[grid_x * 3 + x][grid_y * 3 + y] != '.':
                        not_available.append(board[grid_x * 3 + x][grid_y * 3 + y])
            return [i for i in '123456789' if i not in not_available]
        
        if i == 9: 
            return True
        elif j == 9:
            return self.solve(board, i+1, 0)
        else:            
            if board[i][j] == '.':
                cands = candidates(i, j)
                if not cands:
                    return False
                for cand in cands:
                    board[i][j] = cand
                    if self.solve(board, i, j + 1):
                        return True
                    board[i][j] = '.'
                return False
            else:
                return self.solve(board, i, j+1)

[Leetcode] Smallest Range

This is a smart use of heap.

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.

class Solution(object):
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        h = []
        max_v = -10**5 - 1
        min_v = 10**5 + 1
        for i, num in enumerate(nums):
            h.append([num[0], i, 0])
            if max_v < num[0]: max_v = num[0]
            if min_v > num[0]: min_v = num[0]
        res = [min_v, max_v]
        
        heapq.heapify(h)
        
        while True:
            v, list_index, element_index = heapq.heappop(h)
            if element_index == len(nums[list_index]) - 1:
                return res
            heapq.heappush(h, [nums[list_index][element_index+1], list_index, element_index+1]) 
            if nums[list_index][element_index+1] > max_v:
                max_v = nums[list_index][element_index+1]
            if max_v - h[0][0] < res[1] - res[0]:
                res = [h[0][0], max_v]

[Leetcode] 131. Palindrome Partitioning

Well, doing leetcode problems can be addictive - I used to go to Facebook everyday - not any more and I don't feel missed at all. Now, somehow I must do some leetcode problems, otherwise I just feel wrong. It sometimes gets hard and frustrating. But I guess as I read it somewhere, in our nature human beings just love something bitter, like beer, coffee, as well as challenges (but have to be meaningful and able to make progress and intellectually fulfilling, at least for me).

---

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

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

This problem is similar to subset problem, my solution is not the "optimal" one, but very intuitive.

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if len(s) == 0: return [[]]
        if len(s) == 1: return [[s]]
        
        res = []
        for i in range(1, len(s)+1):
            part1 = s[:i]
            part2 = s[i:]
            #print part1, part2
            if part1 == part1[::-1]:
                tmp_res = self.partition(part2)
                #print tmp_res
                for r in tmp_res:
                    res.append([part1] + r)
        return res

[Leetcode] 145. Binary Tree Postorder Traversal

This is not a hard problem compared to some really hard ones. The key is to flag every node, if first in stack, 1, if all its children are in the stack, mark it as 2. Later, when encounter a node, if its flag is 1, then we push its children in the stack and mark it as 2; if it's 2, then we pop it and record the result. The order to put the children? First right, then left --> then we are able to see left first and then the right.

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

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

1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        visited = {}
        stack = [root]
        visited[root] = 1
        res = []
        
        is_leaf = lambda node: not node.left and not node.right
        
        while stack:
            top = stack[-1]
            if visited[top] == 2 or is_leaf(top):
                top = stack.pop()
                res.append(top.val)
            else: 
                if top.right:
                    stack.append(top.right)
                    visited[top.right] = 1
                if top.left:
                    stack.append(top.left)
                    visited[top.left] = 1
                visited[top] = 2
        return res