Skip to main content

80. Longest Increasing Subsequence

mediumAsked at Snowflake

Find the length of the longest strictly increasing subsequence. Snowflake asks this to test the O(n log n) patience-sort trick — directly relevant to streaming statistics maintenance over ordered data.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-I screens.

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: The LIS is [2,3,7,101].

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. O(n^2) DP

dp[i] = length of LIS ending at i. dp[i] = 1 + max(dp[j] 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);
  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);
    }
  }
  return Math.max(...dp);
}

Tradeoff: Easy to state but n^2. Mention as the baseline.

2. Patience sort with binary search (optimal)

Maintain a 'tails' array where tails[k] = smallest possible tail of an LIS of length k+1. For each n, binary-search for the first tail >= n and replace it (or append if larger than all).

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;
    }
    if (lo === tails.length) tails.push(n);
    else tails[lo] = n;
  }
  return tails.length;
}

Tradeoff: n log n. tails[] is not the actual LIS, just the length-encoding artifact.

Snowflake-specific tips

Snowflake interviewers want the patience-sort version because it scales. Bonus signal: connect to streaming statistics maintenance — when running statistics like 'longest non-decreasing run' over a stream, the patience-sort idea (track minimal tails per length) generalizes.

Common mistakes

  • Confusing tails[] with the actual LIS — it's only the length encoding.
  • Using strict < vs <= incorrectly — strict for 'strictly increasing'.
  • Initial dp value 0 instead of 1 — every element is itself an LIS of length 1.

Follow-up questions

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

  • Reconstruct the actual LIS, not just length.
  • Russian Doll Envelopes (LC 354) — 2D LIS.
  • How does Snowflake compute streaming order statistics?

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 patience sort give the LIS length?

Each pile's top card is the smallest tail of an LIS of that pile's length. When a new card arrives, it replaces the smallest tail >= it. Final pile count = LIS length.

Why isn't tails[] the LIS?

Replacing entries breaks the original ordering. To reconstruct, you'd track predecessor pointers — adds complexity but doable in O(n log n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →