#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/lis-binary-search-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/lis-binary-search-implementation

Repovive

LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation - Longest Increasing Subsequence | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation

O(n log n) code

Here's the faster solution:

function lengthOfLIS(nums)
    tails := empty array
    for each num in nums
        // Binary search for leftmost position >= num
        pos := binarySearch(tails, num)
        if pos = length of tails then
            tails.append(num)
        else
            tails[pos] := num
    return length of tails

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

tails[i] stores the smallest ending element of any increasing subsequence of length i+1. For each new number, you either extend the longest subsequence or replace an element to keep tails as small as possible.

The array tails is always sorted, enabling binary search. This greedy approach works because smaller endings give more room for future elements.