Skip to main content

19. Longest Increasing Subsequence

mediumAsked at Nubank

Find the length of the longest strictly increasing subsequence in an array; Nubank uses LIS to test DP fluency, often framed as longest rising balance trend in a checking account.

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 picks elements in order without requiring them to 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] = max(dp[j]) + 1 for all j<i where nums[j] < nums[i].

Time
O(n^2)
Space
O(n)
function lengthOfLIS(nums){ const dp=Array(nums.length).fill(1); let m=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); m=Math.max(m,dp[i]); } return m; }

Tradeoff:

2. Patience sort / binary search

Maintain tails[] where tails[k] = smallest tail of any LIS of length k+1; binary-search the insertion point for each new number. Final length is tails.length.

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 mid = (lo + hi) >> 1;
      if (tails[mid] < n) lo = mid + 1; else hi = mid;
    }
    tails[lo] = n;
  }
  return tails.length;
}

Tradeoff:

Nubank-specific tips

At Nubank you score bonus points by saying you'd use n log n in a streaming setting where new balance snapshots arrive — they care about scaling intuition.

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

Practice these live with InterviewChamp.AI →