Skip to main content

19. Longest Increasing Subsequence

mediumAsked at Brex

Find the length of the longest strictly increasing subsequence — a DP / patience-sort problem that Brex interviewers use to test algorithmic depth and optimization awareness.

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

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence (elements do not need 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)

For each index i, check all j < i where nums[j] < nums[i] and extend that subsequence.

Time
O(n^2)
Space
O(n)
const dp = new 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 sort (binary search) O(n log n)

Maintain a tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. Binary search to find the correct position for each number and replace.

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

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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

Practice these live with InterviewChamp.AI →