Longest Increasing Subsequence Medium 0 attempts
LeetCode ↗

Longest Increasing Subsequence

Medium Dynamic ProgrammingMemoization LeetCode

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

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

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4
Test Cases
Case 1
Args: [[10,9,2,5,3,7,101,18]] Expected: 4
Case 2
Args: [[0,1,0,3,2,3]] Expected: 4
Topics
Dynamic ProgrammingMemoization

Approach: Binary Search (Patience Sort)

Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number, use binary search to find its position in tails. This gives O(n log n) time.

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

Time Complexity: O(n log n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript