Longest Increasing Subsequence Medium 0 attempts
LeetCode ↗

Longest Increasing Subsequence

Medium Dynamic ProgrammingMemoization LeetCode

Given an integer array nums, find the length of its longest subsequence that is strictly increasing. Remember that a subsequence comes from deleting zero or more elements from the array while keeping the relative order of what's left untouched.

Input Format
Implement longestIncreasingSubsequence(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
nums = [0,1,0,3,2,3]
Output
4
Constraints
  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4
Test Cases (2)
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.

javascript
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