Solution to problem on slide 3:
Follows time complexity constraint, but is slow due to python overhead. Essentially use binary search over the array. First Check if either half of the array is sorted, and the answer lies within that range, then search there. Otherwise, search the other half of the array.
class Solution(object):
def search(self, nums, target):
return self.binary_search(nums, 0, len(nums)-1, target)
def binary_search(self, nums, start, end, target):
if start > end:
return -1
mid = (start+end)//2
if nums[mid] == target:
return mid
# start to mid is sorted
if nums[start] <= nums[mid]:
if nums[start]<=target<nums[mid]:
return self.binary_search(nums, start, mid-1, target)
else:
return self.binary_search(nums, mid+1, end, target)
# mid to end is sorted
else:
if nums[mid]<target<=nums[end]:
return self.binary_search(nums, mid+1, end, target)
else:
return self.binary_search(nums, start, mid-1, target)Solution to problem on slide 4:
solution found on slide.
Essentially flip the arrays and use good old carry-the-one algorithms to do the multiplication.
Solution to problem on slide 5:
no constraint simple solution O(n):
class Solution(object):
def searchRange(self, nums, target):
start = -1
end = -1
for i,v in enumerate(nums):
if v==target:
if start ==-1:
start = i
end = i
else:
end = i
return [start,end]with constraint simple solution O(log(n)):
Use binary search to get the first occurrence and last occurrence of the target.
class Solution(object):
def searchRange(self, nums, target):
start = 0
end = len(nums)-1
l=-1
r=-1
#get last target
while(start <= end):
middle = (start + end)//2
if nums[middle]<=target:
start = middle+1
if nums[middle]==target:
r = middle
else:
end = middle-1
start = 0
end = len(nums)-1
#get first target
while(start <= end):
middle = (start + end)//2
if nums[middle]>=target:
end = middle-1
if nums[middle]==target:
l = middle
else:
start = middle+1
return [l,r]