Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Longest Increasing Subsequence

Longest Increasing Subsequence explained: the O(n²) DP, then the O(n log n) tails-and-binary-search method, both tested in Python, with a live DP visual.

Also searched as: LIS dynamic programming · longest increasing subsequence O(n log n) · patience sorting LIS

🧮

Try it live Free

2D DP Table: LCS & Edit Distance

The DP Table lab makes overlapping subproblems visible for LCS; LIS is the 1D cousin, and in fact the LIS of an array equals the LCS of the array with its sorted, de-duplicated copy.

Also useful: Binary Search

Open the playground →

The problem

Given a list of integers, return the length of the longest strictly increasing subsequence: a subset of elements, kept in their original order, where each element is larger than the one before.

Input[10, 9, 2, 5, 3, 7, 101, 18]
Output4

For example 2, 3, 7, 101.

Input[7, 7, 7, 7]
Output1

Strictly increasing, so equal values do not chain.

The key insight

The classic DP says lis[i] = 1 + max(lis[j]) over earlier j with a smaller value, which is O(n²). The faster idea: keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. tails is always sorted, so each new number either extends it or replaces the first tail that is not smaller, found by binary search.

Brute force first: Checking all 2n subsequences for being increasing is exponential.

Step-by-step approach

  1. Start with an empty list tails.
  2. For each number x, binary-search the leftmost position i where tails[i] >= x.
  3. If i equals the length of tails, append x: it extends the longest subsequence.
  4. Otherwise set tails[i] = x: a subsequence of that length can now end lower, leaving more room to grow.
  5. The answer is len(tails). (Note: tails itself is not necessarily a valid subsequence.)

Python solution

PYTHON 3tested
from bisect import bisect_left


def length_of_lis(nums):
    tails = []                 # tails[k] = smallest tail of an LIS of length k+1
    for x in nums:
        i = bisect_left(tails, x)   # bisect_left -> strictly increasing
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Complexity

TimeO(n log n)
SpaceO(n)

Each of the n numbers does one binary search over tails, which never exceeds n elements. The simpler DP is O(n²) time.

Common mistakes

Frequently asked questions

What is the time and space complexity of Longest Increasing Subsequence?

The tails method runs in O(n log n) time and O(n) space. The straightforward DP is O(n²) time and O(n) space.

How do I print the actual increasing subsequence?

Use the O(n²) DP with a parent array (or store, for each element, the index it extended in the tails method), then follow parent links back from the best ending index.

Why does replacing a tail never break the answer?

A smaller tail for the same length is never worse: anything that could extend the old tail can also extend the new one. The length of tails only grows when a number is bigger than every tail.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.