czxttkl

A post to review RadixSort. The idea is to 

Code

class RadixSort():

    def sort(self, nums):
        max_num = max(nums)

        exp = 1
        while max_num / exp:
            nums = self.count_sort(nums, exp)
            exp = exp * 10

        return nums

    def count_sort(self, nums, exp):
        # how many numbers have 0~9 for the current position
        digit_counts = [0] * 10

        for n in nums:
            digit_counts[(n / exp) % 10] += 1

        # accumulate counts
        for i in xrange(1, 10):
            digit_counts[i] += digit_counts[i-1]

        outputs = [0] * len(nums)
        # traverse from tail to head because we want to keep original order
        # of numbers having same digit on the current position
        for n in nums[::-1]:
            outputs[digit_counts[(n / exp) % 10] - 1] = n
            digit_counts[(n / exp) % 10] -= 1

        return outputs


if __name__ == "__main__":
    s = RadixSort()
    print s.sort([4,3,1,20,100])

Idea

Traverse digits: for each digit, count how many numbers have 0~9 on that digit and put the counts in a bucket (digit_count). Then, convert the bucket into accumulated counts. For example, if digit_count[0]=3 and digit_count[1]=4, then after the conversion, digit_count[1]=7 because we know numbers with 1 on that digit will be put in the position between `[3, 7)` (position starts from 0).  

Then we can reorder the numbers. We reorder from right to left (line 27~29) because we want to keep the original order of numbers which have the same digit on the current digit position.

If a number at most uses $latex d$ digits, radix sort uses time $latex O(d(n+d))$ and space $latex O(n+d)$.  

Reference: http://www.geeksforgeeks.org/radix-sort/

Also see MergeSort and QuickSort.

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        major = ''
        for n in nums:
            if count == 0:
                major = n
            if n == major:
                count += 1
            else:
                count -= 1
        return major

Idea

This is the algorithm called Moore voting. More details can be found: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/. My understanding is that major is the current number whose occurrences has not been outnumbered by other numbers. The majority element will eventually has its occurrence count being positive. 

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        
        for i in xrange(32):
            ones, zeros = 0, 0
            for n in nums:
                # right shift for negative number is weird 
                # in Python. So apply on absolute value.
                if (abs(n) >> i) & 1:
                    ones += 1
                else:
                    zeros += 1
            if ones > zeros:
                ans = ans | (1 << i)
                
        # in python, you need to count signs separately.        
        positive, negative = 0, 0
        for n in nums:
            if n > 0:
                positive += 1
            else:
                negative += 1
        if positive > negative:
            return ans
        else:
            return -ans

Idea

Borrow the idea from Single Number II. Count one’s and zeros appearing in each bit. The majority element dominates those counts so you can reconstruct the number.

Reference: https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits

Code (divide and conquer)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return nums[0]
        a = self.majorityElement(nums[:len(nums)/2])
        b = self.majorityElement(nums[len(nums)/2:])
        if a == b:
            return a
        else:
            return a if nums.count(a) > len(nums)/2 else b

Idea

THink from top to bottom. When nums have two partitions, and we already know a is the majority element of the first partition (line 11) and b is the majority element of the second partition (line 12). If c is the majority element, then either:

1. a == b == c, i.e., c is the majority element in both partitions
2. a != b. then c must be equal to either a or b. 

We can prove 2 by contradiction. If c != a and c != b, then c is not the majority element in either partition. That means, occurrences(c in 1st partition) <= len(1st partition)/2 and occurrences(c in 2nd partition) <= len(2nd partition)/2. Therefore, occurences(c in nums) <= len(nums)/2, which contradicts with the fact that c is the majority element. So we recursively can prove the correctness of every level of divide-and-conquer.

Code (Sorting)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]

Idea

After sorting, the majority element must occupy the position len(nums)/2

Code

# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        # pick up two candidates, exclude at least one each time
        candidates = set(range(n))
        while len(candidates) > 1:
            a, b = candidates.pop(), candidates.pop()
            if knows(a, b) and not knows(b, a):
                candidates.add(b)
            elif not knows(a, b) and knows(b, a):
                candidates.add(a)

        if len(candidates) == 1:
            c = candidates.pop()
            # when only one candidate is left, we still need to ensure
            # his celebrity by definition
            for i in xrange(n):
                if i != c and not (knows(i, c) and not knows(c, i)):
                    return -1
            return c
        else:
            return -1

Idea

This is my first attack. Create a set of candidates. Exclude at least one candidate by determining two candidates’ relationship each time. When there is only one candidate c left, we still need to check by definition whether knows(i, c) and not knows(c, i) for all i != c. 

An improved idea is to think this problem as numerical comparisons. knows(a,b) means a < b. The celebrity will be the largest element among all peers.

Therefore, the code could be:

# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0: 
            return -1
        
        x = 0
        for i in xrange(1, n):
            if knows(x, i):
                x = i
        
        for i in xrange(n):
            if i != x and not (knows(i, x) and not knows(x, i)):
                return -1
        return x

Reference: https://discuss.leetcode.com/topic/25720/java-python-o-n-calls-o-1-space-easy-to-understand-solution

Code

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        sum = 0
        max_res = 0
        # key: sum of all elements so far, value: the index so far
        sum_map = dict()

        for i, n in enumerate(nums):
            sum += n
            if sum == k:
                max_res = i + 1
            elif sum_map.get(sum-k, None) is not None:
                max_res = max(max_res, i - sum_map[sum-k])
            # if sum already exists in sum_map, its index should be
            # smaller than the current index. Since we want to find
            # the maximum length of subarray, the smaller index
            # should be kept.
            if sum_map.get(sum, None) is None:
                sum_map[sum] = i

        return max_res

Idea

The obvious brute-force way is to have two pointers, i and j (0 <=i<len(nums), i+1<=j <len(nums)), and test whether nums[i:j+1] sum to k. This takes O(n^2) time where n is the length of nums.

Our code uses the following idea: Create a dictionary sum_map which records the sum of all previous elements when traversing nums. Its key is the sum of all elements so far and its value is the current index. 

During the traversal, we can check whether the current sum so far equals to k (line 15-16). We can also check whether sum_map contains sum-k as a key. If so, that means a subarray can be found between `sum_map[sum-k]` and `i`.

Reference: https://discuss.leetcode.com/topic/33259/o-n-super-clean-9-line-java-solution-with-hashmap

Code

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        for idx, (chr_s, chr_t) in enumerate(zip(s, t)):
            if chr_s != chr_t:
                # when s and t have same length, 
                # the only possibility is they only differ at this index 
                if len(s) == len(t):
                    return s[idx+1:] == t[idx+1:]
                # if s is longer than t, the only possibility is 
                # s has an insertion at idx
                elif len(s) > len(t):
                    return s[idx+1:] == t[idx:]
                # otherwise,, the only possibility is t has an insertion
                # at idx
                else:
                    return s[idx:] == t[idx+1:]

        return abs(len(s) - len(t)) == 1

Idea

See comments. There are only three conditions to determine if two strings are one edit distance apart.

Reference: https://discuss.leetcode.com/topic/30308/my-clear-java-solution-with-explanation

Code

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        sum = 0
        for i in xrange(32):
            sum += (n >> i) & 1
        
        return sum

Idea

Classic bit operation to count 1.

Another way to count 1 is to do n = n & (n-1) until n is equal to 0:

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n:
            n = n & (n-1)
            count += 1
        return count

Reference: https://discuss.leetcode.com/topic/20120/c-solution-n-n-1

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 inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        if (not p) or (not root):
            return None
        
        # if p has right child, its inorder successor is
        # the leftmost leaf of his right child
        if p.right:
            return self.leftmost(p.right)
        
        # record the most recent traversed node that has the left branch leading to p    
        prev_root = None
        while root != p:
            if p.val <= root.val:
                prev_root = root
                root = root.left
            else:
                root = root.right

        return prev_root

    def leftmost(self, node):
        while node.left:
            node = node.left
        return node

Idea

If p has right child, then its inorder successor is the leftmost leaf of his right child

Otherwise, p’s inorder successor is the most recent traversed node that has the left branch leading to p.

Actually, the code can be simplified as: 

# 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 inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        succ = None
        while root:
            # think in this way: find the smallest element 
            # that is larger than p
            if p.val < root.val:
                succ = root
                root = root.left
            else:
                root = root.right
        return succ

Reference: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative

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 minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0
        
        timeline = []
        for i in intervals:
            timeline.append(('start', i.start))
            timeline.append(('end', i.end))
            
        # sort timeline tuples by time first then by 'start' or 'end' tag
        # e.g. ('end', 13) < ('start', 13)
        timeline = sorted(timeline, key=lambda x: (x[1], x[0]))
        
        room = 0
        max_room = 0
        for k, v in timeline:
            if k == 'start':
                room += 1
            else:
                room -= 1
            if room > max_room:
                max_room = room
        
        return max_room
                

Idea

Create a timeline, a list of tuples. Each tuple marks a “start” or “end” tag with the time. Then sort the timeline and start traversing it. Whenever you see a start time, that means a new room is requested. Whenever you see an end time, that means a room is returned. 

You can also use heap to solve this problem: https://discuss.leetcode.com/topic/25904/python-heap-solution-with-comments

Code

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

from heapq import *

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals = sorted(intervals, key=lambda x: x.start)
        heap = []
        for i in intervals:
            # if the new meeting happens after the earliest meeting ends,
            # replace the earliest ending meeting with the new meeting
            if heap and i.start >= heap[0]:
                heappop(heap)
                heappush(heap, i.end)
            else:
                heappush(heap, i.end)

        return len(heap)

Code

# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):

class Solution(object):
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        idx = 0

        while True:
            if idx == n:
                return idx 

            buf4 = [0]*4
            read4_ret = read4(buf4)
            for i in xrange(read4_ret):
                if idx < n:
                    buf[idx] = buf4[i]
                    idx += 1
                else:
                    return idx

            if read4_ret < 4:
                return idx

Idea

You read contents into buf. You should create a small buffer buf4 to save contents from read4. Then, based on how many characters you have read, determine when to return.

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Code

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ans = []
        self.removeHelper(s, 0, 0, '(', ')', ans)
        return ans

    def removeHelper(self, s, last_i, last_j, char1, char2, ans):
        """ Remove invalid parentheses in two rounds:
            1st round: detect ')' appears more times then '('
            2nd round: detect '(' appears more times then ')'
        """
        sum = 0
        for i in xrange(last_i, len(s)):
            if s[i] == char1: 
                sum += 1
            if s[i] == char2:
                sum -= 1
            if sum >= 0: 
                continue
            # anytime when sum < 0, we can start deleting a char2 between [last_j, i]
            for j in xrange(last_j, i+1):
                # deleted char2 should be first seen or not repeating (to avoid duplication)
                if s[j] == char2 and (j == last_j or s[j] != s[j-1]):
                    self.removeHelper(s[:j] + s[j+1:], i, j, char1, char2, ans)
            # invalid string has had valid result added to ans in recursion. so stop here.
            return
        
        s = s[::-1]
        if char1 == '(':
            self.removeHelper(s, 0, 0, ')', '(', ans)
        else:
            ans.append(s)
        

Idea

Remove invalid parentheses in two rounds:
1st round: detect ‘)’ appears more times then ‘(‘
2nd round: detect ‘(‘ appears more times then ‘)’

We use sum to record whether char2 appears more than char1. Whenever sum < 0, we can start deleting a char2 between [last_j, i]. A char2 to be deleted should be first seen or not repeating with previous chars. (check yourself by some examples.) last_j records the last deletion position. last_i records the last traversed position. 

In the second round, we can just reverse s and swap char1 and char2.

Reference: https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-solution