Skip to main content

78. Longest Increasing Subsequence

mediumAsked at Salesforce

Find the length of the longest strictly increasing subsequence. Salesforce uses this as the canonical DP-with-binary-search optimization.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses similar patterns for trend analysis in forecasting.
  • Blind (2025-10)— Tests both O(n^2) DP and O(n log n) patience sort.

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

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 and 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: Straightforward but slow. Acceptable for n <= 2500.

2. Patience sort (O(n log n))

Maintain `tails[i]` = smallest tail of any increasing subsequence of length i+1. For each x, replace the leftmost tail >= x via binary search (or append).

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) via binary search. tails isn't a real LIS but its length is correct. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses LIS for trend detection in forecast data. They grade on whether you can derive the O(n log n) patience sort (or recognize the pattern). Bonus signal: clarify that `tails` doesn't represent the actual LIS — its length is correct but the values may not be from any real subsequence.

Common mistakes

  • Using O(n^2) when O(n log n) is feasible — works for small inputs but Salesforce will push for the better algorithm.
  • Confusing 'tails' with the actual LIS — explain that tails[i] is the SMALLEST possible tail of any length-(i+1) increasing subseq.
  • Strict vs non-strict — this problem is strict; for non-strict, use upper_bound instead of lower_bound.

Follow-up questions

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

  • Russian Doll Envelopes (LC 354) — 2D LIS.
  • Longest Common Subsequence (LC 1143).
  • Reconstruct the actual LIS, not just its length.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Does tails represent the actual LIS?

No. tails[i] is the smallest possible TAIL of any increasing subseq of length i+1. The actual sequence requires extra bookkeeping (predecessor pointers).

Strict vs non-strict?

Strict: nums[j] < nums[i] (lower_bound). Non-strict: nums[j] <= nums[i] (upper_bound). Adjust the binary search accordingly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →