Problem and Naive DP
LIS: find the length of the longest strictly increasing subsequence of an array. Elements of the subsequence need not be adjacent. Example: [10,9,2,5,3,7,101,18] → LIS length = 4 ([2,3,7,101] or [2,5,7,101]).
O(n^2) DP: dp[i] = length of LIS ending at index i. dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). Answer = max(dp). Two nested loops. O(n^2) time, O(n) space.
def lengthOfLIS_n2(nums):
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)O(n log n) with Binary Search (Patience Sorting)
Maintain a “tails” array where tails[i] is the smallest tail element of all increasing subsequences of length i+1 seen so far. For each number: binary search for the leftmost position in tails where tails[pos] >= num. Replace tails[pos] with num (or append if num is larger than all). The length of tails at the end is the LIS length. The tails array is always sorted, enabling binary search. The binary search is lower_bound (first element >= num).
import bisect
def lengthOfLIS(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num) # first pos where tails[pos] >= num
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Why it works: tails represents the “optimal ending” for subsequences of each length. Replacing tails[pos] with a smaller num keeps future options open (a smaller ending allows more numbers to extend the subsequence). The tails array does NOT represent an actual LIS, but its length equals the LIS length. To reconstruct the actual LIS: track the predecessor array separately (O(n^2) extra space or use a more complex algorithm).
LIS Variants
Longest Non-Decreasing Subsequence: use bisect_right instead of bisect_left (allows equal elements). Russian Doll Envelopes (LC 354): envelope (w, h) can contain another if w and h are both strictly smaller. Sort by width ascending, then height descending. Then apply LIS on heights only. The descending height sort for equal widths ensures we don’t use two envelopes with the same width in the same subsequence. O(n log n). Maximum Length of Pair Chain (LC 646): pairs where pair[0] < prev[1]. Sort by second element. Apply greedy (same as activity selection). O(n log n). LC 300 (LIS length), LC 673 (number of LIS), LC 368 (largest divisible subset).
Number of LIS (LC 673)
Count all distinct LIS of maximum length. O(n^2) DP: maintain two arrays: length[i] = LIS length ending at i, count[i] = number of such LIS. For each i, j < i: if nums[j] length[i]: update length[i], reset count[i] = count[j]. If length[j]+1 == length[i]: count[i] += count[j]. Answer = sum of count[i] for all i where length[i] == max_length.
Largest Divisible Subset (LC 368)
Find the largest subset where every pair (a, b) satisfies a % b == 0 or b % a == 0. Sort the array. If a[i] % a[j] == 0 and a[j] is part of a divisible subset, then a[i] can be appended (divisibility is transitive in sorted order). This reduces to LIS with a custom comparison. Apply O(n^2) DP: dp[i] = largest subset ending at a[i]. Track predecessors to reconstruct the subset.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why does the patience sorting approach give O(n log n) LIS?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Patience sorting maintains a “tails” array where tails[i] is the minimum possible tail value of any increasing subsequence of length i+1. For each number, binary search (bisect_left) for the leftmost position where tails[pos] >= num. This search is O(log n) since tails is always sorted. Replace tails[pos] with num (or append). The replacement keeps future options open: a smaller tail allows more elements to extend the subsequence. The total complexity is O(n log n) — n elements each requiring one O(log n) binary search. The tails array length at the end equals the LIS length. Note: tails does not contain an actual LIS; it is a bookkeeping structure optimized for counting.”
}
},
{
“@type”: “Question”,
“name”: “How do you reconstruct the actual LIS (not just its length)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Track a predecessor array. For each index i, pred[i] stores the index of the element before nums[i] in the LIS ending at i. Also track the index in tails that was updated for each element (not just the value). During the binary search step: when tails[pos] = nums[i], record index_at_level[pos] = i and pred[i] = (pos > 0 ? index_at_level[pos-1] : -1). After processing all elements, the last LIS element is at index_at_level[len(tails)-1]. Trace back through pred to reconstruct the full sequence. This requires O(n) extra space. The reconstruction is O(n) once you have the predecessor array.”
}
},
{
“@type”: “Question”,
“name”: “How does sorting trick solve Russian Doll Envelopes?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Each envelope (w, h) fits inside another if both width and height are strictly smaller. Naive approach: sort by width, then apply LIS on heights. Problem: two envelopes with the same width (w1=w2) — you might include both in the LIS even though they cannot nest (same width). Fix: sort by width ascending, then height descending for equal widths. Now for any group of equal-width envelopes, their heights are in descending order. When applying LIS on heights, bisect_left will place each of these heights at or before the previous one — they will never all be selected together in the LIS. This is the key insight: the descending sort within equal widths makes it impossible for two same-width envelopes to both appear in the LIS. Then apply standard O(n log n) LIS on the height values.”
}
},
{
“@type”: “Question”,
“name”: “What is the difference between bisect_left and bisect_right in the LIS algorithm?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “bisect_left finds the leftmost position where the value can be inserted to keep the array sorted — specifically, the first position where tails[pos] >= num. This replaces the first element that is >= num, enforcing strict increase (nums[j] num. This replaces the first element that is > num, allowing equal elements (nums[j] <= nums[i]), giving the Longest Non-Decreasing Subsequence instead of strictly increasing. Rule: for strictly increasing LIS, use bisect_left. For non-decreasing, use bisect_right. Getting this wrong is a common interview mistake — clarify whether the problem wants strictly increasing or non-decreasing."
}
},
{
"@type": "Question",
"name": "How does LIS relate to other classic DP problems?",
"acceptedAnswer": {
"@type": "Answer",
"text": "LIS is a special case of Longest Common Subsequence (LCS): the LIS of array A equals the LCS of A and sorted(A). This gives an O(n log n) algorithm via the O(n log n) LIS, but LCS itself is O(n^2). LIS also underlies the patience sorting card game algorithm for computing the minimum number of piles. The Russian Doll Envelopes problem is 2D LIS. The Maximum Length of Pair Chain (LC 646) is equivalent to LIS with a custom comparator and can be solved greedily. The Largest Divisible Subset (LC 368) is LIS with divisibility as the ordering relation. Recognizing these reductions is the key skill: when you see a problem asking for the longest chain where each element extends the previous by some property, try mapping it to LIS."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide