🟨 Longest Increasing Subsequence (#300)

🔗 Problem Link

• LeetCode - Longest Increasing Subsequence
• NeetCode - Longest Increasing Subsequence

📋 Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

💡 Examples

Example 1

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

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

🔑 Key Insights & Approach

Core Observation: dp[i] = length of LIS ending at index i.

Why DP?

• O(n²) DP solution
• O(n log n) binary search solution
• For each element, check all previous smaller elements

Pattern: "LIS DP" pattern.

🐍 Solution: Python

Approach 1: DP

Time Complexity: O(n²) | Space Complexity: O(n)

from typing import List

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

        dp = [1] * len(nums)

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

        return max(dp)

Approach 2: Binary Search

Time Complexity: O(n log n) | Space Complexity: O(n)

from typing import List
import bisect

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

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

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

        return len(sub)

🔵 Solution: Golang

Approach: DP

Time Complexity: O(n²) | Space Complexity: O(n)

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }

    maxLen := 1

    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }

    return maxLen
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

📚 References

• NeetCode - Longest Increasing Subsequence