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 halfopen 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 #rangetuples (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 inbetween 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[i1])
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[j1])
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 zerobased.
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 hashtable and reading all the variables smaller then the target into the hash table and doing another pass. But this is an overkill, 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,ji) where i is a positive integer cannot be the solution since a[k]+a[j]
ji.  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 footprint 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)