Solving the longest increasing subsequence with binary search

The longest increasing subsequence (LIS) problem appears in technical interviews, university algorithms courses, and competitive programming contests across Australia and beyond. The task is to find the longest sequence of numbers within an array such that each number is strictly greater than the previous one, while the chosen elements must remain in their original order. The wording is simple, yet the problem hides surprising depth and connects to ideas ranging from patience sorting games to database indexing structures.

A beginner typically solves it with a dynamic programming approach that runs in O(n²) time, which works fine for small arrays. The trouble begins when the input grows to hundreds of thousands of items, the kind of scale routinely processed by analytics teams at companies like REA Group in Melbourne or Atlassian in Sydney. For those situations, an O(n log n) algorithm using binary search is the standard answer, and it fits comfortably in under twenty lines of code once the underlying trick is understood.

Australian software engineers encounter this pattern frequently, whether preparing for graduate interviews in Sydney's financial district, contributing to open-source visualisation libraries in Brisbane, or competing in ICPC-style contests run by UNSW and the University of Melbourne. Mastering the binary search variant is less about memorising code and more about grasping a reusable technique that reappears in problems involving envelopes, Russian dolls, and stock trading.

This article walks through the intuition, the recurrence, the data structure behind the optimisation, and a worked example. It touches on common pitfalls that catch even experienced developers, the kinds of bugs that show up in code reviews at places like Canva and Seek. By the end, the algorithm should feel less like a clever trick and more like a natural extension of how a human would approach it intuitively.

What the longest increasing subsequence really means

Given [10, 22, 9, 33, 21, 50, 41, 60], the goal is to pick a subsequence — not necessarily contiguous — whose values are strictly increasing and whose length is maximal. For this example, the answer is six, achieved by 10, 22, 33, 50, 60 or 10, 22, 33, 41, 60, among others. The "increasing" requirement applies to the values, not the indices, but the indices must remain in ascending order.

The problem has practical uses in bioinformatics pipelines, stock analysis tools, and even text-diff utilities powering version control systems. Recognising them turns the algorithm into a general-purpose thinking tool rather than an abstract puzzle.

To make the definition concrete, imagine the array as a row of beach flags along Sydney's Bondi to Bronte coastal walk. The goal is to take a photo that captures the maximum number of flags while preserving their left-to-right order, but the photo can only include flags taller than the previous one in the shot. The longest such photo corresponds to the LIS length, and once that intuition lands, the binary search approach becomes much easier to absorb.

A side-by-side look at common strategies

Before diving into code, it helps to compare the approaches that solve the same problem. The table below summarises four of the most widely taught methods along with their trade-offs.

Method	Time complexity	Space complexity	Best for
Naive dynamic programming	O(n²)	O(n)	Small inputs and teaching purposes
Binary search with a tails array	O(n log n)	O(n)	Most practical cases, interview default
Segment tree with coordinate compression	O(n log n)	O(n)	Variants requiring fast value queries
Fenwick tree after sorting by index	O(n log n)	O(n)	3D-LIS and patience sorting problems

The naive approach is easiest to write but breaks down quickly. The binary search method strikes an excellent balance between performance and simplicity, which is why it dominates interview preparation material on data structures and competitive programming archives worldwide.

The naive dynamic programming approach

The classic dynamic programming solution defines dp[i] as the length of the longest increasing subsequence ending at position i. The recurrence is dp[i] = 1 + max(dp[j]) for all j < i where arr[j] < arr[i], falling back to 1 if no such j exists. The final answer is the maximum value across the dp array.

Pseudocode looks like this:

for i from 0 to n - 1:
    dp[i] = 1
    for j from 0 to i - 1:
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], 1 + dp[j])
return max(dp)

For an array of length n, this nested loop performs roughly n²/2 comparisons. With one thousand elements, that is half a million operations, still acceptable. With one hundred thousand elements, the count balloons to five billion, well past what is reasonable in real-time systems powering live auction feeds or trading dashboards used by ANZ and CBA. That is the wall that motivates the binary search optimisation.

The patience sorting intuition

The clever insight behind the O(n log n) method comes from a card game called Patience, also known as Solitaire. When laying cards onto stacks according to a specific rule, the minimum number of stacks required equals the length of the longest increasing subsequence of the card values in the order they were dealt.

In the algorithm, each element of the input array is placed onto a "pile" using binary search. Maintain a list of piles where the top card of each pile is in strictly increasing order. For each new number, find the leftmost pile whose top card is greater than or equal to the new number and replace that top card. If no such pile exists, start a new pile to the right.

The number of piles at the end is exactly the LIS length. Each pile represents the tail of an increasing subsequence of some length, and the binary search keeps piles as shallow as possible. The metaphor is often how the algorithm is taught in algorithms courses at Australian universities, particularly those covering amortised analysis.

Core idea behind the binary search method

Reframing the patience-sorting process, the typical implementation maintains a tails array. For each element x, perform a binary search on tails to find the leftmost position where tails[pos] >= x, then set tails[pos] = x. The length of tails at the end equals the LIS length. The contents of tails are not the actual subsequence; they are simply the smallest possible tail values for subsequences of each length.

This works because keeping tail values small maximises future options. If tails says there exists an increasing subsequence of length k ending in value v, then any later element larger than v can extend that subsequence to length k + 1. The binary search step maintains this invariant efficiently, reducing the inner work from linear to logarithmic.

The same trade-off, swapping linear scans for logarithmic ones, is at the heart of search tree optimisations. A clear write-up of one such structure lives in this B-tree indexing review, which walks through similar reasoning in a different context. Recognising the shared pattern turns a one-off algorithm into a transferable skill.

A worked example step by step

Trace through [0, 1, 0, 3, 2, 3] to see the algorithm in action. Initialise tails as an empty array, then process each element using a lower-bound binary search.

Process 0: no position satisfies tails[pos] >= 0, so append. tails is [0]. Process 1: no position satisfies tails[pos] >= 1, so append. tails is [0, 1]. Process 0: the leftmost position with tails[pos] >= 0 is pos = 0, so replace tails[0] with 0. tails stays [0, 1].

Process 3: no position satisfies tails[pos] >= 3, so append. tails becomes [0, 1, 3]. Process 2: the leftmost position with tails[pos] >= 2 is pos = 2, so replace tails[2] with 2. tails becomes [0, 1, 2]. Process 3: no position satisfies tails[pos] >= 3, so append. tails becomes [0, 1, 2, 3].

The final length is 4, matching the actual longest increasing subsequence 0, 1, 2, 3. Note how tails is not the actual subsequence but rather the smallest possible tail values. The binary search does the heavy lifting; everything else is bookkeeping.

Implementation tips and common pitfalls

Translating the algorithm into Python using the bisect module is straightforward, but a few subtle points trip up many developers. The following list highlights the most common issues worth watching for during code review:

• Confusing bisect_left with bisect_right when handling duplicates
• Forgetting that the returned length is the LIS, not the subsequence itself
• Returning tails as the answer rather than its length
• Modifying tails during a debug print and missing the updates
• Off-by-one errors when porting the code to zero-indexed languages like C

For variations, the binary search template adapts naturally to several related problems. The following examples are commonly seen in Australian interview loops and competitive programming rounds:

• Russian Doll Envelopes, where envelopes must be nested by both width and height
• Maximum Sum Increasing Subsequence, where each picked element adds to a running total
• Longest Bitonic Subsequence, which combines an increasing and a decreasing run
• Longest Chain of Pairs, where pairs are sorted and chained by their second element
• Box Stacking, a three-dimensional variant used in logistics planning

With these variations in mind, the binary search method stops feeling like a one-off trick and starts to look like a versatile template. Once the tails array and the lower-bound search are internalised, the same template can be applied almost anywhere a problem asks for the longest strictly increasing subsequence under a mild ordering constraint. That is the real payoff: a way of thinking about sequences that travels well across the rest of computer science.