Skip to main content

24. Longest Increasing Subsequence

mediumAsked at Dropbox

Find the length of the longest strictly increasing subsequence — Dropbox uses a variant of this algorithm when identifying the longest sequence of non-conflicting file versions to establish a clean merge baseline.

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 from the array by deleting some or no elements without changing the order of the remaining elements.

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] or [2,5,7,101], both of length 4.

Example 2

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

Approaches

1. DP — O(n^2)

dp[i] = length of LIS ending at index i. For each i, check all j < i where nums[j] < nums[i] and take the max dp[j] + 1.

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

Tradeoff:

2. Patience sorting — O(n log n)

Maintain a 'tails' array where tails[k] is the smallest tail value of all increasing subsequences of length k+1. Binary search to find where each element fits; replacing rather than appending keeps the array monotone.

Time
O(n log n)
Space
O(n)
function lengthOfLIS(nums) {
  const tails = [];
  for (const num of nums) {
    let lo = 0;
    let 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:

Dropbox-specific tips

Dropbox interviewers expect you to reach O(n log n) unprompted — the quadratic solution is usually sufficient for correctness credit but won't close an offer. Practice explaining patience sorting intuitively: each pile in the card game corresponds to a subsequence, and you always play a card onto the leftmost pile it fits.

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

Practice these live with InterviewChamp.AI →