Skip to main content

21. Longest Increasing Subsequence

mediumAsked at Asana

Find the length of the longest strictly increasing subsequence — Asana uses this DP pattern when computing the critical path of sequentially dependent milestones in a project's dependency chain.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

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

Explanation: LIS is [2,3,7,101] — length 4.

Example 2

Input
nums = [0,1,0,3,2,3]
Output
4

Explanation: [0,1,2,3] or [0,1,3,3] — length 4 (strictly increasing, so the latter is invalid; answer 4 from [0,1,2,3]).

Approaches

1. DP — O(n^2)

dp[i] = length of LIS ending at index i. For each i, check all j < i where nums[j] < nums[i] and take the max dp[j] + 1.

Time
O(n^2)
Space
O(n)
function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

Tradeoff:

2. Patience sorting with binary search — O(n log n)

Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. Binary-search each new element into tails.

Time
O(n log n)
Space
O(n)
function lengthOfLIS(nums) {
  const tails = [];

  for (const num of nums) {
    let lo = 0;
    let 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;
}

Tradeoff:

Asana-specific tips

Asana values knowing both variants. Start with the O(n^2) DP — it's clean and directly expresses the subproblem definition. Then introduce patience sorting as the O(n log n) upgrade. The key insight to articulate: tails doesn't store the actual LIS, it stores the most favorable ending values for subsequences of each length. Interviewers who know algorithm theory will probe this distinction.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Increasing Subsequence and other Asana interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →