def findMinDifference(self, timePoints):
t = [0] * 24 * 60 #array for the time. they are buckets
for s in timePoints:
v = int(s[:2]) * 60 + int(s[3:5])
if t[v]==1: return 0 #find duplicate time
t[v] = 1
tt = t + t # concat two time arrays together, to handle cases like [23:59, 00:01]
ans = 24*60 # value to return
prev = 24*60
for i in xrange(len(tt)):
if tt[i]:
ans = min(ans, iprev)
prev = i
return ans
cbmbbz
@cbmbbz
Posts made by cbmbbz

python O(n) bucket sort

simple solution without using dynamic programing
each number in the array can be picked or not picked to form the subset of array to have a target sum. Here we can scan through the array, and store the sums of the subsets that include or not include the current number. We can use a set to store the sums to avoid duplicates.
def canPartition(self, nums): total = sum(nums) if total % 2 == 1: return False target = total / 2 #target sum s = set([0]) #stores the sums of the subsets for n in nums: sums_with_n = [] #stores the sums of the subsets that contain n for i in s: if i + n == target: return True if i + n < target: sums_with_n.append(i + n) s.update(sums_with_n) return False

easy 10line python solution with inline explanation
def toHex(self, num): if num==0: return '0' mp = '0123456789abcdef' # like a map ans = '' for i in range(8): n = num & 15 # this means num & 1111b c = mp[n] # get the hex char ans = c + ans num = num >> 4 return ans.lstrip('0') #strip leading zeroes

easy python solution based on generating random index and swapping
import random class Solution(object): def __init__(self, nums): self.nums = nums def reset(self): return self.nums def shuffle(self): ans = self.nums[:] # copy list for i in range(len(ans)1, 0, 1): # start from end j = random.randrange(0, i+1) # generate random index ans[i], ans[j] = ans[j], ans[i] # swap return ans

python solution using two maps / or map + list, inline explanation
# bijective maps. # when remove an element , use the last element in the map to fill the hole left by the removed element. import random class RandomizedSet(object): def __init__(self): self.key_val = {} #key from 1 to self.size; val is the inserted val. can use list here instead. self.val_key = {} #reversed map of the above. self.size = 0 def insert(self, val): if val in self.val_key: return False else: self.size += 1 self.val_key[val] = self.size self.key_val[self.size] = val return True def remove(self, val): if val not in self.val_key: return False else: # use the last element to fill the hole left by the removed element key = self.val_key[val] last = self.key_val[self.size] self.key_val[key] = last self.val_key[last] = key del self.val_key[val] del self.key_val[self.size] self.size = 1 return True def getRandom(self): i = random.randrange(1, self.size+1) return self.key_val[i]

RE: Clean python solution, one pass
“if acck in mp:” is to find whether there's a subarray with sum of k; and mp[acck] has the starting index of that subarry, and thus imp[acck] is the length of the subarray.

RE: Clean python solution, one pass
I tried your test case and it showed that the expected answer is 0, not 10. I think u misunderstood the concept of subarray, which is a consecutive part of the input array. In your example, you cannot exclude 3+5 or 1+7 since your resulting "subarray" would not be consecutive.

RE: 10line python solution with priority queue
it may not be better than heapq, Queue does not has a peek() function...

RE: O(n) python solution using binary search
that is the exact mistake I made in this problem  focusing on the searching part and forgot the last seemingly trivial but time dominating insertion part... Now I know I am not the only one who had this mistake since the Python docs feels the need to point it out :).

RE: O(n) python solution using binary search
u r right, slicing 'intervals' makes it O(n).