Skip to main content

17. Longest Increasing Subsequence

mediumAsked at Baidu

Find the length of the longest strictly increasing subsequence of an integer array.

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 order of the remaining ones.

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

Example 2

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

Approaches

1. DP O(n^2)

dp[i] = 1 + max(dp[j] for j<i where nums[j]<nums[i]); answer is max(dp).

Time
O(n^2)
Space
O(n)
const dp=Array(nums.length).fill(1);
for(let i=1;i<nums.length;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 + binary search

Maintain a tails[] array; for each x binary-search the first tail >= x and replace it. Final length of tails is the LIS length.

Time
O(n log n)
Space
O(n)
function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1; else hi = mid;
    }
    tails[lo] = x;
    if (lo === tails.length) tails.push(x);
  }
  return tails.length;
}

Tradeoff:

Baidu-specific tips

Baidu cares about the binary-search O(n log n) variant because the same trick powers their query-rewriting suffix-array compaction; bringing only the O(n^2) DP is a red flag.

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 Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →