Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:


Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note: 


       There may be more than one LIS combination, it is only necessary for you to return the length.
       Your algorithm should run in O(n2) complexity.


Follow up: Could you improve it to O(n log n) time complexity?

Difficulty: interview

Starter code:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return 0
         res = [nums[0]]
         def binarySearch(l,target):
             left , right = 0 , len(l)-1
             while left < right:
                 mid = (left + right)//2
                 if l[mid] >= target:
                     right = mid
                 else:
                     left = mid + 1
             return left
         for i in range(1,len(nums)):
             if nums[i] > res[-1]:
                 res.append(nums[i])
             else:
                 res[binarySearch(res,nums[i])] = nums[i]
         return len(res)


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if not nums:
             return 0
         
         c = [nums[0]]
         
         for i in range(1,len(nums)):
             if nums[i]<=c[0]:
                 c[0] = nums[i] 
                 continue
             
             if nums[i]>c[-1]:
                 c.append(nums[i]) 
                 continue
             
             l = 0
             h = len(c)-1
             
             while l+1!=h:
                 m = (l+h)>>1
                 if nums[i]>c[m]:
                     l = m
                 else:
                     h = m
             c[h] = nums[i]
             
   
         
         return len(c)

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         tails = [0] * len(nums)
         size = 0
         for num in nums:
             i, j = 0, size
             while i != j:
                 m = i + (j - i) // 2
                 if tails[m] < num:
                     i = m + 1
                 else:
                     j = m
             tails[i] = num
             size = max(i+1, size)
         return size

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         tails = [0 for i in range(len(nums))]
         size = 0
         for x in nums:
             i, j = 0, size
             while i != j:
                 m = (i+j)//2
                 if tails[m] < x:
                     i = m+1
                 else: 
                     j = m
             tails[i] = x
             size = max(i+1, size)
         return size


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         tails = [0]*(len(nums))
         size=0
         for num in nums:
             i=0
             j=size
             while i!=j:
                 mid = (i+j)//2
                 if tails[mid]<num:
                     i = mid+1
                 else:
                     j = mid
             tails[j]=num
             size=max(i+1,size)
         return size
                     
             


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         dp = [float('inf')] * (n + 1)
         res = 0
         
         for num in nums:
             # like finding inerstion position             
             lo, hi = 1, n
             while lo < hi:
                 mi = int((lo + hi) / 2)
                 if dp[mi] < num:
                     lo = mi + 1
                 else:
                     hi = mi
             dp[lo] = num
             res = max(res, lo)
         return res


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         tails = []
         size = 0
         def search_tails(tails, n):
             if len(tails) == 0:
                 return 0
             l, r = 0, len(tails)
             while l < r:
                 m = (l+r)//2
                 if tails[m] < n:
                     l = m + 1
                 else:
                     r = m
             return l
             
         for n in nums:
             i = search_tails(tails, n)
             if i == len(tails):
                 tails.append(n)
             else:
                 tails[i] = n
         return len(tails)


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         tails = [0] * len(nums)
         size = 0
         for x in nums:
             i, j = 0, size
             while i != j:
                 m = (i + j) // 2
                 if tails[m] < x:
                     i = m + 1
                 else:
                     j = m
             tails[i] = x
             size = max(i + 1, size)
         return size       

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxLen = 0
         dp = []
         for i in nums:
             if not dp:
                 dp.append(i)
             pos = self.search(i, dp)
             if pos==len(dp): dp.append(i)
             else: dp[pos] = i
             maxLen = max(maxLen, len(dp))
         return maxLen
     
     def search(self, curr, nums):
         start = 0
         end = len(nums)-1
         if curr > nums[-1]: return len(nums)
         while end >= start:
             mid = int(start + (end-start)/2)
             if curr < nums[mid]:
                 end = mid-1
             elif curr > nums[mid]:
                 start = mid+1
             else:
                 return mid
         return start

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         tails = [0] * len(nums)
         size = 0
         
         for x in nums:
             i = 0
             j = size
             index_to_insert = i
             while i < j:
                 mid = i + (j - i) // 2
                 if tails[mid] < x:
                     i = mid + 1
                 else:
                     j = mid
             
             tails[i] = x
             size = max(size, i + 1)
         
         return size
     


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         if n <= 1: return n
         
         tails = [nums[0]]
         for i in range(1, n):
             x = nums[i]
             l, r = 0, len(tails)-1
             while(l < r):
                 mid = (l + r) // 2
                 if tails[mid] >= x:
                     r = mid
                 else:
                     l = mid + 1
             if tails[l] < x:
                 tails.append(x)
             else:
                 tails[l] = x
         return len(tails)

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         if n <= 1: return n
         
         tails = [nums[0]]
         for i in range(1, n):
             l, r = 0, len(tails)-1
             while(l < r):
                 mid = (l + r) // 2
                 if tails[mid] >= nums[i]:
                     r = mid
                 else:
                     l = mid + 1
             if tails[l] < nums[i]:
                 tails.append(nums[i])
             else:
                 tails[l] = nums[i]
         return len(tails)

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import bisect
         
         d = [0] * len(nums)
         
         maxLen = 0
         
         for n in nums:
           i = bisect.bisect_left(d, n, 0, maxLen)
           if i == maxLen:
             maxLen += 1
           d[i] = n
         return maxLen

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if nums == []:
             return 0
         dp = []
         for i, num in enumerate(nums):
             if i == 0 or num > dp[-1]:
                 dp.append(num)
             elif num < dp[0]:
                 dp[0] = num
             else:
                 low, high = 0, len(dp) - 1
                 while(low < high):
                     mid = (low + high)//2
                     mid_num = dp[mid]
                     if num > mid_num:
                         low = mid + 1
                     else:
                         high = mid
                 dp[low] = num
         return len(dp)


class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         lenLastIdx = [-1]
         for i in range(len(nums)):
             currLen = self.findLen(nums, lenLastIdx, nums[i])
             if len(lenLastIdx) == currLen:
                 lenLastIdx.append(0)
             lenLastIdx[currLen] = i
         return len(lenLastIdx) - 1
     
     def findLen(self, nums, lenLastIdx, val):
         p = 1
         q = len(lenLastIdx)
         while p < q:
             mid = p + (q - p) // 2
             if nums[lenLastIdx[mid]] >= val:
                 q = mid
             else:
                 p = mid + 1
         return p