Coding problem · Medium · Dynamic Programming

Longest Increasing Subsequence

Medium Algorithms & data structures Seen at Google, Microsoft, Amazon

Given an integer array nums, return the length of the longest strictly increasing subsequence (elements in order, not necessarily contiguous).

Example 1

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

Example 2

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

Hints

Hint 1

O(n²) DP: lis[i] = 1 + max(lis[j]) for j < i with nums[j] < nums[i].

Hint 2

O(n log n): keep tails[k] = the smallest possible tail of an increasing subsequence of length k+1; binary-search where each number goes.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n log n) · Space O(n)

Patience sorting: scan numbers and maintain tails, where tails[k] is the smallest tail of any increasing subsequence of length k + 1. For each x, find (binary search) the first tail >= x and replace it — or append if x is larger than all tails. The length of tails is the answer. (tails itself is not necessarily a valid subsequence.)

Reference solution

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1; else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}

function lengthOfLIS(nums: number[]): number {
  // O(n²) DP version for comparison with the binary-search approach.
  const lis = new Array<number>(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++)
    for (let j = 0; j < i; j++) if (nums[j] < nums[i]) lis[i] = Math.max(lis[i], lis[j] + 1);
  return Math.max(...lis);
}

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

<?php

function lengthOfLIS(array $nums): int
{
    $tails = [];
    foreach ($nums as $x) {
        [$lo, $hi] = [0, count($tails)];
        while ($lo < $hi) {
            $mid = intdiv($lo + $hi, 2);
            if ($tails[$mid] < $x) {
                $lo = $mid + 1;
            } else {
                $hi = $mid;
            }
        }
        $tails[$lo] = $x;
    }
    return count($tails);
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }
}

Climbing Stairs · Easy
House Robber · Medium
Coin Change · Medium