56. Longest Increasing Subsequence

MediumArray Dynamic Programming Binary Search

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

A subsequence keeps the original order of the elements but may skip any of them. For example, [1,6,8] is a subsequence of [4,1,6,2,8], while [6,1] is not.

Example 1

Input: nums = [4,1,6,2,7,3,8]
Output: 4

Explanation: Both [4,6,7,8] and [1,2,3,8] have length 4, and nothing longer exists.

Example 2

Input: nums = [0,8,4,12,2,10,6,14,1,9]
Output: 4

Example 3

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

Explanation: Equal values do not count as increasing.

Constraints

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

Follow-up: Can you also reconstruct one longest subsequence, not just its length?

💡 Hint 1

An O(n²) DP works: len[i] = 1 + the largest len[j] with j < i and nums[j] < nums[i].

💡 Hint 2

For O(n log n), keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. This array is always sorted.

💡 Hint 3

For each number, binary-search the first tail that is >= it and overwrite it (or append if none). The final length of tails is the answer.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Maintain tails, where tails[k] is the smallest value that can end an increasing subsequence of length k + 1 seen so far. It is always sorted, so for each x binary-search the leftmost tail >= x. If there is none, x extends the longest subsequence (append). Otherwise replace that tail with x: same length, smaller ending, which only makes future extensions easier. Searching for >= x (not > x) keeps equal values from counting as increasing. The length of tails is the answer (the array itself is not necessarily a real subsequence).

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

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0;
    let 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;
}

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;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit