October Leet Code Selection

Leet Code Practice Selection

715. Range Module

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

• addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.

• queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.

• removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Solution

• First idea come up to my mind was holding array of ranges sorted by its starting integer. Such that we can do a binary search on it
• However to remove the overlapping ranges and connect them, one would need some complex procedure and this could take O(n) where n is the #range-tuples (imagine adding a range including all the previous ranges)
• Then I read the post in discussion and it has a very good idea of holding both the start end the end in an array. So we have an array and we are using bisect module to do binary search (very good module).
• We add the new range every time and then prune the everything in-between by removing them.
• All the procedures above takes O(n) where n is the #distinct integers in the ranges provided.

import bisect as bi
class RangeModule(object):

    def __init__(self):
        self.range_points = [float('-inf'),float('inf')]
        self.tracking = [False,False]

    def addRange(self, left, right,track_flag=True):
        """
        :type left: int
        :type right: int
        :rtype: void
        """
        i = bi.bisect_left(self.range_points,left)
        if self.range_points[i] != left:
            self.range_points.insert(i,left)
            self.tracking.insert(i,self.tracking[i-1])

        j = bi.bisect_left(self.range_points,right)
        if self.range_points[j] != right:
            self.range_points.insert(j,right)
            self.tracking.insert(j,self.tracking[j-1])

        self.range_points[i:j] = [left]
        self.tracking[i:j] = [track_flag]

    def queryRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: bool
        """
        i = bi.bisect(self.range_points,left)-1
        j = bi.bisect_left(self.range_points,right)
        return all(self.tracking[i:j])


    def removeRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: void
        """
        self.addRange(left,right,track_flag=False)

715. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

Solution

• So thinking that we may need to read all variables of the array, our algorithm can’t be better then O(n)
• One solution is using an hash-table and reading all the variables smaller then the target into the hash table and doing another pass. But this is an over-kill, since we can do this inplace, with at most n reads of the data.
• Since the data is sorted, a very nice observation is: if for two pair (i,j) the sum is bigger than the target and we know that the solution is within this range, we can approach to the problem greedily, narrowing the range iteratively from both sides.
• We can do this since it is guaranteed that all the k>i such that a[k]+a[j]<target cannot be in the solution. In other words indices (k,j-i) where i is a positive integer cannot be the solution since a[k]+a[j]j-i.
• This code gets into 86%

  class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0
        right = len(numbers) -1
  
        while 1:
            diff = target - numbers[left]
            while numbers[right]>diff:
                right -= 1
            if numbers[right] == diff:
                return [left+1,right+1]
            else:
                diff = target - numbers[right]
                while numbers[left]<diff:
                    left += 1
                if numbers[left] == diff:
                    return [left+1,right+1]
            print left,right
  

715. Verify Preorder Serialization of a Binary Tree

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

…

Solution

• The question is about how to verify a binary tree serialization implementation.
• I did a preorder recursive check, to reduce the foot-print of function calls. I’ve used the indices only.
• One can convert this code into an iterative version with some extra state variables or using a stack, but would be more complicated.
• I saw a very elegant counting solution on the discussions, where you basically count the difference between outgoing and ingoing edges. Since you do preorder the difference should be always positive and result in 0.

  class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        arr = preorder.strip().split(",")
        flag = True
        def helper(i):
            if i<len(arr):
                if arr[i] == "#":
                    return i+1
                else:
                    rest = helper(i+1)
                    rest = helper(rest)
                    return rest
            else:
                return float('inf') # just to force the program to exit
        res = helper(0)
        return res == len(arr)