czxttkl

https://leetcode.com/problems/3sum/

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Code

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums) < 3:
            return []
            
        res = []
        nums.sort()
        
        for i in xrange(len(nums)-2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            
            target = -nums[i]
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == target:
                    res.append([nums[i], nums[left], nums[right]])
                    left_val = nums[left]
                    right_val = nums[right]
                    left += 1
                    right -= 1
                    while left < right and nums[left]==left_val:
                        left += 1
                    while right > left and nums[right]==right_val:
                        right -= 1
                elif nums[left] + nums[right] < target:
                    left = left + 1
                else:
                    right = right - 1
                    
        return res
                

Idea:

You sort the array first in O(nlogn) time. Then you have a pointer `i` starting from 0 and ending at len(nums)-3. The number pointed by `i` denotes the candidate for the first number in a 3sum triplet. You want to run a 2sums algorithm on all elements on the right of `i` with target equal to `-nums[i]`: you create a `left` pointer right next to `i` and a `right` pointer at the end of nums. You move `left` to right or move `right` to left according to `nums[left] + nums[right] ? target`. You should take care of duplication, either for `i` (line 14 -15) and for `left` and `right` (line 27-30)

The time complexity is O(N^2) and space complexity is O(1).

Reference:

Code:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for idx, vlu in enumerate(nums):
            idx2 = dict.get(target - vlu, -1)
            if idx2 < 0:
                dict[vlu] = idx
            else:
                return [idx2+1, idx+1]

Idea:

O(N) space. O(N) time. Read my another post on 3Sum, which sorts array in place in O(nlogn) time but costs no additional space. (3Sum algorithm takes O(N^2) overall)

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

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

Code

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        
        left, right = 0, len(nums)-1                    
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return mid
            if nums[left] <=nums[mid]:
            # left ok
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
            # right ok
                if nums[right] >= target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Idea

It is a variant of binary search. You have `left`, `right` and `mid` three pointers. You only return exact index of `mid` if you find `nums[mid] == target`. Otherwises you return -1. To identify whether you need to search in `[left, mid-1]` or `[mid+1, right]`, you need to determine `nums[left] <= nums[mid]` (line 16). If it is True, that means `nums[left:mid]` is intact from rotation. If it is  False, that means `nums[mid+1:right]` is intact by rotation. Then you determine you need to search in the intact part of the rotated part (line 18 and 24).

Reference:

https://leetcode.com/problems/closest-binary-search-tree-value-ii/

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 closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        stk1 = []
        stk2 = []
        self.inorder(root, False, target, stk1)
        self.inorder(root, True, target, stk2)
        
        res = []
        for _ in xrange(k):
            if not stk1:
                res.append(stk2.pop())
            elif not stk2:
                res.append(stk1.pop())
            else:
                if abs(stk1[len(stk1)-1] - target) < abs(stk2[len(stk2)-1] - target):
                    res.append(stk1.pop())
                else:
                    res.append(stk2.pop())
        return res
        
    def inorder(self, root, reverse, target, stk):
        if root is None:
            return 
        self.inorder(root.right, reverse, target, stk) if reverse else self.inorder(root.left, reverse, target, stk)
        # The first inequality is less than or equal, the second inequality must be larger than (without equal).
        # Or the first is less than, the second is larger than or equal to
        if not reverse and target <= root.val:
            return
        if reverse and target > root.val:
            return
        stk.append(root.val)
        self.inorder(root.left, reverse, target, stk) if reverse else self.inorder(root.right, reverse, target, stk)

        

Idea:

If we do inorder depth-first traverse (left->root->right) of a binary search tree, we can get an ascending sorted list of elements. If we do reverse inorder depth-first traverse (right->root->left) of a binary search tree, we can get a descending sorted list.

So we create two stacks to store. Stack 1 records the ascending sorted list but it terminates before the element which <= target. (line 40). Stack 2 records the descending sorted list but it terminates at the element which < target. (line 42). (You can also make the first inequality with less than, and the second inequality with larger than or equal to. The main point is that the two stacks shouldn’t contain any element at the same time.)

At last you peek at stack 1 and stack 2. You need to pop element into `res` list from whichever stack has the top element closer to target.

Reference:

https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks

https://leetcode.com/problems/regular-expression-matching/

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Code 1:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        
        if len(p)>=2 and p[1] == "*":
            return  s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])         
        else:
            return s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])

Reference: http://xiaohuiliucuriosity.blogspot.com/2014/12/regular-expression-matching.html

Idea:

This is a recursive method.  You start to “consume” `p` and `s` until `p` can be consumed to empty.  If at this moment `s` happens to be consumed to empty also, your match is successful.

Everytime you look at the first and the second character in `p`. There are two situations:

If you find the second character in `p` is “*”. This means, on the left of “*” in p, there is another character, `x`, for example:

p:   x*......

s:   ...............

Then, there are three conditions:

a) `x` is not `.` and the first position of `s` is not the same as `x`. Then you must skip `x*` in p to  continue to match `s`.  So you rely on `isMatch(s, p[2:])`.

b) `x` is not `.` and the first position of `s` is the same as `x`. Then whether `p` matches `s` will depend on ‘isMatch(s[1:], p)’ or `isMatch(s, p[2:])`. You can imagine that the following match will continue to try if the `s`’s following substring  starts with `x*`. 

c) `x` is `.`. Then whether `p` matches `s` will also depend on `isMatch(s[1:], p)`

If you find the second character in `p` is not “*”, then a successful match will only happen if the first character of `p` and `s` are the same and `isMatch(s[1:], p[1:])`, i.e., the rest of `p` and `s` match.

The most bottom case of `isMatch` will only return True when `p` is empty and `s` is empty also. This means `s` has all been matched by `p` without anything left unmatched. Notice that line 12 and line 14 will return False immediately if `s` is empty. This means there are something left in `p` but you have consumed all `s`.

However, this method can’t pass Leetcode OJ written in Python. The time complexity is large because you are essentially exhausting all possible situations. Naturally, you can convert such algorithm into DP.

Code 2:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        table = [[False] * (len(s)+1) for _ in xrange(len(p)+1)]
        table[0][0] = True
        for i in xrange(2, len(p)+1):
            table[i][0] = p[i-1] == '*' and table[i-2][0]
            
        for i in xrange(1, len(p)+1):
            for j in xrange(1, len(s)+1):
                if p[i-1] == '*':
                    table[i][j] = (p[i-2] == '.' or p[i-2] == s[j-1]) and table[i][j-1] or table[i-2][j]
                else:
                    table[i][j] = (p[i-1] == '.' or p[i-1] == s[j-1]) and table[i-1][j-1]


        return table[-1][-1]

Reference: https://leetcode.com/discuss/55253/my-dp-approach-in-python-with-comments-and-unittest

Idea:

It is a DP algorithm. table[i][j] records whether p[0:i] matches s[0:j]. table[0][0] is True because “” matches “”. table[i][0] is the result of a pattern matching “”. It will only be true if `p` only contains `x*` pattern. table[0][j] will always be False because an empty pattern will not be able to match any string. 

Then, we start to update table[i][j], column first.

If p[i-1] == “*”, table[i][j] will be true if:

1. p[i-1] equals to s[j-1] and p[0:i] matches s[0:j-1] (str1 + “x*” matches str2 => str1 + “x*” matches str2 + “x”),
2. p[0:i-1] matches s[0:j] (str1 matches str2 => str1+”x*” matches str2) 

if p[i-1] is not “*”, table[i][j] will be true if p[0:i-1] matches s[0:j-1] (str1 matches str2 => str1+”x” matches str2+”x”)

This algorithm uses O(|p||s|) space to get fast running time. It is accepted by Leetcode finally.

https://leetcode.com/problems/closest-binary-search-tree-value/

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 closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if root is None:
            return None
        self.m = sys.maxint
        self.helper(root, target)
        return self.closest

    def helper(self, root, target):
        if self.m > abs(root.val - target):
            self.closest = root.val
            self.m = abs(root.val - target)
        
        if root.left and target < root.val:
            self.helper(root.left, target)
        if root.right and target > root.val:
            self.helper(root.right, target)

Idea

If a value is larger than root.val, then difference between the value and any node in the root’s left tree must be larger than that between the value and the root itself. If a value is smaller than root.val, then difference between the value and any node in the root’s right tree must be larger than that between the value and the root itself.

The time complexity of this algorithm is O(logN), where N is the total number of nodes in the BST and we assume the BST is balanced.

Reference

https://leetcode.com/discuss/54438/4-7-lines-recursive-iterative-ruby-c-java-python

https://leetcode.com/discuss/56122/standard-binary-search

Code 1: 

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        for i in xrange(len(citations)):
            if citations[i] >= len(citations) - i:
                return len(citations) - i
        return 0

Code 2:

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

Code 3:

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

Idea:

Code 1 takes O(N) time to traverse every citation backwards. But actually, since citations are already sorted, you can use binary search to achieve O(logN) time complexity. We will take code 3 for example. (Code 2 is ugly implemented by my intermediate thoughts, so skip it.) We create `left` and `right` pointers. We use `mid` to binary search the correct point `i`, at which we can return len(citations) – i as h-index. `i` should have the following properties:

1. citations[j] < len(citations)-j for j < i
2. citations[k] >= len(citations)-k for k>=i

We have two condition branches in line 13 and line 15. In this way, we always make sure that:

a. `citations[right+1] > len(citations) – right -1` holds.

b. `citations[left-1] < len(citations) – left +1` holds

The last execution of while loop is when left == right == mid: you check `citations[mid] ? len(citations) – mid` the last time:

1. If line 13 holds, you know that current `right` has: `citations[right] < len(citations) – right`. You set `left = mid + 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. From property a, we know that: `citations[right+1] > len(citations) – right -1`. Therefore we return `len(citations)-right-1` as h-index.
2. If line 15 holds,  you know `right` before set to `mid-1` has: `citations[right] > len(citations) – right`. Then you set `right = mid – 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. Now, `right = mid – 1 = left – 1`. From property b, we know: `citations[right] < len(citations) – right`. So we still return `len(citations)-right-1` as h-index.

This works even in the corner case in which `citations=[0,0,…,0]` because right will be initialized as `len(citations)-1` and will not get changed in the while loop. At the last line, `len(citations)-right -1 =0`, which is still the correct h-index for this case.

Reference:

https://leetcode.com/discuss/56122/standard-binary-search

https://leetcode.com/problems/h-index/

Code:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        cnt = [0] * (len(citations)+1)
        for c in citations:
            if c>= len(citations):
                cnt[-1] += 1
            else:
                cnt += 1
        
        total = 0
        for i in xrange(len(cnt)-1, -1, -1):
            print i
            total += cnt[i]
            if total >= i:
                return i

Idea:

This algorithm needs O(N) time and O(N) space. A researcher’s h-index can’t be beyond the number of his publications, i.e., len(citations). So we create an array `cnt` of length len(citations)+1. For any citation, if it is larger than len(citations), we count that in cnt[-1]. The meaning of `cnt` array is that cnt[i] is the number of publications which have i citations. Exceptionally, cnt[-1] is a count for all other publications with the citations >= `len(citations)`. 

Then we traverse from cnt[-1] to cnt[0]. If cnt[-1] is already larger than len(citations), that means all publications have citations more than len(citations). if not, whenever the accumulated sum of cnt until `i` is equal to or larger than `i`, that means we have found at least `i` publications with at least i citations. Thus we return `i` immediately.

Another idea is to sort `citations` first in place in O(nlogn) then you don’t need the O(n) space. See H-Index II.

Reference:

https://leetcode.com/discuss/56987/python-o-n-lgn-time-with-sort-o-n-time-with-o-n-space

https://leetcode.com/problems/3sum-smaller/

[-2, 0, 1]
[-2, 0, 3]

Code:

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if nums is None or len(nums) <=2:
            return 0
        nums.sort()
        cnt = 0
        for k in xrange(2, len(nums)):
            i, j = 0, k-1
            while i < j:
                if nums[i] + nums[j] + nums[k] < target:
                    cnt += j - i
                    i += 1
                    j = k-1
                else:
                    j -= 1
        return cnt

Idea:

This is O(N^2) solution. You first sort nums in O(nlogn). Then, for every `k` in xrange(2, len(nums)), you start to pivot `i` at 0, and j on the left of `k`. Since nums is already a sorted array, if nums[i] + nums[j] + nums[k] < target, then fixing `i` and `k`, moving the index `j`  between`i+1` and `j` can always satisfy the inequality. On the other hand, if nums[i] + nums[j] + nums[k] >= target, you need to move j one position left and retry. The algorithm is O(N^2) because for each `k`, i and j will be traversed until they meet together in the middle of nums, i.e. `i` and `j` will be traversed together in O(N).

https://leetcode.com/problems/wiggle-sort/

Code:

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for x in xrange(1, len(nums), 2):
            if x < len(nums)-1 and nums[x+1] > nums[x]:
                nums[x], nums[x+1] = nums[x+1], nums[x]
            if nums[x] < nums[x-1]:
                nums[x], nums[x-1] = nums[x-1], nums[x]

Idea:

You start from every odd index of x, if nums[x+1] > nums[x], you exchange them. At the moment after the exchange, nums[x] > nums[x+1] for sure. Now, if you also find that nums[x-1] > nums[x], nums[x-1] must already be larger than nums[x+1]. So you are safe to exchange nums[x-1] and nums[x] to meet nums[x-1] <= nums[x] >= nums[x+1] without any potential to break the inequality.