Skip to main content

83. Longest Increasing Subsequence

mediumAsked at Workday

Find the length of the longest strictly-increasing subsequence. Workday uses this for DP-vs-patience-sort decisions — same shape as finding the longest streak of strictly-rising compensation reviews.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 onsite.

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
  • Follow-up: Can you come up with an algorithm that runs in O(n log n) time complexity?

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

Approaches

1. DP O(n^2)

dp[i] = LIS ending at i. dp[i] = 1 + max(dp[j] for j < i and nums[j] < nums[i]).

Time
O(n^2)
Space
O(n)
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: Simple and correct. Fine for n=2500. Fails the follow-up.

2. Patience sort with binary search

Maintain tails[]: the smallest tail of an increasing subsequence of each length. For each num, binary-search-replace.

Time
O(n log n)
Space
O(n)
function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}

Tradeoff: O(n log n). tails is NOT the LIS itself — just the smallest possible tail at each length. Its length IS the LIS length.

Workday-specific tips

Workday wants the n log n version with binary search. Mention 'patience sort' by name and clarify: tails is not the LIS itself, just a witness for its length. State this caveat — interviewers love it.

Common mistakes

  • Confusing tails[] with the actual LIS — it's a witness, not the sequence.
  • Using strict < vs <= for the binary search — strict gives increasing, <= gives non-decreasing.
  • Stopping at the DP O(n^2) version when the follow-up explicitly asks for n log n.

Follow-up questions

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

  • Number of Longest Increasing Subsequences (LC 673).
  • Russian Doll Envelopes (LC 354) — 2D LIS.
  • Longest Common Subsequence — different problem.

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 isn't tails the actual LIS?

tails[i] is the smallest tail of any increasing subsequence of length i+1 SEEN SO FAR. The sequence in tails is not necessarily a subsequence of nums — but its length matches the LIS length.

How to reconstruct the actual LIS?

Track the predecessor index when you place each element. Walk back from the last replaced position. More code; ask if needed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →