Skip to main content

85. Longest Increasing Subsequence

mediumAsked at Reddit

Find the length of the longest strictly increasing subsequence. Reddit uses this to test DP + binary search — relevant when finding the longest monotonically increasing run in a vote stream (a bot-detection signal).

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit data-platform DP question.

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. Follow up: Can you come up with an algorithm that runs in O(n log n) time complexity?

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: [2,3,7,101]

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 j < i with nums[j] < nums[i].

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

Tradeoff: Quadratic but clear.

2. Patience sorting / binary-search (optimal)

Maintain tails[]: tails[k] = smallest tail of any LIS of length k+1. Binary-search insert each value.

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: O(n log n). The 'tails' array isn't the actual LIS — only its length matches.

Reddit-specific tips

Reddit interviewers expect the patience sort optimization. Bonus signal: clarify that tails[] does NOT contain the actual LIS — it's a 'canonical form' that just preserves the length.

Common mistakes

  • Believing tails[] is the LIS (it's only correct in length).
  • Using <= where strict < is needed.
  • Initializing dp to 0 instead of 1 (length-1 subsequence is always a candidate).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Number of LIS (LC 673).
  • Russian doll envelopes (LC 354) — 2D LIS.
  • Longest chain of pairs (LC 646).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does tails work?

tails[k] tracks the smallest tail among length-(k+1) subsequences. Smaller tails are weakly better because they leave room for more extensions.

How to recover the actual LIS?

Track predecessors in the DP version, or do reconstruction with a parent array in the binary-search version (more involved).

Practice these live with InterviewChamp.AI

Drill Longest Increasing Subsequence and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →