czxttkl

https://leetcode.com/problems/unique-paths-ii/

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

My Code:

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if len(obstacleGrid)==0 or len(obstacleGrid[0])==0:
            return 0
        
        ways = [0] * len(obstacleGrid[0])        
        ways[0] = 1 
        for j in xrange(0, len(obstacleGrid)):
            for i in xrange(0, len(obstacleGrid[0])):
                if obstacleGrid[j][i]:
                    ways[i] = 0
                elif i:  # only handle cells after the first column
                    ways[i] = ways[i] + ways[i-1] 
        
        return ways[-1]

Idea:

Following my previous post, you only need 1D array to store intermediate number of ways reaching `cell[j][i]`. Other than that, the only difference is that you need to handle obstacle. It is intuitive to do that though: you set `ways[i]=0` if you see an obstacle, i.e., no way can reach a cell without obstacle.

https://leetcode.com/problems/unique-paths/

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m <0 or n < 0:
            return 0
        
        ways = [[0] * n for _ in xrange(m)]
        for i in xrange(0, n):
            ways[0][i] = 1
        for j in xrange(0,m):
            ways[j][0] = 1
        
        for j in xrange(1,m):
            for i in xrange(1,n):
                ways[j][i] = ways[j-1][i] + ways[j][i-1]
        
        return ways[-1][-1]
        

Idea

Use very naive idea of Dynamic Programming by creating an m*n matrix ,`ways`. Each cell records the number of ways that can reach there. At the end, just return `ways[-1][-1]`. This requires `O(m*n)` time and `O(m*n)` space.

The space can be reduced by observing that you are either updating `ways` row by row or column by column. This means you only need to keep O(m) or O(n) space in memory all the time. Below is the updated code (not in Python) (https://leetcode.com/discuss/38353/0ms-5-lines-dp-solution-in-c-with-explanations):

class Solution {
    int uniquePaths(int m, int n) {
        if (m > n) return uniquePaths(n, m);
        vector<int> cur(m, 1);
        for (int j = 1; j < n; j++)
            for (int i = 1; i < m; i++)
                cur[i] += cur[i - 1]; 
        return cur[m - 1];
    }
}; 

Another idea is to derive `ways[-1][-1]` using combination formula: you always need `n+m-2` steps to reach (m,n) from (1,1) by either going down or right. Among the `n+m-2` steps, you need exactly `m-1` steps going down. Therefore ways[-1][-1] = $latex C_{n+m-2}^{m-1}$. The code implementing this idea (https://leetcode.com/discuss/9110/my-ac-solution-using-formula):

class Solution {
    public:
        int uniquePaths(int m, int n) {
            int N = n + m - 2;// how much steps we need to do
            int k = m - 1; // number of steps that need to go down
            double res = 1;
            // here we calculate the total possible path number 
            // Combination(N, k) = n! / (k!(n - k)!)
            // reduce the numerator and denominator and get
            // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i;
            return (int)res;
        }
    };

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

My original code:

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if nums is None or len(nums) == 0:
            return None
        if len(nums)== 1:
            return nums[0]
        
        
        left, right = 0, len(nums)-1
        
        while left < right-1:
            mid = (left+right)/2
            if nums[left] < nums[mid] and nums[mid] > nums[right]:
                left = mid
            elif nums[left] > nums[mid] and nums[mid] < nums[right]:
                right = mid
            else:
                left = right = 0
                
        return min(nums[left], nums[right])

My original idea:

A rotated array has a property: if you do binary search by having `left`, `mid` and `right` pointers, if  nums[left] < nums[mid] and nums[mid] > nums[right], that means the left part is intact and the minimum has been rotated to `nums[mid:right+1]`. Similarly, if nums[left] > nums[mid] and nums[mid] < nums[right]  , that means the right part is intact and the minimum has been rotated to `nums[0:mid+1]`. However, in the code above, I didn’t set `left` and `right` to `mid+1` and `mid-1` as in standard binary search because I was afraid that after excluding the current element `nums[mid]`, I may let the whole subarray being without rotation. I thought my algorithm will not work if the array is in a correct format. For example, if we always set `left` to `mid+1`:

input: [3412]

iteration 0: left=0, right=3, mid=1

iteration 1: left=2, right=3. Now nums[left:right+1] is [12] which has correct order

But later I find I can safely set `left` and `right` to `mid+1` and `mid` to not exclude the minimum in `nums[left:right+1]`. As long as the minimum is in `nums[left:right+1]`, the algorithm can finally find the minimum. This can be done by:

setting `left` to mid+1 if nums[mid] > nums[right]. 

setting `right` to mid if nums[left] > nums[mid].

So the more concise code can be (https://leetcode.com/discuss/63514/9-line-python-clean-code): 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        j = len(nums) - 1
        while i < j:
            m = i + (j - i) / 2
            if nums[m] > nums[j]:
                i = m + 1
            else:
                j = m
        return nums[i]

https://leetcode.com/problems/zigzag-iterator/

v1 = [1, 2]
v2 = [3, 4, 5, 6]

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

My verbose code:

class ZigzagIterator(object):

    def __init__(self, v1, v2):
        """
        Initialize your data structure here.
        :type v1: List[int]
        :type v2: List[int]
        """
        self.v1 = v1
        self.v2 = v2
        self.pointer = 0
        if len(v1) != 0:
            self.l = 0  
        else:
            self.l = 1
        self.x = 0

    def next(self):
        """
        :rtype: int
        """
        n = None
        if self.l == 0:
            n = self.v1[self.x]
            if self.x < len(self.v2):
                self.l = 1
                # keep self.x same
            else:
                # keep self.l same
                self.x += 1
        else: 
            n = self.v2[self.x]
            if self.x < len(self.v1) - 1:
                self.l = 0
                self.x += 1
            else:
                self.x += 1
        
        self.pointer += 1
        return n
        
        
    def hasNext(self):
        """
        :rtype: bool
        """
        return self.pointer < len(self.v1)+len(self.v2)

# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())

However, there are more elegant codes which leverage Python generator (https://leetcode.com/discuss/57997/python-o-1-space-solutions):

class ZigzagIterator(object):

    def __init__(self, v1, v2):
        self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))
        self.n = len(v1) + len(v2)

    def next(self):
        self.n -= 1
        return next(self.vals)

    def hasNext(self):
        return self.n > 0

Here, self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))  uses `itertools.count()` as a generator to generate infinite integer `i`. For each `i`, if `i < len(v)` then the list `self.vals` will add v[i]. This essentially constitutes a zigzag output in the initialization. However, since `itertools.count()` is just a generator, `self.vals` don’t occupy the memory: every element in `self.val` will be yielded whenever you call `next(self.vals)`. 

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

Code:

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

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.pushAll(root)
        print [s.val for s in self.stack]

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.stack 

    def next(self):
        """
        :rtype: int
        """
        n = self.stack.pop()
        self.pushAll(n.right)
        return n.val
        
    def pushAll(self, node):
        while node:
            self.stack += [node]
            node = node.left
        
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

Idea

First, load `self.stack` from root to the leftmost leaf. This requires O(log n) memory and time. Then, when you call `next()`, you pop the top element from `self.stack`, which is guaranteed to be smallest. Before you return this, you also need to load this element’s right child’s path to its leftmost child into `self.stack`. To do so, you call `self.pushAll(node.right)`. 

https://leetcode.com/problems/insert-interval/

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not intervals:
            return [newInterval]
        strt_idx = self.binary_search(intervals, newInterval.start)        
        end_idx = self.binary_search(intervals, newInterval.end)
        
        if strt_idx ==0 and newInterval.end < intervals[0].start:    # Condition 1
            intervals[0:1] = [newInterval, intervals[0]]
        elif newInterval.start > intervals[strt_idx].end:            # Condition 2
            intervals[strt_idx:end_idx+1] = [intervals[strt_idx], 
                                             Interval(newInterval.start, max(intervals[end_idx].end, newInterval.end))]
        else:                                                        # Condition 3
            intervals[strt_idx:end_idx+1] = [Interval(min(intervals[strt_idx].start, newInterval.start), 
                                             max(intervals[end_idx].end, newInterval.end))]
        return intervals

    def binary_search(self, intervals, t):
        left, right = 0, len(intervals)-1
        while left <= right:
            mid = (left + right) / 2
            if t > intervals[mid].start:
                left = mid + 1
            elif t < intervals[mid].start:
                right = mid - 1
            else:
                return mid
        
        # return index where t >= intervals[index].start
        return left-1 if left - 1 >=0 else 0
        

Idea

Do two rounds of binary search to determine the rightmost interval in `intervals` whose start $latex \leq$ `newInterval.start`. Also determine the rightmost interval whose start $latex \leq$ `newInterval.end`. Then you have three situations to deal with:

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

Code

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        end = dict()
        max_len = 0
        start = 0
        for i,c in enumerate(s):
            if len(end) <2:
                end = i
            else: # len(end) == 2
                if c in end.keys():
                    end = i
                else:
                    end_early_c = min(end.keys(), key=lambda x: end[x])
                    start = end[end_early_c] + 1
                    end.pop(end_early_c, None)
                    end = i
                
            l = i - start + 1
            if l > max_len:
                max_len = l
                
        return max_len

Idea

Use a dictionary `end` to record at which indices the previous two distinct characters are last seen. Then, when a new character appears which are not in `end.keys()`, the substring satisfying our rules can only start after one of the two existing characters, whichever is seen more earlier.

for example, `aaabbbaac`. When you see `c`, you can only start after `bb`.  

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

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 kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        for v in self.inorder(root):
            if k == 1:
                return v
            else:
                k -= 1
                
    def inorder(self, root):
        if root:
            for v in self.inorder(root.left):
                yield v
            yield root.val
            for v in self.inorder(root.right):
                yield v
        

Idea 

We use depth first in order traverse of BST to read element from the smallest to the largest. We can count when each element is read, until we read k element. Here we use `yield` instead of `return`  in the inorder function to be more memory thrifty. 

Locating the smallest element will take O(log N) time, plus you read O(k) element before you return.

Reference

https://leetcode.com/discuss/44731/pythonic-approach-with-generator

https://leetcode.com/problems/merge-intervals/

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        r = []
        for i in sorted(intervals, key=lambda x: x.start):
            if r and i.start <= r[-1].end:
                r[-1].end = max(i.end, r[-1].end)
            else:
                r += [i]
        return r
        

Idea

First, sort intervals based on their start points (Achieve in O(nlogn) time). Then, one by one examining whether the current start point is behind or in front of the last effective interval’s end point. The following plot shows the specific rules for update: