Skip to main content

84. Longest Increasing Subsequence

mediumAsked at Datadog

Find the length of the longest strictly increasing subsequence. Datadog asks this for the patience-sorting O(n log n) trick — same shape as their monotonic-history compression for time-series anomaly trend detection.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded on patience sort.
  • Blind (2025-10)— Recurring at Datadog.

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

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] = LIS ending at i. dp[i] = max(dp[j] + 1) for j < i where 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: O(n^2). Datadog accepts; they push for O(n log n) for senior roles.

2. Patience sort with binary search (optimal)

Maintain tails[]: tails[i] = smallest tail of any LIS of length i+1. For each num, binary-search and replace.

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). Datadog-canonical for senior roles. The tails array is NOT the LIS itself — it's a tracker that gives the right length.

Datadog-specific tips

Datadog grades on whether you can explain WHY tails[] gives the right length without being the actual LIS. The invariant: tails[i] = smallest possible tail of any LIS-of-length-i+1. Replacing keeps tails sorted; the length is what we return.

Common mistakes

  • Trying to reconstruct LIS from tails[] — that doesn't work; tails is a tracker, not the sequence.
  • Confusing strict vs non-strict — use < for strict, <= for non-strict.
  • Using lower_bound vs upper_bound incorrectly — strict LIS uses lower_bound.

Follow-up questions

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

  • LIS with path reconstruction — additional bookkeeping.
  • Russian Doll Envelopes (LC 354) — 2D LIS.
  • Datadog-style: monotonic-history compression for trend detection.

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 is tails monotonic?

By construction. tails[i] = smallest tail of any LIS-of-length-i+1. Bigger lengths require bigger tails.

Why doesn't tails contain the actual LIS?

Because we OVERWRITE earlier positions when a smaller tail is found. The actual LIS would require auxiliary back-pointers.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →