Skip to main content

15. Longest Increasing Subsequence

mediumAsked at Confluent

Return the length of the longest strictly increasing subsequence — Confluent uses it to probe DP/binary-search hybrid thinking, which connects to ordered-offset analysis over a Kafka log.

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 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]) for j < i with 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=0;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 binary search

Maintain piles whose tops form an increasing array. For each number, binary-search for the leftmost top >= x and replace; the array length 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 m = (lo + hi) >> 1;
      if (tails[m] < x) lo = m + 1; else hi = m;
    }
    tails[lo] = x;
    if (lo === tails.length) tails.push(x);
  }
  return tails.length;
}

Tradeoff:

Confluent-specific tips

Confluent will pivot to streaming — explain how each partition can maintain its own LIS array and emit it on rebalance so the downstream merger can recompute the global LIS without re-reading from the log.

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

Practice these live with InterviewChamp.AI →