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

Example 1:

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

Constraints:

• 1 <= nums.length <= 2500

Patience sorting / binary search build tails array in O(n log n) time.

Binary Search Patience Sorting / DP

graph TD
    Problem["Problem of Size N"] --> Sub["Break into Subproblems DP[i]"]
    Sub --> Base["Base Cases: DP[0], DP[1]"]
    Base --> Trans["State Transition: DP[i] = f(DP[i-1], DP[i-2], ...)"]
    Trans --> Table["Fill DP Table / Variables"]
    Table --> Result["Return DP[N]"]

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

• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Explanation: Patience sorting.

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

• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Explanation: Binary search tails array.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Build tails array of smallest tail of all increasing subsequences of length i.

1. dp[i] is length of LIS ending at index i.
2. O(n log n) with patience sorting.

👉 Solve this problem interactively in the DSA Lab