Skip to main content

25. Longest Increasing Subsequence

mediumAsked at SoFi

Find the length of the longest strictly increasing subsequence in an integer array — a classic DP problem SoFi applies to modeling loan amortization schedules and sequential credit score trends.

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

Explanation: The LIS is [2,3,7,101] with length 4.

Example 2

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

Approaches

1. Brute force

Recursively enumerate all subsequences and track the longest increasing one.

Time
O(2^n)
Space
O(n)
function lis(nums, i, prev) {
  if (i === nums.length) return 0;
  let skip = lis(nums, i + 1, prev);
  let take = 0;
  if (nums[i] > prev) take = 1 + lis(nums, i + 1, nums[i]);
  return Math.max(skip, take);
}

Tradeoff:

2. Dynamic programming with patience sort (binary search)

Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. Binary search to find the insertion point for each element, giving O(n log n) time. This mirrors how you'd efficiently find the longest run of increasing loan payments or credit-score improvements in a time series.

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

Tradeoff:

SoFi-specific tips

SoFi asks about personal finance algorithms and sequential data processing, so frame your solution around real-world analogies like tracking an improving credit score series or an ascending loan payment schedule, and be ready to extend to returning the actual subsequence.

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

Practice these live with InterviewChamp.AI →