Medium

Longest Increasing Subsequence

064

Return the length of the longest strictly increasing subsequence.

EXAMPLES

Example 1

Input
{
  "nums": [
    10,
    9,
    2,
    5,
    3,
    7,
    101,
    18
  ]
}

Output
4

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Maintain array where tails[i] = smallest ending value of all increasing subsequences of length i+1. Binary search to find position for new element.

Reveal reference solution +

pythonREFERENCE

def lengthOfLIS(self, nums: List[int]) -> int:
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗