Longest Increasing Subsequence

Difficulty: Medium Source: NeetCode

Problem

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

A subsequence is derived from an array by deleting some or no elements without changing the order of the remaining elements.

Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 (e.g. [2,3,7,101] or [2,5,7,101])

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

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Subsequences vs Substrings — elements don’t need to be contiguous
• DP on Indices — dp[i] depends on all dp[j] where j < i
• Binary Search (bisect) — used in the O(n log n) patience sorting approach

1. Dynamic Programming O(n²)

Intuition

dp[i] = length of the longest increasing subsequence ending at index i. For each element, look back at all previous elements: if nums[j] < nums[i], then we can extend the LIS ending at j by one. Take the maximum of all such extensions.

Algorithm

1. Initialize dp = [1] * n (each element is an LIS of length 1 by itself).
2. For each i from 1 to n-1:
   • For each j from 0 to i-1:
     • If nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1).
3. Return max(dp).

Solution

def lengthOfLIS_dp(nums):
    n = len(nums)
    dp = [1] * n

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

    return max(dp)


print(lengthOfLIS_dp([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(lengthOfLIS_dp([0, 1, 0, 3, 2, 3]))             # 4
print(lengthOfLIS_dp([7, 7, 7, 7]))                   # 1
print(lengthOfLIS_dp([1, 3, 6, 7, 9, 4, 10, 5, 6]))   # 6

Complexity

• Time: O(n²) — nested loops
• Space: O(n) — DP array

2. Patience Sorting with Binary Search O(n log n)

Intuition

Imagine playing solitaire where you build piles of cards. You place each card on the leftmost pile whose top card is greater than or equal to the current card. If no such pile exists, start a new pile.

The number of piles at the end equals the length of the LIS. We maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. This array stays sorted, so we can use binary search to find the right position for each new element.

This doesn’t reconstruct the actual LIS, but correctly counts its length.

Algorithm

1. Initialize an empty tails list.
2. For each number in nums:
   • Use binary search to find the leftmost position in tails where tails[pos] >= num.
   • If pos == len(tails), append num (new longer subsequence).
   • Otherwise, replace tails[pos] = num (better tail for this length).
3. Return len(tails).

Solution

import bisect

def lengthOfLIS(nums):
    tails = []  # tails[i] = smallest tail of LIS with length i+1

    for num in nums:
        # Find position to place num (replace first tail >= num)
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)


print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(lengthOfLIS([0, 1, 0, 3, 2, 3]))             # 4
print(lengthOfLIS([7, 7, 7, 7]))                   # 1  (strict: 7 >= 7, replaces)
print(lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6]))   # 6
print(lengthOfLIS([1]))                             # 1

Complexity

• Time: O(n log n) — n elements × binary search per element
• Space: O(n) — tails array

Common Pitfalls

Using bisect_right instead of bisect_left. Since we need strictly increasing, we use bisect_left to find the first position where the tail is >= num. Using bisect_right would allow non-strict increases.

Thinking tails represents an actual subsequence. The tails array is a bookkeeping structure — it’s not the actual LIS. Its length gives you the LIS length, but the elements might not form a valid increasing subsequence themselves.

Forgetting to handle all-equal arrays. For [7, 7, 7], every element would replace tails[0] because of strict inequality. The LIS length is 1, which is correct — no strictly increasing subsequence of length > 1 exists.