class Solution(object):
def lengthOfLIS(self, A):
tail_values = []
for v in A:
idx = self.lower_bound(tail_values, v)
if idx == len(tail_values):
tail_values.append(v)
else:
tail_values[idx] = v
return len(tail_values)
# Return the index of the first element in input array A that is smaller
# than the given value v.
def lower_bound(self, A, v):
n = len(A)
if not n:
return 0
start = 0
end = n
while start < end:
mid = start + (end  start) / 2
if A[mid] < v:
start = mid + 1
else:
end = mid
return start
youke
@youke
Posts made by youke

Simple python O(nlogn) solution

Simple python solution  O(n) time, O(1) space and no division
class Solution(object): def productExceptSelf(self, nums): n = len(nums) if n < 2: return nums res = list(nums) # transform nums such that nums[i] = num[1] x nums[2] x ... x nums[i  1] nums[0] = 1 for i in range(1, n): nums[i] = nums[i  1] * res[i  1] # transform res such that res[i] = res[i + 1] x res[i + 2] x ... x res[n  1] tmp = res[1] res[1] = 1 for i in reversed(range(0, n  1)): t = res[i] res[i] = tmp * res[i + 1] tmp = t # transform res such that res[i] = res[1] x res[2] x ... x res[i  1] x res[i + 1] x ... x res[n  1] for i in range(1, n): res[i] *= nums[i] return res

Short python solution
class Solution(object): def lowestCommonAncestor(self, root, p, q): if not root: return None if root is p or root is q: return root if p.val < root.val < q.val or q.val < root.val < p.val: return root if p.val < root.val: return self.lowestCommonAncestor(root.left, p, q) else: return self.lowestCommonAncestor(root.right, p, q)

Short python solution
class Solution(object): def isPalindrome(self, l): if not l or not l.next: return True # find the head of the second half of the list prev = ListNode('') prev.next = l curr = prev.next fast = l while fast and fast.next: fast = fast.next.next curr = curr.next prev = prev.next prev.next = None # now curr is the head of the second half, flip the second half head = None while curr: tmp = curr.next curr.next = head head = curr curr = tmp # compare two lists first, second = l, head while first and second: if first.val != second.val: return False first, second = first.next, second.next return True

Simple python solution
class Solution(object): def countDigitOne(self, n): d = 1 count = 0 range_total = 0 # number of 1's in [0, d / 10] while d <= n: r = n % d c = (n % (10 * d)) / d if c > 0: count = c * range_total + count + (d if c > 1 else (r + 1)) range_total = 10 * range_total + d d *= 10 return count

Simple python solution
class Solution(object): def computeArea(self, A, B, C, D, E, F, G, H): total = (C  A) * (D  B) + (G  E) * (H  F) width = max(0, min(C, G)  max(A, E)) height = max(0, min(D, H)  max(B, F)) return total  width * height

RE: One line python solution
to determine whether a integer is a power of two, we only need to check when written in its binary form, the binary sequence contains just a single 1 in any position other than the highest bit. That is
An integer x is a power of two IF AND ONLY IF its binary sequence contains exactly one 1 in any position other than its highest bit.
the proof of above statement is quite straightforward: First if the highest bit is 1 then the integer is negative which makes it impossible to be a power of two(that's why we test if its positive first). Next, think about how a power of two could be obtained: for any integer that is a power of two, say x = 2^y, we shift bits of the integer 1 to the left by y positions. Therefore the binary sequence of x can contain exactly one 1.
For any binary sequence that contains a single 1, we can test it by checking whether x & (x  1) is zero  if the binary form of x contains two or more 1's, then subtracting it by 1 reduces at most one 1 from its binary form,(and possible introduces more 1's) and the remaining 1 (or 1's) makes x & (x  1) nonzero.
hope it helps.

One line python solution
class Solution(object): def isPowerOfTwo(self, n): return n > 0 and (n & (n  1)) == 0

O(1) python AC solution
class Solution: # @param {integer[][]} matrix # @return {void} Do not return anything, modify matrix inplace instead. def setZeroes(self, mtx): if not mtx or not mtx[0]: return m, n = len(mtx), len(mtx[0]) is_first_row_zero = is_first_col_zero = False for i in range(m): if mtx[i][0] == 0: is_first_row_zero = True for i in range(n): if mtx[0][i] == 0: is_first_col_zero = True for i in range(1, m): for j in range(1, n): if mtx[i][j] == 0: mtx[i][0] = 0 mtx[0][j] = 0 for i in range(1, m): if mtx[i][0] == 0: for j in range(1, n): mtx[i][j] = 0 for i in range(1, n): if mtx[0][i] == 0: for j in range(1, m): mtx[j][i] = 0 if is_first_row_zero: for i in range(m): mtx[i][0] = 0 if is_first_col_zero: for i in range(n): mtx[0][i] = 0

68ms Newton's method python code
class Solution: # @param {integer} x # @return {integer} def mySqrt(self, x): if x <= 0: return 0 if x == 1: return 1 d = x / 2 pprev = 0 prev = d d = (d + x / d) >> 1 while d != prev: pprev = prev prev = d d = int(0.5 * (d + x / d)) if pprev == d: return min(prev, d) return d