LeetCode · #300

Longest Increasing Subsequence Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #300

🏗️

Pattern

DP — 1D subsequence / patience sort

Given array nums, return the length of the longest strictly increasing subsequence. A subsequence can skip elements but must maintain relative order.

Example

 Input: nums = [10,9,2,5,3,7,101,18]
Output: 4 // LIS is [2, 3, 7, 101] or [2, 5, 7, 101]. 

Constraints

• 1 ≤ nums.length ≤ 2500 • -10⁴ ≤ nums[i] ≤ 10⁴

Section Two · Approach 1

DP — O(n²)

dp[i] = length of LIS ending at index i. For each i, look at all j < i: if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1). Return max of all dp values.

Why it works

Every increasing subsequence ending at i must be formed by extending some subsequence ending at an earlier j where nums[j] < nums[i]. Trying all such j and taking the max covers all possibilities.

Why we can do better

Problem: O(n²) with n=2500 gives ~6 million operations — acceptable but can be improved. The patience sorting approach maintains a "tails" array where tails[k] = smallest tail element of any increasing subsequence of length k+1. Binary search on this array gives O(n log n).

Java — O(n²) DP

 import java.util.Arrays;
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
        Arrays.fill(dp, 1); // every element is LIS of 1 int max = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            max = Math.max(max, dp[i]);
        }
return max;
    }
}

Python — O(n²) DP

 class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

Metric	Value
Time	O(n²)
Space	O(n)

Section Three · Approach 2

Patience Sort — O(n log n)

Maintain a tails array. For each number, binary search for the position where it should replace an existing tail or extend the array. The length of tails at the end is the LIS length.

💡 Mental model: You're dealing cards into piles. Each new card goes on the leftmost pile whose top card is ≥ the new card (you replace that top card). If no pile works, start a new pile to the right. The number of piles at the end equals the LIS length. Each pile represents extending the longest subsequence by one, and keeping tops as small as possible maximizes future extensions. Binary search finds the right pile in O(log n).

Algorithm

Initialize empty tails array.
For each num: binary search tails for the leftmost value ≥ num.
If found at index pos: tails[pos] = num (replace — keep tails small).
If not found (num is larger than all tails): append num (extend LIS by 1).
Return tails.length.

🎯 When to recognize this pattern:

"Longest subsequence with ordering constraint." The signal: subsequence (not subarray), strictly increasing/decreasing.
O(n²) DP is the standard interview answer; O(n log n) patience sort is the follow-up.
Also used in LC 354 (Russian Doll Envelopes — 2D LIS), LC 673 (Number of LIS).

Why tails is not the actual LIS:

The tails array tracks the smartest possible tails for subsequences of each length — it's NOT a valid subsequence itself.
Its length equals the LIS length, but reconstruct the actual LIS requires tracking back-pointers (not asked in this problem).

Section Four · Trace

Visual Walkthrough

Trace for nums = [10, 9, 2, 5, 3, 7, 101, 18].

LIS — Patience Sort (binary search on tails)

Section Five · Implementation

Code — Java & Python

Java — Patience sort O(n log n)

 import java.util.*;
class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = Collections.binarySearch(tails, num);
if (pos < 0) pos = -(pos + 1); // insertion point if (pos == tails.size())
                tails.add(num); // extend LIS else
tails.set(pos, num); // replace — keep tails small
}
return tails.size();
    }
}

Python — Patience sort O(n log n)

 import bisect
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []
for num in nums:
            pos = bisect.bisect_left(tails, num)
if pos == len(tails):
                tails.append(num) # extend LIS else:
                tails[pos] = num # replace — keep tails small return len(tails)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force (all subsequences)	O(2ⁿ)	O(n)	Impossible for n=2500
DP O(n²)	O(n²)	O(n)	Standard interview answer; simple to code
Patience sort ← optimal	O(n log n)	O(n)	Binary search on tails array; follow-up answer

When to use which: O(n²) DP is preferred in interviews when the interviewer asks "describe your approach" — it's easier to explain. Patience sort / binary search is the follow-up for "can you do better?" Know both.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[5]`	LIS = 1. Both approaches handle trivially.
Already sorted	`[1,2,3,4]`	LIS = n. Tails grows every step.
Reverse sorted	`[4,3,2,1]`	LIS = 1. Each element replaces tails[0].
All equal	`[7,7,7]`	LIS = 1. Strictly increasing — equal doesn't count.
Negative numbers	`[-1,-2,3]`	Works normally. LIS = [-2, 3] length 2.
bisect_left vs bisect_right	`[1,3,3,5]`	Must use bisect_left for strict increase — bisect_right would allow equal elements.

⚠ Common Mistake: Initializing dp[i] = 0 instead of 1. Every single element is an increasing subsequence of length 1. Starting at 0 means the final max is one less than correct. Always Arrays.fill(dp, 1).

← Back to DP — 1D problems

LearningTree

LC 300 · Longest Increasing Subsequence — Solution & Explanation | DSA Guide