Python O(NLogN) solution using binary search

• ``````def lengthOfLIS(self, nums):
def search(lst, lo, hi, target):
if hi - lo < 1:
return lo
mid = lo + (hi - lo)/2
return search(lst, mid+1, hi, target) if lst[mid] < target else search(lst, lo, mid, target)

seq = []
for n in nums:
pos = search(seq, 0, len(seq), n)
if pos >= len(seq):
seq.append(n)
else:
seq[pos] = min(seq[pos], n)

return len(seq)``````

• You mean, O(N Log N), not O(Log N) =)

• My bad, thanks for reminding me :)

• I don't quite understand what the `seq` means, why can you change `seq[pos]` when `pos < len(seq)-1` ? Could you please explain ?

• Hi, seq means 'sequence' :)
Please refer to https://leetcode.com/discuss/67687/c-o-nlogn-solution-with-explainations-4ms for more details, we have the same idea, and this guys has a very nice explanation, give him an up vote for me if you like his answer as well.

• Thank you ! I understand somehow now. `seq[i]` means "the smaller ending number for a increasing subsequence of length i", right ?

• You're welcome:). That's right, it does mean "the smaller ending number for a increasing subsequence of length i"

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.