MediumArrayBinary SearchDynamic ProgrammingUpdated Sep 2026

300. Longest Increasing Subsequence

Asked at Atlassian

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an integer array nums. Return the length of the longest strictly increasing subsequence.

A subsequence is what you get by deleting some elements (possibly none) from the array while keeping the remaining elements in their original order. It does not have to be a contiguous block. Strictly increasing means every element is larger than the one before it — equal values are not allowed.

You only need to return the length, not the subsequence itself. The follow-up asks for an O(n log n) solution, which is the one described below.

Subsequence, not subarray

nums109253710118012345672, 3, 7, 101 is increasing and keeps the original order — length 4
We may skip elements, but the chosen values must stay in order and strictly grow.

Constraints

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

Examples

Example 1
Inputnums = [10,9,2,5,3,7,101,18]
Output4
WhyOne valid choice is 2, 3, 7, 101. These appear in order in the array and each value is bigger than the previous one, so the length is 4. No longer increasing subsequence exists.
Example 2
Inputnums = [0,1,0,3,2,3]
Output4
WhyPick 0, 1, 2, 3 (the last 3). The order in the array is kept and the values strictly grow, giving length 4.
Example 3
Inputnums = [7,7,7,7,7,7,7]
Output1
WhyAll values are equal, so no two of them can be strictly increasing. The best we can do is a single element, length 1.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

DP approach: dp[i] = length of LIS ending at index i. For each i, check all j < i. If nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1). Time: O(n²). Good but not optimal.

2

Binary search optimization: maintain a tails array where tails[k] = smallest possible tail of all increasing subsequences of length k+1. This array is always sorted, so binary search works.

3

For each number in nums: if it's larger than all elements in tails, append it (extends the longest subsequence). Otherwise, use binary search to find the first element >= num in tails and replace it. This keeps tails minimal for future extensions.

4

Why replacing works: replacing a larger tail with a smaller one doesn't change the length of any existing subsequence, but it gives future numbers a better chance of extending. tails is NOT the actual LIS, just a tool to track length.

5

Time: O(n log n) (n iterations, each with O(log n) binary search). Space: O(n) for the tails array.

Optimal Approach

Binary search with tails array:

  1. Initialize tails as empty.
  2. For each num in nums:
    a. If tails is empty or num > last element of tails, append num.
    b. Otherwise, use binary search to find the first element in tails >= num, and replace it with num.
  3. Return length of tails.

Binary search: use left = 0, right = len(tails) - 1. While left <= right, compute mid. If tails[mid] >= num, go left. Else go right. Replace at left.

Walkthrough: nums = [0, 8, 4, 12, 2].

  • 0: tails = [0]
  • 8: append. tails = [0, 8]
  • 4: replace 8. tails = [0, 4]
  • 12: append. tails = [0, 4, 12]
  • 2: replace 4. tails = [0, 2, 12]
    Length = 3. LIS: [0, 4, 12] or [0, 2, 12].

Time: O(n log n). Space: O(n).

Patience sorting with a tails array

tails2371010123After 101 we have a run of length 4; the next number18 replaces 101tails23718012318 is smaller than 101, so it takes that slot andkeeps the tail as small as possiblenum > tails[-1] → appendelse → replace first tails[i] >= numanswer = len(tails)
tails[k] is the smallest possible last value of an increasing subsequence of length k+1.
ComplexityTime O(n log n)Space O(n)We loop over n numbers and each one costs one binary search over the tails array, which is at most n long.

What Trips People Up in Real Interviews

1

Confusing subsequence with subarray. A subsequence does NOT need to be contiguous. [2, 3, 7, 101] is a valid subsequence of [10, 9, 2, 5, 3, 7, 101, 18] even though the indices aren't consecutive.

2

Thinking tails stores the actual LIS. It doesn't. tails stores the minimum possible tail for each length. The actual LIS can be reconstructed by tracking predecessors, but the problem only asks for length.

3

Using binary search incorrectly. You need bisect_left (find first >= num), not bisect_right (find first > num). Using bisect_right fails on duplicate values and doesn't maintain the strictly increasing property.

4

Forgetting that tails is sorted. If you don't maintain the sorted invariant, binary search won't work. Appending when num > all tails and replacing otherwise maintains sorted order.

5

Trying to return tails as the answer. The length of tails is the answer, not tails itself. For example, tails = [2, 3, 7, 18] but the actual LIS is [2, 3, 7, 101].

Solution Code

O(n log n) time
import bisect

def lengthOfLIS(nums):
    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)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest Increasing Subsequence problem?

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order. The `O(n log n)` solution uses patience sorting with binary search.

How do you solve Longest Increasing Subsequence?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Increasing Subsequence?

Longest Increasing Subsequence is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Longest Increasing Subsequence?
  • Confusing subsequence with subarray. A subsequence does NOT need to be contiguous. [2, 3, 7, 101] is a valid subsequence of [10, 9, 2, 5, 3, 7, 101, 18] even though the indices aren't consecutive.
  • Thinking `tails` stores the actual LIS. It doesn't. `tails` stores the minimum possible tail for each length. The actual LIS can be reconstructed by tracking predecessors, but the problem only asks for length.
  • Using binary search incorrectly. You need `bisect_left` (find first >= num), not `bisect_right` (find first > num). Using `bisect_right` fails on duplicate values and doesn't maintain the strictly increasing property.
  • Forgetting that `tails` is sorted. If you don't maintain the sorted invariant, binary search won't work. Appending when num > all tails and replacing otherwise maintains sorted order.
  • Trying to return `tails` as the answer. The length of `tails` is the answer, not `tails` itself. For example, `tails = [2, 3, 7, 18]` but the actual LIS is [2, 3, 7, 101].