czxttkl

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
            return ""

        start = 0
        max_len = 1        

        for i in xrange(len(s)):
            if i-max_len-1 >=0 and s[i-max_len-1:i+1] == s[i-max_len-1:i+1][::-1]:
                start = i - max_len - 1
                max_len = max_len + 2
                continue

            if i-max_len >=0 and s[i-max_len:i+1] == s[i-max_len:i+1][::-1]:
                start = i - max_len
                max_len = max_len + 1

        return s[start:start+max_len]

Reference:

https://leetcode.com/discuss/21332/python-o-n-2-method-with-some-optimization-88ms

https://leetcode.com/problems/median-of-two-sorted-arrays/

Median of Two Sorted Arrays

Let me first show the code and then show the idea.

import sys

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) == 0 and len(nums2) == 0:
           return None
        	
        if len(nums1) < len(nums2):
           nums1, nums2 = nums2, nums1

        if len(nums2) == 0:        
           return (nums1[(len(nums1)-1)/2] + nums1[len(nums1)/2]) / 2.0

        jmin, jmax = 0, 2*len(nums2)        
        while jmin <= jmax:
            jmid = (jmin + jmax) / 2
            imid = len(nums1) + len(nums2) - jmid
            i_left = nums1[(imid-1)/2] if imid else - sys.maxint
            i_right = nums1[imid/2] if 2*len(nums1) - imid else sys.maxint
            j_left = nums2[(jmid-1)/2] if jmid else - sys.maxint
            j_right = nums2[jmid/2] if 2*len(nums2) - jmid else sys.maxint
            if i_left > j_right:
                jmin = jmid + 1
            elif j_left > i_right:
                jmax = jmid - 1
            else: // i_left <= j_right and j_left <= i_right               
                return (max(i_left, j_left) + min(i_right, j_right)) / 2.0 

Idea

The length of nums1 or nums2 can be odd or even. The total length of nums1 and nums2 can also be odd or even. To calculate median, if the list has N (N is odd) elements, you should return the very middle element list[N/2]. If N is even, you should return the average of the two middle elements: (list[(N-1)/2] + list[N/2]) / 2. All these considerations will make your brain twisted. So first of all we need to come up with a more general notation system to deal with either odd or even numbers.

The notation system can be better illustrated in the following two examples:

original array: 99, 100, 101

original index: 0, 1, 2

expanded array: #, 99, #, 100, #, 101, #

expanded index: 0, 1, 2, 3, 4, 5, 6

median cut original index: 1 

median cut expanded index: 3

median: 100

original array: 99, 100, 101, 102

original index: 0, 1, 2, 3

expanded array: #, 99, #, 100, #, 101, #, 102, #

expanded index: 0, 1, 2, 3, 4, 5, 6, 7, 8

median cut original index: 2,3 

median cut expanded index: 4

median: (100 + 101)/2

The two arrays are expanded by adding `#` between numbers as well as at the beginning and at the end of the array. You may find that ‘#’ always have odd index in the expanded array. Numbers always have even index in the expanded array. Every position in the expanded array denotes a possible cut. A cut at position `c` (0-based, c!=0 and c!=len(arr)) in the expanded array will return:

1. If you cut at `#`, then the cut will return the average of two numbers on its left and right. i.e., (ori[(c-1)/2] + ori)/2
2. If you cut at a number in the expanded array, you return that number directly. Or equivalently, you can imagine you cut on that number so the number is copied and splitted both on the cut’s left side and right side. So you still return the average of two (same) numbers on its left and right, i.e., (ori[(c-1)/2] + ori)/2, since ori[(c-1)/2] and ori always point to that number in this case.

The expanded array always has odd number length. If we know where we should cut in the expanded array to find the median of the original array (say position `c`), you can always return (ori[(c-1)/2] + ori)/2. You can think that the largest value on the left of cut `c` in the original array is always ori[(c-1)/2]. The smallest value on the right of cut `c` in the original array is always ori. 

Now go back to our problem. We have nums1 and nums2. We make sure that nums1 always has no shorter length than nums2 in order to make us focus only on one case. (line 13-14.) 

From now on we suppose that nums1 and nums2 have already been expanded. So the two expanded arrays have 2*N1+1 and 2*N2+1 length respectively. (N1 >= N2). The total length of nums1 and nums2 is thus 2*N1+2*N2+2, an even number.  The whole algorithm’s idea is to find two cuts, cut_i and cut_j, in nums1 and nums2 so that the median of the two lists resides in the middle of the two cuts. Such two cuts, cut_i and cut_j, will have two following properties:

1. There should be totally (N1+N2) elements on the left of cut_i in nums1 and on the left of cut_j in nums2. There should also be totally (N1+N2) elements on the right of cut_1 in nums1 and on the left of cut_j in nums2. So once cut_i’s or (cut_j’s) index is determined, the other is determined also.
2. The median is between the two cuts’ values. So, the largest element in nums1 which is on the left of cut_i (nums1[(cut_i-1)/2]), should be no larger than the smallest element on the right of cut_j in nums2 (nums2[cut_j/2]). The largest element on the left of cut_j in nums2, nums2[(cut_j-1)/2], should be no larger than the smallest element on the right of cut_i in nums1 (nums1[cut_i/2]).  

Using these two properties, you can start to binary search a cut in nums2, and consequently determine the cut in nums1. If either of the two properties doesn’t hold, you need to adjust the cut in nums2 in a binary search manner. However, we shouldn’t first start binary search a cut in nums1 (the longer list) and then determine the cut in nums2 (the shorter list). Because you may find a cut in nums1 on the left of which there already are more elements than N1+N2. In that case, you can’t even determine where is the cut in nums2.

The only corner cases you need to handle is when any cut is at index 0 or end index. But such cases can be handled intuitively: if you cut at index 0, your left value should be -inf. If you cut at end index, your right value should be inf.

Reference

https://leetcode.com/discuss/41621/very-concise-iterative-solution-with-detailed-explanation

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start_pos = 0
        character_dict = {}
        max_len = 0
        
        for i in xrange(len(s)):
            last_pos = character_dict.get(s[i], -1)
            if last_pos != -1 and last_pos >= start_pos:
                start_pos = last_pos + 1
            cur_len = i - start_pos + 1
            if cur_len > max_len:
                max_len = cur_len
                
            character_dict[s[i]] = i
        
        return max_len

https://leetcode.com/problems/subsets-ii/

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

Idea:

Initialize the return list, `res`, with a list of an empty list, since any set will have empty set as one of its subset. You need to sort the numbers first, because you are asked to give non-descending order subsets. 

Then, starting from the first number in the sorted list, you compare the current number with the previous number. If they are different (or the current number is the first number you scan), you need to concatenate the current number with all existing subsets in `res`.  If the current number is the same as the previous number, the current number has no need to concatenate with all previous subsets. It will introduce duplication if you do so. Instead, you only need to concatenate the current number with the subsets that have been added into `res` by the previous same number. For example, if the previous number is 2, and it introduces [2], [1,2] into the `res` by concatenating with [] and [1]. Then, the current number being 2 will only need to append new subsets [2,2] and [1,2,2] by concatenating with [2] and [1,2]. However, it is not needed to concatenate with [] and [1] again.

Code:

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        nums.sort()
        for i in xrange(len(nums)):
            if len(res) == 1 or nums[i] != nums[i-1]:
                l = len(res)
            for j in xrange(len(res)-l, len(res)):
                res.append(res[j] + [nums[i]])
        return res

https://leetcode.com/problems/the-skyline-problem/

The Skyline Problem

I failed to do it myself. My first thought was to traverse each building once and determine all skyline points that should be added. However, `O(N)` seems unable to solve this problem. Because there are many cases that you need to go back to check already added skyline points.

The correct idea is to use merge and sort, though there are so many edge cases. Two solutions that seem easy to understand:

https://leetcode.com/discuss/37444/my-220ms-divide-and-conquer-solution-in-python-o-nlogn

http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/

http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

One piece of code from them:

#
class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def getSkyline(self, buildings):
        if buildings==[]:
            return []
        if len(buildings)==1:
            return [[buildings[0][0],buildings[0][2]],[buildings[0][1],0]]
        mid=(len(buildings)-1)/2
        left=self.getSkyline(buildings[0:mid])
        right=self.getSkyline(buildings[mid:])
        return self.merge(left,right)

    def merge(self,left,right):
        i=0
        j=0
        result=[]
        h1=None
        h2=None
        while i<len(left) and j<len(right):
            if left[i][0]<right[j][0]:                            # Condition 1
                h1=left[i][1]
                new=[left[i][0],max(h1,h2)]
                if result==[] or result[-1][1]!=new[1]:
                    result.append(new)
                i+=1
            elif left[i][0]>right[j][0]:                          # Condition 2
                h2=right[j][1]
                new=[right[j][0],max(h1,h2)]
                if result==[] or result[-1][1]!=new[1]:
                    result.append(new)
                j+=1
            else:                                                 # Condition 3
                h1=left[i][1]
                h2=right[j][1]
                new=[right[j][0],max(h1,h2)]
                if result==[] or result[-1][1]!=new[1]:
                    result.append([right[j][0],max(h1,h2)])
                i+=1
                j+=1
        while i<len(left):                                        # Condition 4
            if result==[] or result[-1][1]!=left[i][1]:
                result.append(left[i][:])
            i+=1
        while j<len(right):                                       # Condition 5
            if result==[] or result[-1][1]!=right[j][1]:
                result.append(right[j][:])
            j+=1

        return result

The basic idea is to divide and conquer the problem. In a basis case, where we only have one building, we return the building’s left up corner and its right down corner. (line 8-9). The crux of this problem is the `merge` function. It will always merge two sets of skyline points so that a set of merged valid skyline points is returned. So the `getSkyline` function is always merging two sets of already valid skyline points.

In `merge`, no matter how you append a skyline point to `result`, you always compare two things: 1. whether `result` is empty, which means you can always safely add it as a first element to `result`. 2. otherwise, whether the last element in `result` has the same height as the current skyline point that is about to be appended. That is because we want to avoid two consecutive skyline points on the same height.

In another perspective, `merge` always scans a pair of sets of skyline points from left to right, and only add those which:

1. if the pair of sets both have skyline points left to be scanned, then the current skyline point will be added either if it has a higher height than the previous added skyline point from the other set, or the current result is empty.
2. if one set has no skyline point left to be scanned,  then we will add all the remaining skyline points to the result, as long as they don’t have the same height as the element added most recently.

Let’s look at four simple examples. All the four examples have input of two buildings.

Example 1:

In `merge`, the `left` list has point 1 and 2. The `right` list has point 3 and 4. Point 1 will be scanned first and be added according to condition 1. Next, point 2 will be scanned and be added according to condition 1.  After that, point 3 and point 4 will be added according to condition 5.

Example 2:

In `merge`, the `left` list has point 1 and 2. The `right` list has point 3 and 4. Point 1 will be scanned first and be added according to condition 1. Point 3 will be scanned next and be added according to condition 2. Point 2 will be scanned next but be discarded by condition 1’s sub-condition `result[-1][1]!=new[1]`. Point 4 will be added according to condition 5.

Example 3:

In `merge`, the `left` list has point 1 and 2. The `right` list has point 3 and 4. Point 1 will be scanned first and be added according to condition 1. Point 3 will be scanned next and be added according to condition 2. Point 4 will be scanned but be discarded by condition 2’s sub-condition `result[-1][1]!=new[1]`.  Point 2 will be scanned at last and be added according to condition 4.

Example 4:

In `merge`, the `left` list has point 1 and 2. The `right` list has point 3 and 4. Point 1 and point 3 will be scanned together according to condition 3 and point 3 will be added to the result. Then, point 2 and point 4 will be scanned together according to condition 3 and point 2 (or point 4) will be added to the result.

Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Naive idea: traverse from left to right. left[i] means the height of the tallest wall on the left of element i (element i itself excluded). right[i] means the height of the tallest wall on the right of element i (element i itself excluded). Then you traverse the `height` list again, determine how high each element can hold water. This idea will take O(N) time and O(N) space.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # Get left[i]
        prev = 0
        left = [0] * len(height)
        for idx, val in enumerate(height):
            left[idx] = prev
            if val > prev:
                prev = val
        
        # Get right[i]
        prev = 0
        right = [0] * len(height)
        for idx, val in enumerate(height[::-1]):
            right[len(height)- 1 - idx] = prev
            if val > prev:
                prev = val
        
        sum = 0
        for i in xrange(0, len(height)):
            diff = min(left[i], right[i]) - height[i]
            if diff > 0:
                sum += diff
        print left
        print right
                
        return sum

Another idea takes O(N) time but O(1) space: You have two pointers, left and right. The water that an element can hold is dependent on min height (the tallest wall to its left, the tallest wall to its right).  We use `max_left` and `max_right` to record both heights. You roll out the algorithm from the two ends of the list, every time either moving `left` to one element right or `right` to one element left until they meet somewhere in the central. If the current element has a lower height of the tallest wall to its left than the tallest wall to its right, its vertical water holding amount will be determined by `max_left` as well as the element’s own height. If the current element has a lower height of the tallest wall to its right than the tallest wall to its left, its vertical water holding amount will be determined by `max_right` as well as the element’s own height.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        max_left = 0
        right = 0
        max_right = 0
        right = len(height) -1
        
        sum = 0
        while left <= right:
            if max_left < max_right:
                if height[left] > max_left:
                    max_left = height[left]
                else:
                    sum += max_left - height[left]
                left += 1
            else:
                if height[right] > max_right:
                    max_right = height[right]
                else:
                     sum += max_right - height[right]
                right -= 1

        return sum