Skip to main content

12. Longest Increasing Subsequence

mediumAsked at JetBrains

Find the length of the longest strictly increasing subsequence — JetBrains uses this to test whether you reach for binary-search patience-sort over naive DP.

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

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. The subsequence elements need not be contiguous.

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] where j<i and nums[j]<nums[i]); answer is max(dp).

Time
O(n^2)
Space
O(n)
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 sort with binary search

Maintain a sorted tails array; for each n, binary-search the leftmost tail >= n and replace it. Tails length is the answer. JetBrains values this O(n log n) discipline.

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

Tradeoff:

JetBrains-specific tips

JetBrains expects you to reach for binary search even when O(n^2) DP passes — they grade for choosing the right algorithmic ceiling, mirroring their inspection-engine cost budgeting.

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

Practice these live with InterviewChamp.AI →