Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

13 Core Algorithmic Patterns & 225 Practice Problems

  • 1. Two Pointers (16 Paradigms, 43 Problems): Opposite ends, sorted pair sums, palindrome verification, trapping rain water, 3Sum, container with most water — includes the Sliding Window and Fast & Slow Pointers paradigms (contiguous subarray invariants, longest substrings, Floyd's cycle detection, linked list middle).
  • 2. Binary Search (9 Paradigms, 14 Problems): Monotonic predicate partitioning (feasible(x)), boundary search, rotated sorted arrays, square roots, minimum ship capacity, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (5 Paradigms, 11 Problems): Counting set bits, XOR cancellation, bit reversal, bitmask pairing, maximum XOR with a bitwise trie.
  • 4. Math & Geometry (8 Paradigms, 14 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (15 Paradigms, 24 Problems): Path sums, lowest common ancestor, tree diameter, validating BSTs, tree DP (House Robber III, Binary Tree Cameras).
  • 6. Tree/Graph Breadth-First Search (5 Paradigms, 12 Problems): Level-order traversals, shortest path in unweighted graphs, zig-zag traversals, rotting oranges, word ladders.
  • 7. Graphs (12 Paradigms, 22 Problems): Topological sort, cycle detection, Dijkstra's algorithm, bipartite graph validation, network delay.
  • 8. Backtracking (6 Paradigms, 14 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens, Sudoku solver.
  • 9. Dynamic Programming (13 Paradigms, 28 Problems): Memoization vs tabulation, 0/1 knapsack, unbounded knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (9 Paradigms, 11 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (7 Paradigms, 17 Problems): Trie (prefix tree), Union-Find (Disjoint Set Union), LRU Cache, LFU Cache, range-sum queries with updates.
  • 12. Stack (5 Paradigms, 9 Problems): Next greater element, largest rectangle in histogram, remove k digits, decode string, min stack.
  • 13. Intervals & Greedy (2 Paradigms, 6 Problems): Merge intervals, interval scheduling, meeting rooms by sweep line, jump game.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Read the pattern's mental model, loop invariant and Big-O proof, compare the pattern's template with the problem's solution side by side, and use the step-by-step debugger. The solution can also be shown in C#, Java, TypeScript, C++, Go or Rust for almost every problem.
  2. Stage 2 (Active Recall): Rebuild the solution from memory in a code editor, with an invariant checklist and optional progressive hints, and check it against a judged test suite.
  3. Stage 3 (AI Interview Coach, coming soon): A mock-interview stage still in development; for now, students go straight from Stage 2 to Stage 4.
  4. Stage 4 (Solve on Your Own): Solve a new problem on your own against a 15-minute timer; your code is graded against a test suite. Python and TypeScript run in your browser and C# runs on our server (design problems grade in Python and TypeScript).

Equipped with a spaced-repetition review hub on a fixed 7-step schedule (1 day up to 90 days), a two-pane Studio workspace, and study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Coins: New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins.
  • AI Coach: Each AI coach question costs 1-5 coins, priced by the server according to its size.
  • BYOK (Bring Your Own Key): AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK).
  • Extras: Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1).
  • Payments & Refunds: Nothing on the site is sold for money: coins can only be earned, never bought. There are no subscriptions or charges, so there is nothing to refund.
  • Platform Operator: Hi👋WebEnterprise. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

Arena
238Items
Theory Context•Dynamic Programming

Builds on Linear DP and Lower Bound, which you haven’t finished yet.

P2MediumMental model~3 min speedrun

Longest Increasing Subsequence (Patience Sorting)

The problem

Longest Increasing Subsequence (LC 300)(opens leetcode.com)

You're given an integer array nums. Deleting any subset of its elements (possibly none) while keeping the rest in their original order produces a subsequence.

Find the length of the longest subsequence you can produce this way whose values keep strictly increasing from left to right.

Example 1
Input:nums = [10,9,2,5,3,7,101,18]
Output:4
The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

LIS

array ➔ tails array maintenance ➔ binary search replacement
Spot it when: You need the longest strictly increasing chain in a sequence, or pairs and envelopes that become one after sorting.
LIS
Python
1import bisect
2 
3def length_of_lis(nums: list[int]) -> int:
4 """Longest Increasing Subsequence via Patience Sorting.
5 Time: O(N log N) | Space: O(N)
6 """
7 # tails: sorted; tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far
8 tails: list[int] = []
9 
10 for x in nums:
11 # 1. Find Where x Fits:
12 # bisect_left finds the first tail >= x, the pile x can legally extend or replace.
13 idx = bisect.bisect_left(tails, x)
14 if idx == len(tails):
15 # 2. Start A Longer Subsequence:
16 # No tail is >= x, so x extends the longest subsequence found so far by one.
17 tails.append(x)
18 else:
19 # 3. Lower An Existing Tail:
20 # x is smaller than tails[idx], so it leaves more room for later values at this same length.
21 tails[idx] = x
22 
23 return len(tails)
Invariant: tails is sorted, and tails[k] is the smallest last value of any increasing subsequence of length k + 1 among the numbers seen so far.

Keep tails[k] as the smallest last value of any increasing subsequence of length k + 1, and for each x replace the first tail that is >= x (found with bisect_left), or append x when there is none. A smaller tail can only help, because it leaves more room for the values that come later, and replacing never breaks the order of tails, so len(tails) is always the longest length reached so far. The trap is reading tails as the answer: it has the right length but is usually not a real subsequence, so store each element's predecessor index when you must rebuild the sequence.

See it run

Longest Increasing Subsequence with tails, step by step

tails [] · len(tails) 0

tails [10] · len(tails) 1

tails [9] · len(tails) 1

tails [2] · len(tails) 1

tails [2, 5] · len(tails) 2

tails [2, 3] · len(tails) 2

tails [2, 3, 7] · len(tails) 3

tails [2, 3, 7, 101] · len(tails) 4

tails [2, 3, 7, 18] · len(tails) 4

tails [2, 3, 7, 18] · len(tails) 4 · answer 4

In the nums row each column is an index i. In the tails row each column is a position k in the list tails.

  • x the number being read
  • idx the tail that x replaces
  • idx (new) the new tail that x adds at the end
  • < x a tail that is smaller than x, so it stays unchanged
  • tail a tail that is counted in the final answer

Start: tails = [], an empty sorted list. No increasing subsequence exists yet.

x = 10: bisect_left gives idx = 0, which equals len(tails). So 10 is larger than every tail, and it is appended.

x = 9: bisect_left gives idx = 0, because tails[0] = 10 is the first tail that is at least 9. So write tails[0] = 9.

x = 2: bisect_left gives idx = 0, because tails[0] = 9 is the first tail that is at least 2. So write tails[0] = 2.

x = 5: bisect_left gives idx = 1, which equals len(tails). So 5 is larger than every tail, and it is appended.

x = 3: bisect_left gives idx = 1, because tails[1] = 5 is the first tail that is at least 3. So write tails[1] = 3.

x = 7: bisect_left gives idx = 2, which equals len(tails). So 7 is larger than every tail, and it is appended.

x = 101: bisect_left gives idx = 3, which equals len(tails). So 101 is larger than every tail, and it is appended.

x = 18: bisect_left gives idx = 3, because tails[3] = 101 is the first tail that is at least 18. So write tails[3] = 18.

Done: the function returns len(tails) = 4. The list tails is not necessarily one real subsequence.

nums
010
19
22
35
43
57
6101
718
tails
1 / 10
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Returning tails as the subsequence

    Mistake
    return tails
    Fix
    return len(tails)

    What happens: tails[k] is the smallest last value of any increasing subsequence of length k + 1. Its length is right. Its values can come from different subsequences, in the wrong order. To rebuild a real subsequence, store each element's predecessor index.

    Example: nums = [3, 4, 1]
    Mistake: returns [1, 4]Fix: returns 2
  2. 2

    Gotcha 2: Using bisect_right for a strictly increasing subsequence

    Mistake
    idx = bisect.bisect_right(tails, x)
    Fix
    idx = bisect.bisect_left(tails, x)

    What happens: bisect_left finds the first tail that is greater than or equal to x, so an equal value replaces it. bisect_right finds the first tail that is strictly greater than x. An equal value is then appended, so a run of equal values counts as increasing. Use bisect_right only when the problem allows equal neighbours.

    Example: nums = [2, 2, 2]
    Mistake: returns 3Fix: returns 1
  3. 3

    Gotcha 3: Sorting envelopes of equal width by ascending height

    Mistake
    envelopes.sort()
    Fix
    envelopes.sort(key=lambda e: (e[0], -e[1]))

    What happens: In Russian Doll Envelopes (LC 354), an envelope fits only when both its width and height are smaller. After sorting by width, the LIS runs on the heights. With equal widths in ascending height order, the LIS can nest one inside the other. Heights in descending order stop that.

    Example: Russian Doll Envelopes (LC 354): envelopes = [[1, 1], [1, 2]]
    Mistake: returns 2Fix: returns 1
Not this one if…
  • The chain must follow the order of a second sequence rather than rising values, as in Longest Common Subsequence (LC 1143): there is no sorted order to search in. See Two-Sequence DP

Deep Dive

From the slow table to tails

The first solution is a table. dp[i] is the length of the longest increasing subsequence that ends at index i. For each i, check every earlier j with nums[j] < nums[i] and take dp[j] + 1. This is correct, and it costs O(N^2) time. For N = 2500, there are 3,123,750 pairs.

The card keeps a different state. tails[k] is the smallest last value of any increasing subsequence of length k + 1. One array of that kind is enough, because only the smallest last value matters for each length.

Why is the smallest last value enough? Two subsequences of the same length are equal for the future, except for their last value. The one with the smaller last value accepts every later number that the other accepts, and possibly more. So the larger one can be forgotten.

Why tails stays sorted, and why the length is the answer

For each x, bisect_left returns the first index idx with tails[idx] >= x. Then tails[idx - 1] < x <= tails[idx]. Writing x into tails[idx] keeps the array sorted, because x is larger than its left neighbour and not larger than the old value.

A sorted array is what allows a binary search on the next number.

If no tail is >= x, then x is larger than every tail, so x extends the longest subsequence by one, and append is correct. Otherwise x lowers the tail for length idx + 1, which can only help later numbers.

Example: for nums = [10, 9, 2, 5, 3, 7, 101, 18], tails changes as [10], [9], [2], [2, 5], [2, 3], [2, 3, 7], [2, 3, 7, 101], [2, 3, 7, 18]. The final length is 4.

The length of tails only grows when x is larger than all tails. That happens exactly when a longer increasing subsequence now exists. So len(tails) is the longest length reached so far.

tails is not a subsequence

Each entry of tails is the end of some subsequence, but the entries can come from different ones. For nums = [3, 4, 1], the final tails is [1, 4]. The values 1 and 4 are in the wrong order in nums, because 1 comes after 4. The length 2 is correct, as [3, 4] is a real subsequence of that length.

To return a real subsequence, store the index of the number in each tail, and store for each index the tail to its left at the time it was placed. Then follow these links back from the last tail.

For nums = [10, 9, 2, 5, 3, 7, 101, 18], that method returns [2, 3, 7, 18].

The cost: N searches of size log N

Each of the N numbers does one bisect_left on an array of at most N entries, which takes O(log N) steps. The append or the replacement is O(1). So the time is O(N log N).

The space is O(N) for tails in the worst case, where the input is already increasing. Rebuilding the subsequence adds O(N) for the links.

Strict and non-strict order differ by one function. bisect_left gives a strictly increasing subsequence, so equal values replace each other. bisect_right gives a non-decreasing subsequence, so equal values are appended. For [2, 2, 2], the lengths are 1 and 3.

60-Second Pitch

"The simple solution stores, for each index, the longest increasing subsequence that ends there. It compares every pair, so it takes O(N^2) time. I can do better with one observation. For each length, only the smallest last value matters, because it accepts the most later numbers. So I keep tails, where tails[k] is the smallest last value of any increasing subsequence of length k + 1. This array is always sorted. For each number I use bisect_left to find the first tail that is greater than or equal to it. I replace that tail, or I append the number when none exists. The answer is the length of tails. That is N binary searches, so O(N log N) time and O(N) space. If you need the subsequence itself, I store a link for each index."

Common Questions

Why does the array tails stay sorted?

bisect_left returns the first index idx where tails[idx] >= x, so tails[idx - 1] < x. The new value fits between its two neighbours. When x is larger than all tails, it goes at the end. In both cases the order is kept, so the next binary search is valid.

What are the time and space complexity?

O(N log N) time, because each of the N numbers needs one binary search over at most N entries. The space is O(N) for tails. The simple table solution takes O(N^2) time and O(N) space.

How do you return the subsequence and not only its length?

Store the index of each tail value, and for each index store the index of the tail to its left at the moment it was placed. After the loop, start at the last tail and follow these links back, then reverse the result. The array tails alone is not enough, because its values can come from different subsequences.

How do you change the solution for a non-decreasing subsequence?

Replace bisect_left with bisect_right. Then an equal value is appended after the equal tails instead of replacing one. For [2, 2, 2] the result changes from 1 to 3.

How does Russian Doll Envelopes (LC 354) use this?

An envelope fits into another only when both width and height are smaller. Sort the envelopes by width ascending. For equal widths, sort by height descending, so two envelopes of the same width never form an increasing pair. Then the longest strictly increasing subsequence of the heights is the answer.

SWE Reasoning

Spot it

  • You must find the longest strictly increasing chain in a sequence, and the chain keeps the original order.
  • An O(N^2) table is too slow, because N can be too large for N^2 steps.
  • Pairs or boxes must be nested in both dimensions, as in Russian Doll Envelopes (LC 354). Sorting by one dimension turns the problem into an increasing subsequence on the other.
  • You need a length, not the number of such subsequences. For the count, as in Number of Longest Increasing Subsequence (LC 673), a plain table is used.
  • Among subsequences of the same length, the one with the smaller last value is always at least as good.

The invariant, step by step

  1. tails starts empty. The invariant holds, because no number has been seen.
  2. A number x arrives. bisect_left(tails, x) finds idx, the first tail that is >= x.
  3. If idx == len(tails), every tail is smaller than x. So x can follow the longest subsequence. The code appends x, and a new length now exists.
  4. Otherwise tails[idx] >= x. A subsequence of length idx + 1 can end at x, and x is not larger than the old tail. The code writes tails[idx] = x.
  5. In both cases tails is still sorted, because tails[idx - 1] < x <= tails[idx].
  6. After all numbers, tails[k] is the smallest last value for length k + 1, and len(tails) is the longest length. The code returns len(tails).

Traps

  • Return tails. It has the right length, but its values can come from different subsequences. For [3, 4, 1], it is [1, 4]. Return len(tails), or store links to rebuild a real subsequence.
  • Use bisect_right for a strict order. Equal values are then appended, and [2, 2, 2] gives 3 instead of 1.
  • Use bisect_left when equal values are allowed. The problem then wants a non-decreasing subsequence, and bisect_left returns too small a length.
  • Sort envelopes of equal width by ascending height. Two envelopes with the same width then look nestable. Sort by width ascending and by height descending.
  • Binary search on the table. The values dp[i] of the O(N^2) table are not sorted, so bisect on them gives wrong answers. Search tails, which is sorted.

Practice

Canonical LeetCode:Longest Increasing Subsequence (LC 300)Russian Doll Envelopes (LC 354)Maximum Length of Pair Chain (LC 646)Best Team With No Conflicts (LC 1626)Increasing Triplet Subsequence (LC 334)Longest Arithmetic Subsequence of Given Difference (LC 1218)
Theory Context•Dynamic Programming

Builds on Linear DP and Lower Bound, which you haven’t finished yet.

P2MediumMental model~3 min speedrun

Longest Increasing Subsequence (Patience Sorting)

The problem

Longest Increasing Subsequence (LC 300)(opens leetcode.com)

You're given an integer array nums. Deleting any subset of its elements (possibly none) while keeping the rest in their original order produces a subsequence.

Find the length of the longest subsequence you can produce this way whose values keep strictly increasing from left to right.

Example 1
Input:nums = [10,9,2,5,3,7,101,18]
Output:4
The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

LIS

array ➔ tails array maintenance ➔ binary search replacement
Spot it when: You need the longest strictly increasing chain in a sequence, or pairs and envelopes that become one after sorting.
LIS
Python
1import bisect
2 
3def length_of_lis(nums: list[int]) -> int:
4 """Longest Increasing Subsequence via Patience Sorting.
5 Time: O(N log N) | Space: O(N)
6 """
7 # tails: sorted; tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far
8 tails: list[int] = []
9 
10 for x in nums:
11 # 1. Find Where x Fits:
12 # bisect_left finds the first tail >= x, the pile x can legally extend or replace.
13 idx = bisect.bisect_left(tails, x)
14 if idx == len(tails):
15 # 2. Start A Longer Subsequence:
16 # No tail is >= x, so x extends the longest subsequence found so far by one.
17 tails.append(x)
18 else:
19 # 3. Lower An Existing Tail:
20 # x is smaller than tails[idx], so it leaves more room for later values at this same length.
21 tails[idx] = x
22 
23 return len(tails)
Invariant: tails is sorted, and tails[k] is the smallest last value of any increasing subsequence of length k + 1 among the numbers seen so far.

Keep tails[k] as the smallest last value of any increasing subsequence of length k + 1, and for each x replace the first tail that is >= x (found with bisect_left), or append x when there is none. A smaller tail can only help, because it leaves more room for the values that come later, and replacing never breaks the order of tails, so len(tails) is always the longest length reached so far. The trap is reading tails as the answer: it has the right length but is usually not a real subsequence, so store each element's predecessor index when you must rebuild the sequence.

See it run

Longest Increasing Subsequence with tails, step by step

tails [] · len(tails) 0

tails [10] · len(tails) 1

tails [9] · len(tails) 1

tails [2] · len(tails) 1

tails [2, 5] · len(tails) 2

tails [2, 3] · len(tails) 2

tails [2, 3, 7] · len(tails) 3

tails [2, 3, 7, 101] · len(tails) 4

tails [2, 3, 7, 18] · len(tails) 4

tails [2, 3, 7, 18] · len(tails) 4 · answer 4

In the nums row each column is an index i. In the tails row each column is a position k in the list tails.

  • x the number being read
  • idx the tail that x replaces
  • idx (new) the new tail that x adds at the end
  • < x a tail that is smaller than x, so it stays unchanged
  • tail a tail that is counted in the final answer

Start: tails = [], an empty sorted list. No increasing subsequence exists yet.

x = 10: bisect_left gives idx = 0, which equals len(tails). So 10 is larger than every tail, and it is appended.

x = 9: bisect_left gives idx = 0, because tails[0] = 10 is the first tail that is at least 9. So write tails[0] = 9.

x = 2: bisect_left gives idx = 0, because tails[0] = 9 is the first tail that is at least 2. So write tails[0] = 2.

x = 5: bisect_left gives idx = 1, which equals len(tails). So 5 is larger than every tail, and it is appended.

x = 3: bisect_left gives idx = 1, because tails[1] = 5 is the first tail that is at least 3. So write tails[1] = 3.

x = 7: bisect_left gives idx = 2, which equals len(tails). So 7 is larger than every tail, and it is appended.

x = 101: bisect_left gives idx = 3, which equals len(tails). So 101 is larger than every tail, and it is appended.

x = 18: bisect_left gives idx = 3, because tails[3] = 101 is the first tail that is at least 18. So write tails[3] = 18.

Done: the function returns len(tails) = 4. The list tails is not necessarily one real subsequence.

nums
010
19
22
35
43
57
6101
718
tails
1 / 10
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Returning tails as the subsequence

    Mistake
    return tails
    Fix
    return len(tails)

    What happens: tails[k] is the smallest last value of any increasing subsequence of length k + 1. Its length is right. Its values can come from different subsequences, in the wrong order. To rebuild a real subsequence, store each element's predecessor index.

    Example: nums = [3, 4, 1]
    Mistake: returns [1, 4]Fix: returns 2
  2. 2

    Gotcha 2: Using bisect_right for a strictly increasing subsequence

    Mistake
    idx = bisect.bisect_right(tails, x)
    Fix
    idx = bisect.bisect_left(tails, x)

    What happens: bisect_left finds the first tail that is greater than or equal to x, so an equal value replaces it. bisect_right finds the first tail that is strictly greater than x. An equal value is then appended, so a run of equal values counts as increasing. Use bisect_right only when the problem allows equal neighbours.

    Example: nums = [2, 2, 2]
    Mistake: returns 3Fix: returns 1
  3. 3

    Gotcha 3: Sorting envelopes of equal width by ascending height

    Mistake
    envelopes.sort()
    Fix
    envelopes.sort(key=lambda e: (e[0], -e[1]))

    What happens: In Russian Doll Envelopes (LC 354), an envelope fits only when both its width and height are smaller. After sorting by width, the LIS runs on the heights. With equal widths in ascending height order, the LIS can nest one inside the other. Heights in descending order stop that.

    Example: Russian Doll Envelopes (LC 354): envelopes = [[1, 1], [1, 2]]
    Mistake: returns 2Fix: returns 1
Not this one if…
  • The chain must follow the order of a second sequence rather than rising values, as in Longest Common Subsequence (LC 1143): there is no sorted order to search in. See Two-Sequence DP

Deep Dive

From the slow table to tails

The first solution is a table. dp[i] is the length of the longest increasing subsequence that ends at index i. For each i, check every earlier j with nums[j] < nums[i] and take dp[j] + 1. This is correct, and it costs O(N^2) time. For N = 2500, there are 3,123,750 pairs.

The card keeps a different state. tails[k] is the smallest last value of any increasing subsequence of length k + 1. One array of that kind is enough, because only the smallest last value matters for each length.

Why is the smallest last value enough? Two subsequences of the same length are equal for the future, except for their last value. The one with the smaller last value accepts every later number that the other accepts, and possibly more. So the larger one can be forgotten.

Why tails stays sorted, and why the length is the answer

For each x, bisect_left returns the first index idx with tails[idx] >= x. Then tails[idx - 1] < x <= tails[idx]. Writing x into tails[idx] keeps the array sorted, because x is larger than its left neighbour and not larger than the old value.

A sorted array is what allows a binary search on the next number.

If no tail is >= x, then x is larger than every tail, so x extends the longest subsequence by one, and append is correct. Otherwise x lowers the tail for length idx + 1, which can only help later numbers.

Example: for nums = [10, 9, 2, 5, 3, 7, 101, 18], tails changes as [10], [9], [2], [2, 5], [2, 3], [2, 3, 7], [2, 3, 7, 101], [2, 3, 7, 18]. The final length is 4.

The length of tails only grows when x is larger than all tails. That happens exactly when a longer increasing subsequence now exists. So len(tails) is the longest length reached so far.

tails is not a subsequence

Each entry of tails is the end of some subsequence, but the entries can come from different ones. For nums = [3, 4, 1], the final tails is [1, 4]. The values 1 and 4 are in the wrong order in nums, because 1 comes after 4. The length 2 is correct, as [3, 4] is a real subsequence of that length.

To return a real subsequence, store the index of the number in each tail, and store for each index the tail to its left at the time it was placed. Then follow these links back from the last tail.

For nums = [10, 9, 2, 5, 3, 7, 101, 18], that method returns [2, 3, 7, 18].

The cost: N searches of size log N

Each of the N numbers does one bisect_left on an array of at most N entries, which takes O(log N) steps. The append or the replacement is O(1). So the time is O(N log N).

The space is O(N) for tails in the worst case, where the input is already increasing. Rebuilding the subsequence adds O(N) for the links.

Strict and non-strict order differ by one function. bisect_left gives a strictly increasing subsequence, so equal values replace each other. bisect_right gives a non-decreasing subsequence, so equal values are appended. For [2, 2, 2], the lengths are 1 and 3.

60-Second Pitch

"The simple solution stores, for each index, the longest increasing subsequence that ends there. It compares every pair, so it takes O(N^2) time. I can do better with one observation. For each length, only the smallest last value matters, because it accepts the most later numbers. So I keep tails, where tails[k] is the smallest last value of any increasing subsequence of length k + 1. This array is always sorted. For each number I use bisect_left to find the first tail that is greater than or equal to it. I replace that tail, or I append the number when none exists. The answer is the length of tails. That is N binary searches, so O(N log N) time and O(N) space. If you need the subsequence itself, I store a link for each index."

Common Questions

Why does the array tails stay sorted?

bisect_left returns the first index idx where tails[idx] >= x, so tails[idx - 1] < x. The new value fits between its two neighbours. When x is larger than all tails, it goes at the end. In both cases the order is kept, so the next binary search is valid.

What are the time and space complexity?

O(N log N) time, because each of the N numbers needs one binary search over at most N entries. The space is O(N) for tails. The simple table solution takes O(N^2) time and O(N) space.

How do you return the subsequence and not only its length?

Store the index of each tail value, and for each index store the index of the tail to its left at the moment it was placed. After the loop, start at the last tail and follow these links back, then reverse the result. The array tails alone is not enough, because its values can come from different subsequences.

How do you change the solution for a non-decreasing subsequence?

Replace bisect_left with bisect_right. Then an equal value is appended after the equal tails instead of replacing one. For [2, 2, 2] the result changes from 1 to 3.

How does Russian Doll Envelopes (LC 354) use this?

An envelope fits into another only when both width and height are smaller. Sort the envelopes by width ascending. For equal widths, sort by height descending, so two envelopes of the same width never form an increasing pair. Then the longest strictly increasing subsequence of the heights is the answer.

SWE Reasoning

Spot it

  • You must find the longest strictly increasing chain in a sequence, and the chain keeps the original order.
  • An O(N^2) table is too slow, because N can be too large for N^2 steps.
  • Pairs or boxes must be nested in both dimensions, as in Russian Doll Envelopes (LC 354). Sorting by one dimension turns the problem into an increasing subsequence on the other.
  • You need a length, not the number of such subsequences. For the count, as in Number of Longest Increasing Subsequence (LC 673), a plain table is used.
  • Among subsequences of the same length, the one with the smaller last value is always at least as good.

The invariant, step by step

  1. tails starts empty. The invariant holds, because no number has been seen.
  2. A number x arrives. bisect_left(tails, x) finds idx, the first tail that is >= x.
  3. If idx == len(tails), every tail is smaller than x. So x can follow the longest subsequence. The code appends x, and a new length now exists.
  4. Otherwise tails[idx] >= x. A subsequence of length idx + 1 can end at x, and x is not larger than the old tail. The code writes tails[idx] = x.
  5. In both cases tails is still sorted, because tails[idx - 1] < x <= tails[idx].
  6. After all numbers, tails[k] is the smallest last value for length k + 1, and len(tails) is the longest length. The code returns len(tails).

Traps

  • Return tails. It has the right length, but its values can come from different subsequences. For [3, 4, 1], it is [1, 4]. Return len(tails), or store links to rebuild a real subsequence.
  • Use bisect_right for a strict order. Equal values are then appended, and [2, 2, 2] gives 3 instead of 1.
  • Use bisect_left when equal values are allowed. The problem then wants a non-decreasing subsequence, and bisect_left returns too small a length.
  • Sort envelopes of equal width by ascending height. Two envelopes with the same width then look nestable. Sort by width ascending and by height descending.
  • Binary search on the table. The values dp[i] of the O(N^2) table are not sorted, so bisect on them gives wrong answers. Search tails, which is sorted.

Practice

Canonical LeetCode:Longest Increasing Subsequence (LC 300)Russian Doll Envelopes (LC 354)Maximum Length of Pair Chain (LC 646)Best Team With No Conflicts (LC 1626)Increasing Triplet Subsequence (LC 334)Longest Arithmetic Subsequence of Given Difference (LC 1218)
© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•