LeetCode 300: Longest Increasing Subsequence

Problem Restatement

We are given an integer array nums.

We need to return the length of the longest strictly increasing subsequence.

A subsequence is formed by deleting some or no elements without changing the order of the remaining elements.

Strictly increasing means:

nums[i] < nums[j] for all i < j in the subsequence

We do not need to return the subsequence itself, only its length.

Input and Output

Function shape:

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

Examples

For:

nums = [10, 9, 2, 5, 3, 7, 101, 18]

One longest increasing subsequence is:

[2, 3, 7, 101]

Answer:

4

For:

nums = [0, 1, 0, 3, 2, 3]

Longest increasing subsequence:

[0, 1, 2, 3]

Answer:

4

For:

nums = [7, 7, 7, 7]

Answer:

1

First Thought: Dynamic Programming

Define:

dp[i] = length of LIS ending at index i

Transition:

For each i, check all j < i:

if nums[j] < nums[i]:
    dp[i] = max(dp[i], dp[j] + 1)

Code:

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

Time complexity is O(n^2).

Key Insight: Greedy + Binary Search

We maintain an array tails.

Interpretation:

• tails[k] = smallest possible tail of an increasing subsequence of length k+1.

We iterate through numbers and place each number into tails using binary search.

Rules:

• If num is larger than all tails, append it.
• Otherwise replace the first element in tails that is >= num.

This keeps subsequences flexible (small tails are better).

Algorithm

tails = []

For each number:

• Binary search position pos
• Replace or append

Correctness

We never care about actual subsequence, only best possible ending values for each length.

Keeping smaller tails is always better because it allows more future extensions.

Binary search ensures each update maintains sorted order of tails.

The size of tails equals the longest increasing subsequence length.

Complexity

Implementation

import bisect

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []

        for num in nums:
            pos = bisect.bisect_left(tails, num)

            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num

        return len(tails)

Code Explanation

We keep candidate subsequence tails:

tails = []

For each number, we find where it fits:

pos = bisect.bisect_left(tails, num)

If it extends the sequence:

tails.append(num)

Otherwise we replace:

tails[pos] = num

This maintains minimal tail values for each length.

Final answer:

return len(tails)

Testing

def test_lis():
    s = Solution()

    assert s.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert s.lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
    assert s.lengthOfLIS([7, 7, 7, 7]) == 1
    assert s.lengthOfLIS([1, 2, 3, 4, 5]) == 5
    assert s.lengthOfLIS([5, 4, 3, 2, 1]) == 1

    print("all tests passed")

test_lis()