Skip to main content

21. Longest Increasing Subsequence

mediumAsked at Palantir

Given an integer array nums, return the length of the longest strictly increasing subsequence. Palantir asks this to see whether you know the O(n log n) patience-sort trick — they care because the same algorithm powers monotone trend extraction over a sorted-by-time partition in a Foundry transform.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE — wanted the O(n log n) version, not just DP.
  • Blind (2025-09)— Reported alongside a follow-up reconstructing the actual subsequence.

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence 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
  • Follow-up: O(n log n) time.

Examples

Example 1

Input
nums = [10,9,2,5,3,7,101,18]
Output
4

Explanation: LIS is [2,3,7,101] or [2,3,7,18].

Example 2

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

Example 3

Input
nums = [7,7,7,7,7,7,7]
Output
1

Approaches

1. DP O(n^2)

dp[i] = length of LIS ending at index i. For each i, look at all j < i; if nums[j] < nums[i], dp[i] = max(dp[i], dp[j]+1).

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: Straightforward but O(n^2) — Palantir will absolutely push for the n log n version.

2. Patience sort with binary search

Maintain tails[i] = smallest tail of an LIS of length i+1. For each num, binary-search the first tail >= num and replace it. Length of tails is the answer.

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 canonical Palantir answer. Tails isn't a valid LIS itself, but its LENGTH equals the LIS length. Be explicit about that invariant.

Palantir-specific tips

Palantir specifically tests for the O(n log n) version — getting only the O(n^2) DP is a junior signal here. State the invariant out loud before coding: tails[i] is the SMALLEST possible tail of any LIS of length i+1. Bonus signal: explain that you'd reconstruct the actual subsequence by tracking predecessor indices, but skip the implementation unless asked. Connect to Foundry: monotone-trend extraction over time-series partitions uses this exact shape.

Common mistakes

  • Using <= instead of < when replacing in tails — gives longest non-decreasing, not strictly increasing.
  • Claiming tails IS the LIS — it isn't. Only its length is correct. The actual LIS needs a predecessor array.
  • Using a linear scan instead of binary search — that's O(n^2) all over again.

Follow-up questions

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

  • Reconstruct the LIS itself — track predecessor indices.
  • Russian Doll Envelopes (LC 354) — sort by one dim, LIS on the other.
  • Longest Common Subsequence (LC 1143) — different DP, related framing.

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 the patience-sort trick give the right LENGTH?

Because each new element either extends the longest LIS by one (appended to tails) or improves a smaller-length LIS's tail (replaced via binary search). The length of tails never decreases and equals the LIS length.

Does this give the actual subsequence?

No — only the length. To reconstruct, store the parent index for each element and walk back from the last appended. That's an extra O(n) space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →