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.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide