Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Longest Increasing Subsequence (LC 300)

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is derived by deleting zero or more elements without changing order.

Example 1:

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101] has length 4.

Example 2:

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

Constraints:

• 1 <= nums.length <= 2500 (for basic DP)
• Follow-up: nums.length up to 10^5 — requires O(n log n).

Difficulty: Medium

---

Pattern Recognition

• Input structure: 1D array.
• What are we optimizing? length of longest strictly increasing subsequence.
• Pattern:
  • O(n^2) — DP on prefixes: dp[i] = 1 + max(dp[j]) for j < i and nums[j] < nums[i].
  • O(n log n) — patience sorting: binary search insertion into a "tails" array.
• Why: DP captures optimal substructure naturally. Patience sorting exploits the fact that you only care about the smallest possible tail for each length, not the actual subsequence.

Google L4 expects both. The O(n log n) version is frequent because "binary search on answer" is a Google favorite.

---

Approach

O(n^2) — DP

dp[i] = length of LIS ending at index i. Answer = max(dp).

for i in 0..n-1:
    dp[i] = 1
    for j in 0..i-1:
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

Time: O(n^2). Space: O(n).

O(n log n) — Patience Sort / Binary Search

Key Insight: Maintain an array tails where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1. For each x in nums, binary-search the leftmost position in tails with value ≥ x and overwrite it (or append if x is larger than everything).

• If x is larger than all current tails, append → extends the LIS by 1.
• Otherwise, replace the first tail ≥ x with x → keeps the length the same but lowers the tail, giving future elements more room.
• Final LIS length is tails.length. Note: tails itself is not a valid subsequence — just a bookkeeping array.

tails = []
for x in nums:
    i = binarySearchLeft(tails, x)  // first index where tails[i] >= x
    if i == tails.length: tails.push(x)
    else: tails[i] = x
return tails.length

Time: O(n log n). Space: O(n).

For non-strict increase, use binarySearchRight (upper bound) instead.

---

Walkthrough

nums = [10, 9, 2, 5, 3, 7, 101, 18], tails method.

x	Binary search result	tails
10	append	[10]
9	replace index 0	[9]
2	replace index 0	[2]
5	append	[2, 5]
3	replace index 1 (first ≥ 3)	[2, 3]
7	append	[2, 3, 7]
101	append	[2, 3, 7, 101]
18	replace index 3	[2, 3, 7, 18]

Final tails.length = 4. (The true LIS is [2, 3, 7, 18] or [2, 3, 7, 101].)

---

Implementation

TypeScript

// O(n^2) DP
function lengthOfLIS_DP(nums: number[]): number {
    const n = nums.length;
    const dp: number[] = new Array(n).fill(1);
    let best = 1;
    for (let i = 1; i < n; 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;
}

// O(n log n) — patience sort
function lengthOfLIS(nums: number[]): number {
    const tails: number[] = [];
    for (const x of nums) {
        // Lower bound — first index with tails[i] >= x
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(x);
        else tails[lo] = x;
    }
    return tails.length;
}

C++

// O(n^2) DP
int lengthOfLIS_DP(vector<int>& nums) {
    int n = nums.size(), best = 1;
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    return best;
}

// O(n log n) — patience sort
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

Watch out:

1. tails is not the LIS. It is the minimum-tail table. To recover the actual LIS you need to store parent pointers during the sweep.
2. For non-strict increase, use upper_bound / right-binary-search instead of lower_bound — otherwise duplicates will not be counted.
3. Off-by-one in the lower-bound loop (using lo <= hi instead of lo < hi) gives wrong insertion indices.

---

Complexity Analysis

	Time	Space
DP	O(n^2)	O(n)
Patience Sort	O(n log n)	O(n)

Bottleneck: the DP is dominated by the pairwise scan. Patience sort replaces it with a binary search. Getting the actual subsequence (not just length) adds O(n) pointer bookkeeping without changing the asymptotics.

---

Edge Cases

1. Empty array — constraints say n ≥ 1; if you generalize, return 0.
2. All equal elements — strict LIS has length 1. The first element sets tails[0]; everything else replaces it in place.
3. Already increasing — every element appends; answer is n.
4. Already decreasing — every element overwrites tails[0]; answer is 1.
5. Negative numbers — no special handling needed; comparisons work.
6. Very large n — O(n^2) becomes dangerous at n ≥ 10^4. Use patience sort.

---

Related Problems

• LC 354 — Russian Doll Envelopes — Reduce to LIS after clever sort.
• LC 673 — Number of LIS — Count how many distinct LISs exist; needs an auxiliary count[i] array.
• LC 1671 — Minimum Removals to Make Mountain Array — LIS from both ends.
• LC 1964 — Longest Valid Obstacle Course at Each Position — Non-strict LIS; use upper_bound.

---

What Is Expected at Each Level

Junior: Solve with O(n^2) DP and explain the recurrence.

Mid-level: Implement the O(n log n) patience-sort version, correctly distinguish strict vs non-strict, handle the "tails is not the LIS" subtlety.

Senior (L4 target): Derive the patience-sort invariant ("smallest tail for each length"), explain why lower_bound vs upper_bound matters for strict vs non-strict, recover the actual subsequence with parent pointers if asked, and pivot smoothly to LC 354 or LC 673 variants — this is exactly the kind of DP → binary-search-on-answer pivot Google loves.