Longest Increasing Subsequence — Patience Sorting with Binary Search [LC 300, Google, Amazon]

Problem Statement#

LeetCode 300 — Longest Increasing Subsequence · Difficulty: Medium

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived by deleting some or no elements without changing the relative order of the remaining elements.

Constraints:

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

Example 1:

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 5, 7, 101] or [2, 3, 7, 101] — length 4.

Example 2:

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0, 1, 2, 3] — length 4.

Example 3:

Input:  nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: All equal, no strictly increasing subsequence of length 2.

Why This Problem Matters#

LC 300 is one of the most famous algorithm problems in existence and has been asked at Google, Amazon, Microsoft, and Apple for decades. It sits at the intersection of two canonical techniques: dynamic programming and binary search. Most candidates know the O(n²) DP solution. The O(n log n) binary search variant — patience sorting — is what distinguishes candidates who truly understand algorithmic optimisation.

Patience sorting is not just a clever trick for this problem. It is a fundamental algorithm used in:

• Merge sort analysis — the number of piles in patience sorting equals the length of the LIS, and the number of piles directly corresponds to the minimum number of merge passes.
• Optimal scheduling — minimising the number of "stacks" in card-game patience is mathematically equivalent to minimising job chains.
• Version control — diffing algorithms use LIS to find the longest common subsequence (LCS), which reduces to LIS after appropriate transformation.

In interviews, being able to derive the O(n log n) solution and explain the tails invariant earns significantly more points than presenting the O(n²) DP. The binary search variant is expected at senior and staff engineer levels.

The Core Insight#

Maintain an array tails where tails[i] stores the smallest possible tail element of any increasing subsequence of length i + 1 seen so far.

The invariant: tails is always strictly increasing.

Why? If tails[i] is the smallest tail for length i+1, and we found a subsequence of length i+2, its tail must be strictly greater than tails[i]. So tails[i] < tails[i+1] always.

For each new number x:

1. Binary search tails for the leftmost position where tails[pos] >= x (i.e., bisect_left).
2. If pos == len(tails): x extends the longest subsequence found so far. Append x.
3. Otherwise: x can replace tails[pos] with a smaller tail, potentially enabling longer subsequences later. Replace tails[pos] = x.

The final answer is len(tails).

Key clarification: tails does NOT store the actual LIS. It stores the optimal tail values for subsequences of each length. After processing all elements, len(tails) is the LIS length, but the elements of tails may not form an actual valid subsequence of nums.

Visual Dry Run#

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

Final tails = [2, 3, 7, 18], length = 4. Correct.

Note: tails = [2, 3, 7, 18] is NOT the LIS itself (the actual LIS is [2, 3, 7, 101] or [2, 5, 7, 101]), but its length is correct.

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

Final length = 1. Correct — no strictly increasing pair.

Common Mistakes#

1. Using bisect_right instead of bisect_left. bisect_left finds the leftmost position where x can be inserted to keep tails sorted, i.e., the first tails[pos] >= x. bisect_right finds the first position where tails[pos] > x, which would allow duplicates into the subsequence and compute LIS for non-strictly increasing sequences. Since this problem requires strictly increasing, always use bisect_left.

2. Thinking tails IS the LIS. This is perhaps the most common misconception. tails stores optimal tail values — the actual LIS may differ. If you need to reconstruct the LIS itself (not just its length), you need an additional parent-pointer or patience-deck tracking structure. The length alone is len(tails).

3. Forgetting that the O(n²) DP is acceptable for n up to 2500. The constraints (n <= 2500) allow O(n²). In an interview, start with the O(n²) DP for clarity, then optimise to O(n log n). Jumping straight to patience sorting without explaining the simpler DP can confuse interviewers who then doubt you understand the problem.

4. Implementing bisect_left manually with the wrong boundary. A common error is using while lo <= hi for the inner binary search. Use while lo < hi and return lo — the left boundary template finds the first position where the condition holds.

5. Initialising tails with sentinel values. Some implementations pre-fill tails with -inf or inf. This is unnecessary and adds complexity. Start with an empty tails and use pos == len(tails) to detect the "append" case.

6. Applying this algorithm to non-strictly increasing problems without changing bisect_left to bisect_right. For the "longest non-decreasing subsequence" variant, you need bisect_right (allow equal tails). Mixing the two is a silent bug.

Solutions#

Python#

import bisect
 
def lengthOfLIS(nums: list[int]) -> int:
    # tails[i] = smallest tail of any increasing subsequence of length i+1
    # Invariant: tails is always strictly increasing
    tails = []
 
    for x in nums:
        # Find the leftmost index in tails where tails[pos] >= x.
        # bisect_left gives the position to maintain strict increase.
        pos = bisect.bisect_left(tails, x)
 
        if pos == len(tails):
            # x is larger than all current tails:
            # it extends the longest subsequence found so far
            tails.append(x)
        else:
            # Replace the existing tail with x (a smaller or equal tail).
            # This does NOT change the length of tails, but improves
            # future chances: a smaller tail allows more elements to extend it.
            tails[pos] = x
 
    # The length of tails equals the length of the longest increasing subsequence
    return len(tails)

JavaScript#

function lengthOfLIS(nums) {
    // tails[i] = smallest tail element for any increasing subsequence of length i+1
    // tails is always strictly increasing (maintained by bisect_left logic below)
    const tails = [];
 
    for (const x of nums) {
        // Binary search: find the leftmost position where tails[pos] >= x
        // This is equivalent to Python's bisect.bisect_left
        let lo = 0;
        let hi = tails.length;
 
        while (lo < hi) {                        // left-boundary binary search
            const mid = lo + Math.floor((hi - lo) / 2);
            if (tails[mid] < x) {
                lo = mid + 1;                    // x must go to the right of mid
            } else {
                hi = mid;                        // tails[mid] >= x; candidate pos is mid or left
            }
        }
        // lo is now the leftmost position where tails[lo] >= x
 
        if (lo === tails.length) {
            // x is greater than all current tails: extend the longest subsequence
            tails.push(x);
        } else {
            // Replace tails[lo] with x: x is smaller (or equal), which is better
            // for allowing future elements to extend this length subsequence
            tails[lo] = x;
        }
    }
 
    // Length of tails = length of the longest strictly increasing subsequence
    return tails.length;
}

Complexity Analysis#

For n = 2500: O(n²) = 6.25M operations (fast). For n = 100,000 (if constraints change): O(n²) = 10B operations (too slow), while O(n log n) = 1.7M.

The binary search inside the loop makes each of the n element insertions O(log n), giving total O(n log n).

Follow-up Questions#

Q: How do you reconstruct the actual LIS, not just its length? Track a parent array where parent[i] is the index of the element before nums[i] in the optimal subsequence. Alternatively, track the patience-sorting "piles" and follow the chain backward. This reconstruction is O(n log n) time and O(n) space.

Q: What about the longest non-decreasing subsequence (allowing equals)? Change bisect_left to bisect_right. This allows equal elements to be part of the subsequence. The rest of the algorithm is identical.

Q: What is the connection to patience sorting? In the card game Patience (Solitaire), you deal cards into piles following a rule: place each card on the leftmost pile whose top card is not smaller. The number of piles equals the LIS length — this is the Dilworth theorem. The tails array stores the top card of each pile.

Q: What is the connection to LCS? The Longest Common Subsequence of two sequences A and B can be reduced to LIS: for each element in A, find its positions in B, then find the LIS of those position sequences. This O(n log n) reduction underpins many diff algorithms.

Q: Can you solve LIS in O(n) time? No. There is an information-theoretic lower bound of Omega(n log n) for comparison-based LIS computation (proved via reduction to sorting). O(n log n) is optimal.

This Pattern Solves#

• LC 300 — Longest Increasing Subsequence (this problem)
• LC 354 — Russian Doll Envelopes (2D LIS using sort + patience sort)
• LC 1964 — Find the Longest Valid Obstacle Course at Each Position (LIS with reconstruction)
• LC 673 — Number of Longest Increasing Subsequences (count LIS; needs augmented DP)
• LC 1671 — Minimum Number of Removals to Make Mountain Array (LIS from both ends)
• Any problem requiring optimal subsequence length under a monotonicity constraint

Key Takeaway#

The patience sorting approach to LIS maintains a tails array where tails[i] is the smallest possible tail of any increasing subsequence of length i + 1. The array is always strictly increasing, enabling binary search (bisect_left) to find the right position in O(log n) per element. When a new element is larger than all tails, append it (new longest subsequence found). Otherwise, replace the first tail that is >= x with x (optimise future extensions). The result is len(tails) in O(n log n) — a factor of n / log n faster than the classic DP, and the expected solution at senior-level FAANG interviews.

Key Takeaways#

• LC 300 (LIS) is asked by Google, Amazon, and Microsoft; the O(n log n) patience sorting solution is expected at senior levels and distinguishes strong candidates.
• Maintain a tails array where tails[i] is the smallest tail value of any increasing subsequence of length i + 1.
• The tails array is always strictly increasing, which is the invariant that makes binary search (bisect_left) applicable inside the loop.
• For each element x: if x is larger than all tails, append it (extend the longest subsequence); otherwise replace the first tail >= x with x (optimise future extensions).
• The final LIS length is len(tails) — the tails array itself does NOT represent a valid LIS, only its length is meaningful.
• For non-decreasing subsequences (allowing equals), switch from bisect_left to bisect_right — the only change needed.
• The connection to patience sorting (card game) and Dilworth's theorem gives this algorithm deep combinatorial roots that interviewers love to discuss.