Domain 2MediumCORE

Longest Increasing Subsequence

We are given an integer array nums and need to find the length of its longest strictly increasing subsequence (LIS). A subsequence maintains relative order but does not require contiguous elements. 'Strictly' means duplicates cannot be part of the same sequence (e.g., [2, 3] is valid; [2, 3, 3] is invalid for length calculation purposes if we treat it as strictly increasing).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Binary Search#Dynamic Programming

300. Longest Increasing Subsequence

Model: qwen3.5:9b
Topics: Binary Search,Dynamic Programming
FAANG asked: 1
Acceptance rate: 44.5%


Problem Breakdown

We are given an integer array nums and need to find the length of its longest strictly increasing subsequence (LIS). A subsequence maintains relative order but does not require contiguous elements. “Strictly” means duplicates cannot be part of the same sequence (e.g., [2, 3] is valid; [2, 3, 3] is invalid for length calculation purposes if we treat it as strictly increasing).

Inputs: An integer array nums. Outputs: A single integer representing the maximum length. Constraints & Edge Cases:

  • Array size up to 2500 (allows O(N2)O(N^2), but interviewers expect optimization).
  • Values range from −104-10^4 to 10410^4 (standard integers, no overflow issues in Python).
  • Duplicates: Must be handled carefully; [7, 7] yields length 1.

Intuition

First, I consider the brute-force approach: generate all possible subsequences and check which is longest increasing. This takes O(2N)O(2^N) time due to exponential combinations—clearly infeasible for N=2500.

Next, Dynamic Programming (O(N2)O(N^2)). Let dp[i] be the length of LIS ending at index i. To compute dp[i], we iterate through all previous indices j < i. If nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1). This works but is quadratic.

To improve this, I look for a greedy property: For any length kk, do we want the LIS ending at index ii to be as large or small? We actually care about keeping the ending value of an increasing subsequence of length kk as small as possible. Why? Because a smaller tail makes it easier for future elements to extend that sequence (since they just need to be larger than the tail).

This leads to maintaining an auxiliary array, tails, where tails[k] stores the smallest ending element of all increasing subsequences of length k+1k+1. Since we always want the smallest possible end value, this array remains sorted. This allows us to use binary search instead of linear scanning for updates.

Approach

We maintain a list called subsequence_ends. We iterate through each number in nums:

  1. If the current number is greater than all elements currently tracked (i.e., larger than the last element), it extends our longest subsequence found so far. We append it to subsequence_ends.
  2. Otherwise, we find the first element in subsequence_ends that is ≥\ge the current number and replace it with the current number. This “lowers” the tail for a specific length without changing the maximum length achieved yet.

This replacement logic ensures that if multiple subsequences of the same length exist, we keep track of the one ending with the smallest value (greedy optimization). Since subsequence_ends is always sorted in ascending order, finding this position takes O(log⁡N)O(\log N) using binary search (bisect_left).

Complexity Analysis

  • Time: O(Nlog⁡N)O(N \log N). We iterate through each of the NN elements once. For each element, we perform a binary search on subsequence_ends, which has size at most NN, taking log⁡N\log N. Total: N×log⁡NN \times \log N.
  • Space: O(N)O(N) to store the subsequence_ends array in the worst case (strictly increasing input).

Solution

import bisect

def lengthOfLIS(nums):
    # 'tails' will store the smallest tail of all increasing subsequences 
    # of length i+1 at index i. It remains sorted, allowing binary search.
    tails = []
    
    for num in nums:
        if not tails or num > tails[-1]:
            # If current number is larger than any existing subsequence end,
            # it extends the longest one found so far.
            tails.append(num)
        else:
            # Otherwise, replace the first element >= num with 'num'.
            # This maintains the smallest possible tail for that length.
            idx = bisect.bisect_left(tails, num)
            if idx < len(tails):
                tails[idx] = num
                
    return len(tails)

Edge Cases Handled

  • Single Element: The loop runs once; tails becomes [num], returns length 1. Correct.
  • All Duplicates (e.g., [7, 7]): First 7 appends to tails ([7]). Second 7 triggers replacement at index 0 with itself or no change effectively since it’s not greater than tails[-1]. Length remains 1. Correct for strictly increasing.
  • Decreasing Sequence (e.g., [5,4]): First element [5], second replaces 5 with 4 ([4]). Returns length 1. Correct.