What is the brute force approach and complexity for Longest Increasing Subsequence?

Recurse over the numbers: skip one, or take it if it is bigger than the last one taken with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Longest Increasing Subsequence?

Keep the smallest possible end for each chain length; each number costs one binary search with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Longest Increasing Subsequence?

Look for key signals in the prompt: "subsequence" indicates Numbers can be skipped, so the chain is any set of positions in order. It is not a window of neighbours.; "strictly increasing" indicates Each new number must be bigger than the last one in the chain. Equal numbers break the chain, so the check is <, not <=.; "length of the longest" indicates We want a length, so each end keeps its best length, and the answer is the best of all ends..

Longest Increasing Subsequence

Medium·LeetCode #300Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLongest Increasing Subsequence (classic: dp per end, or tails with binary search)

Complexity:O(2^N)→O(N log N)

Key Insight

Keep an array tails. tails[k] is the smallest value that can end an increasing chain of length k + 1. For each number x, binary search for the first tail that is at least x. If there is none, append x, since it makes a longer chain. Otherwise replace that tail with x, which keeps the same length with a smaller end.

Core Validity Invariant

tails[k] is always the smallest possible end of a chain of length k + 1, so each new number can be placed with one binary search.

Problem

You are given a list of whole numbers nums.

A subsequence keeps the original order, but it may skip numbers. Find the length of the longest subsequence where every number is strictly bigger than the one before it.

Follow-up: can you do better than comparing each number with all the numbers before it?

Input

An integer array nums.

Output

One number: the length of the longest strictly increasing subsequence.

Example 1

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

One longest chain is 2, 3, 7, 101. Another is 2, 3, 7, 18. No chain has 5 numbers.

Example 2

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

Output: 4

The chain 0, 1, 2, 3 uses the items at positions 0, 1, 4 and 5. It skips the other items.

Example 3

Input: nums = [7, 7, 7, 7, 7, 7, 7]

Output: 1

Equal numbers do not count as increasing, so every chain has one number.

Constraints

• 1 ≤ nums.length ≤ 2500
• −10^4 ≤ nums[i] ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A subsequence can skip numbers. Does the chain have to sit next to itself in the list?
2.
If I decide that the chain ENDS at this number, what must the number just before it in the chain look like?
3.
Two numbers are equal. Can both be in a strictly increasing chain?
4.
If I know the longest chain for every ending position so far, how could I get the answer for the next position from them?
5.
Is the answer always the chain that ends at the last number? Try [3, 1, 2] and check.

Brute force approach

Idea

Walk through the numbers from left to right. For each one, either skip it, or take it when it is bigger than the last number taken. Every path that reaches the end is one chain. Keep the longest one. The rule only looks at the last number taken, so the recursion carries that one index.

Thinking process

1
Take nums = [1, 3, 2]. Take 1, since nothing was taken yet. Then 3 is bigger than 1, so take it: the chain 1, 3 has length 2.
2
Now skip 3 instead. Then 2 is bigger than 1, so take it: the chain 1, 2 also has length 2.
3
Taking 3 and then 2 is not allowed, because 2 is not bigger than 3. That branch is cut.
4
Every path has been tried, and the best one has length 2. So the answer is 2.

Visual

Each circle is one call, written i|last: i = the next index to decide, last = index of the last item taken (- = none). Blue = the calls now open. ✗ = take cut, because the last item is not smaller. Orange = a state already solved on another branch.

Brute force: take or skip, remember the last item takennums = [1, 3, 2]step 1/23

calls

nums

▲i

State

next index i: 0
last taken: none
calls: 1
repeated calls: 0

Decide nums[0] = 1

Skip nums[0] = 1, or take it if it is bigger than the last item taken.

Code & Implementation

brute.cpp

class Solution {
    // best(i, prev): the longest increasing chain that uses only nums[i..], given that the
    // last item taken so far is nums[prev]. prev = -1 means nothing is taken yet.
    int best(vector<int>& nums, int i, int prev) {
        if (i == (int)nums.size()) return 0;           // no items left to take
        int skip = best(nums, i + 1, prev);            // leave nums[i] out
        int take = 0;
        if (prev == -1 || nums[prev] < nums[i])        // nums[i] must be bigger than the last one taken
            take = 1 + best(nums, i + 1, i);           // take it: i is now the last one taken
        return max(skip, take);
    }

public:
    int lengthOfLIS(vector<int>& nums) {
        return best(nums, 0, -1);
    }
};

Complexity

Time O(2^N)Space O(N)

Each number is either skipped or taken, so there are at most 2^N paths. The recursion goes at most N levels deep, so the space is O(N).

Better approach

Why brute force is slow

The brute force keeps the whole path, so each call re-explores the rest of the list for every chain that reaches it.

What repeated work are we doing?

In the brute tree for [1, 3, 2], the state (next index 2, last taken index 1) is reached on two different paths, so its answer is worked out twice.

What information can we reuse?

dp[j] already holds the best chain that ends at each earlier number. For a new number, we only need one value from each earlier j, and each dp value is computed once.

New approach

Idea

Fix the end of the chain instead of the whole path. Let dp[i] be the length of the longest increasing chain that ends at nums[i]. Then dp[i] is 1 plus the largest dp[j] over earlier numbers j with nums[j] < nums[i], or 1 if there is no such j. Each dp[i] is one number, filled in once.

Thinking process

1
nums = [10, 9, 2, 5]. dp[0] = 1, the chain 10 alone. dp[1] = 1: 9 is not bigger than 10, so 9 starts its own chain.
2
dp[2] = 1: 2 is smaller than 10 and 9, so neither can come before it.
3
dp[3] = 2: 5 can follow 2, because 2 < 5. So dp[3] = dp[2] + 1 = 2. It cannot follow 10 or 9, since they are bigger.
4
The answer is the largest dp value, not the value at the last index. Try [1, 2, 3, 0]: dp = [1, 2, 3, 1]. The chain 1, 2, 3 ends at index 2, so the answer is 3, not dp[3] = 1.

Visual

The input is the top track; dp is the bottom track, with the same indices. Blue = an earlier item that is smaller than nums[i] (a candidate for the chain before it). Red = an earlier item that is not smaller (cannot come before). Green = dp already filled. The pointer j is the candidate that gives the longest chain.

Better: dp[i] = longest chain that ends at inums = [10, 9, 2, 5, 3, 7, 101, 18]step 1/9

nums

101

▲i

Step

i: 0
nums[i]: 10
best earlier j: none
dp[i]: 1
answer so far: 1

Check each earlier j

no earlier items: dp[i] = 1

10 starts a chain: dp = 1

No earlier smaller number, so 10 can only start a chain of length 1.

Code & Implementation

better.cpp

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // dp[i] = length of the longest increasing chain that ENDS at nums[i].
        vector<int> dp(n, 1);                          // nums[i] alone is a chain of length 1
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i])                 // nums[j] can sit right before nums[i]
                    dp[i] = max(dp[i], dp[j] + 1);
            answer = max(answer, dp[i]);               // the chain can end anywhere, not only at the last item
        }
        return answer;
    }
};

Complexity

Time O(N^2)Space O(N)

For each i we check every earlier j, which is about N²/2 comparisons. The dp array holds N values.

Optimized approach

Idea

Start from brute force

The brute force decides take or skip for each number, and the state (next index, last taken) is worked out again on different paths. The dp version fixes the end of the chain, so each index is solved once. The tails version goes one step further: for each length it keeps only the smallest end.

Find the repeated work

The dp version checks every earlier j for every i, which is about N² pairs. The tails version needs only one binary search per number, because most ends never have to be stored.

Define the state — what variables do I need?

tails[k]: The smallest value that can end an increasing chain of length k + 1, using the numbers seen so far. tails stays strictly increasing.
pos: The first index where tails[pos] is at least x (a lower_bound). This is where x goes.
tails.size(): The length of the longest increasing chain seen so far. At the end, this is the answer.

Define validity

tails[k] is always the smallest possible end of a chain of length k + 1, so each new number can be placed with one binary search.

Define the transitions — when does each pointer move, and why is it safe?

x is bigger than every tail (lower_bound returns the end)

Append x to tails

x extends the longest chain by one. No other entry changes.

lower_bound gives pos with tails[pos] at least x

Set tails[pos] = x

tails[pos - 1] is below x, so x can end a chain of length pos + 1, and x is smaller than the old tail. Longer chains built on the old tail still work with the smaller end.

Before the loop

tails = []

No numbers are seen yet, so no chains exist.

What does the current window add to the answer?

After each number, tails.size() is the length of the longest chain seen so far. The values in tails are only the best ends for each length. They are not always a real chain, so do not print them as the answer (see the mistakes).

Code & Implementation

optimal.cpp

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // tails[k] = the smallest value that can end an increasing chain of length k + 1 so far.
        // tails is NOT the LIS itself. Its length is the answer; its values are only the best tails.
        vector<int> tails;
        for (int x : nums) {
            // First tail that is >= x. Strictly increasing chains cannot use an equal value,
            // so x must replace that tail (or the equal one), never go after it.
            auto pos = lower_bound(tails.begin(), tails.end(), x);
            if (pos == tails.end()) tails.push_back(x);   // x extends the longest chain so far
            else *pos = x;                                // x gives a chain of the same length a smaller tail
        }
        return (int)tails.size();
    }
};

Complexity

Time O(N log N)Space O(N)

Each number does one binary search over tails, which holds at most N values. tails is not itself an increasing chain, so only its length is the answer.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse over the numbers: skip one, or take it if it is bigger than the last one taken	O(2^N)	O(N)
Better	dp[i] = 1 + the best dp[j] over earlier smaller j; each dp[i] is filled once	O(N^2)	O(N)
Optimal	Keep the smallest possible end for each chain length; each number costs one binary search	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“subsequence”Numbers can be skipped, so the chain is any set of positions in order. It is not a window of neighbours.
“strictly increasing”Each new number must be bigger than the last one in the chain. Equal numbers break the chain, so the check is <, not <=.
“length of the longest”We want a length, so each end keeps its best length, and the answer is the best of all ends.

Subsequence (skip allowed)+each number extends a smaller earlier end+keep the best length per end, or the smallest end per length→Longest Increasing Subsequence (classic: dp per end, or tails with binary search)

This is the anchor of the pattern. The key rule is that dp[i] only looks at earlier smaller items, so each end is solved from the ends before it. The answer is not always at the last index: the answer is the best length over all ends. The other classic questions in this subpattern change the validity rule (a fixed length, a sum, or a count), so this one is the base for all of them.

Don't make this mistake

Pattern confusion: a contiguous run instead of a subsequence

✗ int run = 1, best = 1; for (int i = 1; i < n; i++) { run = nums[i] > nums[i - 1] ? run + 1 : 1; best = max(best, run); }

✓ for (int j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);

The wrong version only looks at neighbours, so it is a longest increasing subarray. On [10, 9, 2, 5, 3, 7, 101, 18] it finds the run 3, 7, 101 and prints 3. The right answer is 4: the chain 2, 3, 7, 101 skips the 5 between 2 and 3.

upper_bound instead of lower_bound with equal values

✗ auto pos = upper_bound(tails.begin(), tails.end(), x);

✓ auto pos = lower_bound(tails.begin(), tails.end(), x);

upper_bound moves past an equal tail, so an equal number gets appended. On [1, 3, 3, 3] the wrong version builds tails = [1], [1, 3], [1, 3, 3], [1, 3, 3, 3] and prints 4. The right answer is 2 (1, 3), because a strictly increasing chain cannot use two 3s.

Using <= in the dp check

✗ if (nums[j] <= nums[i]) dp[i] = max(dp[i], dp[j] + 1);

✓ if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);

With <=, each 7 chains onto the 7 before it. On [7, 7, 7] the dp values become 1, 2, 3 and the answer is 3. The right answer is 1, because equal numbers are not strictly increasing.

Treating tails as the chain itself

✗ // rebuild the answer from the tails array return tails;

✓ // tails only gives the length return tails.size();

The length of tails is right, but its values are not always a chain in the input order. On [2, 3, 1, 4], tails ends as [1, 3, 4]. Those three values are not in order in the list (1 comes after 3), so they are not a subsequence. The real longest chain is 2, 3, 4. To rebuild a real chain you need to keep a parent link for each number.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture