LIS LeetCode 300 — DP and Binary Search

LeetCode 300 — Longest Increasing Subsequence — asks you to find the length of the longest strictly increasing subsequence in an integer array nums. A subsequence is derived from the array by deleting some or no elements without changing the relative order of the remaining elements. The subsequence does not need to be contiguous — elements can be spread across any positions in the original array, as long as their original left-to-right order is preserved.

For example, given nums = [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] with length 4. Multiple valid LIS sequences may exist — the problem only asks for the length, not the actual subsequence itself. The strict monotonicity means each subsequent element must be strictly greater than the previous; equal values do not count.

LeetCode 300 is rated Medium and is one of the most important DP problems in technical interviews. It appears frequently at top-tier companies and serves as the foundation for a family of subsequence DP problems. Two distinct solutions exist: an O(n^2) DP approach that is expected in most interviews, and an O(n log n) patience sorting approach that demonstrates mastery of binary search optimization.

The standard DP approach defines dp[i] as the length of the longest increasing subsequence that ends at index i. Every element starts as a subsequence of length 1 (itself alone), so dp[i] is initialized to 1 for all i. To fill dp[i], we examine every index j where j < i and nums[j] < nums[i] — meaning nums[j] can legally precede nums[i] in an increasing subsequence. For each such j, dp[i] = max(dp[i], dp[j] + 1).

After filling the entire dp array, the answer is the maximum value in dp. The recurrence captures the idea that the longest increasing subsequence ending at i is one longer than the longest increasing subsequence ending at any earlier index j that can be extended by nums[i]. Because we check all valid j for each i, the time complexity is O(n^2). The space complexity is O(n) for the dp array.

This approach is straightforward to code and reason about, making it the expected solution in most interview contexts. For n up to 2500, O(n^2) is roughly 6.25 million operations — well within the time limit. The DP table also provides a clear mental model: each dp[i] is an independent subproblem whose solution builds on previously solved subproblems to its left.

Initialize a dp array of length n with all values set to 1 — every element by itself is an increasing subsequence of length 1. Then run a nested loop: outer loop i from 1 to n-1 (inclusive), inner loop j from 0 to i-1. For each pair (j, i), if nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1). After the inner loop completes for index i, dp[i] holds the length of the LIS ending at i.

Track a global maximum variable ans initialized to 1. After each update to dp[i], check if dp[i] > ans and update ans accordingly. Alternatively, compute max(dp) after the outer loop completes. Both approaches yield O(n) extra work and do not affect overall time complexity. The answer is returned as ans after both loops finish.

Common pitfalls: forgetting to initialize dp[i] = 1 (some implementations accidentally leave it at 0); using nums[j] <= nums[i] instead of strictly less-than (which would find the longest non-decreasing subsequence, not strictly increasing); starting the outer loop at i = 0 (valid but the inner loop runs zero iterations, so nothing changes — initializing dp[0] = 1 and starting at i = 1 is cleaner and slightly more efficient).

The O(n log n) algorithm maintains a tails array where tails[k] represents the smallest tail element among all increasing subsequences of length k+1 seen so far. Initially tails is empty. For each number in nums, we either extend the longest known subsequence (if the number is greater than all tails) or find the leftmost position in tails where we can replace the current tail with a smaller value.

The key invariant is that tails is always sorted in strictly increasing order. This invariant holds because: if tails[k] >= tails[k+1] at any point, it would mean there is an increasing subsequence of length k+2 whose tail is not strictly greater than the tail of a subsequence of length k+1 — a contradiction. The sorted invariant enables binary search to find the correct insertion position in O(log n) per element.

After processing all n elements, the length of the tails array equals the length of the LIS. The algorithm runs in O(n log n) total time: O(n) elements each requiring O(log n) binary search. Space is O(n) for the tails array. This is optimal for comparison-based LIS algorithms — a lower bound of O(n log n) exists for LIS in the comparison model.

For each number num in the input array, we perform one of two operations on tails. If num is strictly greater than the last element of tails, we append num — this extends the current longest known subsequence by one. The LIS length grows by 1. This is the "extend" case: num can be placed at the end of the longest known increasing subsequence.

If num is not greater than the last element of tails, we find the leftmost position pos in tails such that tails[pos] >= num, then set tails[pos] = num. This "replacement" keeps tails as small as possible at every position, maximizing the chance that future elements can extend subsequences. In Python, bisect_left(tails, num) gives pos directly. In Java, Arrays.binarySearch handles this with some offset arithmetic.

The intuition behind replacement: if we have a subsequence of length k+1 ending in a large value, and we find a new element that could end a subsequence of the same length with a smaller value, we prefer the smaller ending. A smaller ending makes it strictly easier for future elements to extend that subsequence. Replacing never decreases the LIS length — it only improves future potential.

Python O(n^2) DP (8 lines): def lengthOfLIS(nums): n = len(nums); dp = [1] * n; ans = 1; for i in range(1, n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); return ans. Python O(n log n) (10 lines): from bisect import bisect_left; def lengthOfLIS(nums): tails = []; for num in nums: pos = bisect_left(tails, num); if pos == len(tails): tails.append(num); else: tails[pos] = num; return len(tails).

Java O(n^2) DP: public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int ans = 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); } ans = Math.max(ans, dp[i]); } return ans; }. Java O(n log n): 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); if (pos == tails.size()) tails.add(num); else tails.set(pos, num); } return tails.size(); }.

The bisect_left call in Python finds the leftmost index where num can be inserted to keep tails sorted — equivalent to the first position where tails[pos] >= num. In Java, Collections.binarySearch returns a negative value -(insertion_point) - 1 when the element is not found; converting with -(pos+1) gives the insertion point. Both approaches correctly identify the replacement position. The O(n^2) solution is 8 lines in Python and 9 in Java; the O(n log n) is 10 lines in Python and 10 in Java.

Longest Common Subsequence (LeetCode 1143) is the 2D analogue of LIS. Instead of finding the longest increasing subsequence of a single array, LCS finds the longest subsequence common to two strings. The recurrence is dp[i][j] = dp[i-1][j-1] + 1 if s1[i] == s2[j], else max(dp[i-1][j], dp[i][j-1]). LCS runs in O(mn) time and can be space-optimized to O(min(m,n)). Many string DP problems — edit distance, shortest common supersequence — reduce to or build upon LCS.

Longest Palindromic Subsequence (LeetCode 516) asks for the LCS of a string with its reverse. It uses the same 2D DP table as LCS but applied to a single string and its mirror. House Robber II (LeetCode 213) is a linear DP problem with a circular constraint — not a subsequence problem, but it shares the same "define dp[i] over a linear scan" template. Both are important members of the DP problem family that appears frequently in top-tier interviews.

The subsequence family — LIS, LCS, longest palindromic subsequence, longest bitonic subsequence, number of LIS — all share the structural insight that subsequences preserve relative order. LIS is the gateway to this family. Once you internalize the dp[i] = "best ending at i" pattern and the patience sorting O(n log n) optimization, the other subsequence problems feel like natural extensions. Practice LIS until both the O(n^2) and O(n log n) solutions feel automatic before moving on.