Skip to main content

300. Longest Increasing Subsequence

mediumAsked at Google

Return the length of the longest strictly increasing subsequence. Google asks this to test whether you reach for O(n log n) via patience sorting / binary search rather than stopping at the textbook O(n^2) DP.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the DP-optimization round.
  • Blind (2025-10)— Recurring Google interview problem.

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 longest increasing subsequence 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] = max(dp[j] + 1) for all j < i with nums[j] < nums[i].

Time
O(n^2)
Space
O(n)
function lengthOfLISDP(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: Standard DP — works but at n = 2500 the O(n log n) version is ~50x faster. Mention this as the natural first solution, then optimize.

2. Patience sorting / binary search (optimal)

Maintain a 'tails' array where tails[i] is the smallest possible tail of any increasing subsequence of length i+1. Binary-search to update.

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: The 'tails' array is sorted (by construction), so we can binary-search for the insertion point. The array's LENGTH is the LIS length — the contents are not the LIS itself.

Google-specific tips

Google interviewers want the O(n log n) version. State out loud: 'I'm maintaining tails[k] = smallest possible tail of any increasing subsequence of length k+1. Smaller tails leave more room to extend, so this is a greedy invariant.' If you stop at O(n^2), the interviewer will explicitly ask 'can you do better?' and now you're under time pressure.

Common mistakes

  • Confusing the 'tails' array with the actual LIS — the array's CONTENTS are not the LIS, only its length is correct.
  • Using <= instead of < in the binary search — that gives longest non-decreasing, not strictly increasing.
  • Stopping at the O(n^2) DP and not optimizing.

Follow-up questions

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

  • Return the actual LIS, not just its length (requires parent pointers; can't be done with the tails trick alone).
  • Russian Doll Envelopes (LC 354): 2D LIS, sort then 1D LIS on heights.
  • Number of Longest Increasing Subsequences (LC 673).

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 the tails array always sorted?

We maintain the invariant via binary search: each insertion either appends (when n exceeds all tails) or replaces the first tail >= n. Both operations preserve sortedness.

Why does smaller tails = better?

Because tail[i] is the smallest end of a length-(i+1) subsequence, it leaves the most room for future numbers to extend the subsequence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →