Longest Increasing Subsequence (LIS) Interview Questions
Last updated 2026-11-19
The longest increasing subsequence problem asks for the longest sequence of elements, in original order but not necessarily adjacent, that strictly increases. It is a favourite because it has a simple O(n^2) dynamic programming solution and a clever O(n log n) improvement, so an interviewer can test depth with follow-ups.
This page covers both solutions and the variants built on them: printing the sequence, counting, bitonic, envelopes and more, each with Python and Java code, complexity and edge cases. Wider DP technique is in dynamic programming interview questions; a related two-sequence problem is in longest common subsequence interview questions.
| Quadratic DP | O(n^2) time, O(n) space |
|---|---|
| Fast version | O(n log n) with binary search |
| Key distinction | Subsequence is not subarray |
| Variants | Count, print, bitonic, 2D nesting |
The pattern and when to spot it
Think LIS whenever a question asks for the longest chain in which each item must be larger, later or nested relative to the previous one, and items can be skipped. Chains of envelopes, boxes, divisible numbers and string predecessors are all LIS with a different comparison.
The quadratic DP defines dp[i] as the best chain ending exactly at i, which gives the freedom to add parent pointers, counts or sums. The fast version keeps tails, the smallest possible last element for each length, which stays sorted and so supports binary search. It only gives the length; to print the sequence you must also record where each tail came from. For two-dimensional nesting, sort on one dimension so only the second one remains, and break ties so equal values cannot chain.
Frequent mistakes
- Returning dp[n-1] instead of the maximum over all dp values.
- Using bisect_right or upper bound for a strict LIS, which lets equal values extend a chain.
- Treating the tails array as the actual subsequence. It usually is not.
- Forgetting that the quadratic version cannot handle n above about 10^4 in time limits.
- Sorting ties in the wrong direction in the envelope problem.
Longest Increasing Subsequence (LIS) Interview Questions: questions with worked answers
1 Longest increasing subsequence in O(n^2)
mediumLet dp[i] be the length of the longest strictly increasing subsequence ending at index i. It is 1 plus the best dp[j] over earlier j with a[j] < a[i]. The answer is the maximum over all i, not dp[n-1]. A subsequence keeps order but may skip elements, unlike a subarray. Time O(n^2), space O(n). Edge cases: empty array (0), all equal values (1), strictly decreasing (1), the answer is not necessarily at the last index.
pythondef lis(a): n = len(a) dp = [1] * n for i in range(n): for j in range(i): if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp, default=0)javaint lis(int[] a) { int n = a.length, best = 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1); best = Math.max(best, dp[i]); } return best; }2 Longest increasing subsequence in O(n log n)
mediumKeep an array tails where tails[k] is the smallest possible last value of an increasing subsequence of length k+1. For each number, binary search the first tail that is not smaller than it and replace that tail, or append if none exists. The length of tails is the answer. The array is not itself an LIS. Time O(n log n), space O(n). Edge cases: duplicates (lower bound replaces equal, giving a strict LIS), empty input, a descending array (tails stays length 1), tails does not hold the actual subsequence.
pythonfrom bisect import bisect_left def lis_fast(a): tails = [] for x in a: i = bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails)javaint lisFast(int[] a) { int[] tails = new int[a.length]; int len = 0; for (int x : a) { int i = Arrays.binarySearch(tails, 0, len, x); if (i < 0) i = -i - 1; tails[i] = x; if (i == len) len++; } return len; }3 Print an actual longest increasing subsequence
mediumExtend the fast method to store indexes. tails[k] holds the index of the smallest tail for length k+1, and prev[i] records the index of the element before i in the best subsequence ending at i, which is tails[k-1] when i is placed at position k. After the pass, follow prev from the last tail back and reverse. Time O(n log n), space O(n). Edge cases: empty input, several valid subsequences (any is correct unless a tie rule is given), forgetting prev when k is 0.
pythondef lis_sequence(a): tails, prev = [], [-1] * len(a) for i, x in enumerate(a): lo, hi = 0, len(tails) while lo < hi: mid = (lo + hi) // 2 if a[tails[mid]] < x: lo = mid + 1 else: hi = mid if lo > 0: prev[i] = tails[lo - 1] if lo == len(tails): tails.append(i) else: tails[lo] = i out, k = [], tails[-1] if tails else -1 while k != -1: out.append(a[k]) k = prev[k] return out[::-1]javaList<Integer> lisSequence(int[] a) { int n = a.length; int[] tails = new int[n], prev = new int[n]; Arrays.fill(prev, -1); int len = 0; for (int i = 0; i < n; i++) { int lo = 0, hi = len; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[tails[mid]] < a[i]) lo = mid + 1; else hi = mid; } if (lo > 0) prev[i] = tails[lo - 1]; tails[lo] = i; if (lo == len) len++; } LinkedList<Integer> out = new LinkedList<>(); for (int k = len > 0 ? tails[len - 1] : -1; k != -1; k = prev[k]) out.addFirst(a[k]); return out; }4 Number of longest increasing subsequences
mediumTrack two arrays: length[i] for the LIS ending at i and count[i] for how many such subsequences exist. For each j before i with a[j] < a[i], if length[j] + 1 is larger than length[i], copy the count; if equal, add it. The answer sums count[i] over indexes whose length equals the global maximum. Time O(n^2), space O(n). Edge cases: all equal values (n subsequences of length 1), a unique LIS (count 1), counts overflow for long arrays.
pythondef number_of_lis(a): n = len(a) length, count = [1] * n, [1] * n for i in range(n): for j in range(i): if a[j] < a[i]: if length[j] + 1 > length[i]: length[i], count[i] = length[j] + 1, count[j] elif length[j] + 1 == length[i]: count[i] += count[j] best = max(length, default=0) return sum(c for l, c in zip(length, count) if l == best)javaint numberOfLis(int[] a) { int n = a.length; int[] len = new int[n], cnt = new int[n]; int best = 0, total = 0; for (int i = 0; i < n; i++) { len[i] = 1; cnt[i] = 1; for (int j = 0; j < i; j++) if (a[j] < a[i]) { if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; } else if (len[j] + 1 == len[i]) cnt[i] += cnt[j]; } best = Math.max(best, len[i]); } for (int i = 0; i < n; i++) if (len[i] == best) total += cnt[i]; return total; }5 Increasing triplet subsequence
easyYou only need to know whether an increasing subsequence of length 3 exists, so keep the two smallest tails: first is the smallest value seen, second is the smallest end of an increasing pair. Any number bigger than both completes a triplet. This is the fast LIS with tails capped at length 2. Time O(n), space O(1). Edge cases: duplicates (use less-or-equal so equal values do not form a triplet), fewer than three elements, descending input.
pythondef increasing_triplet(nums): first = second = float('inf') for x in nums: if x <= first: first = x elif x <= second: second = x else: return True return Falsejavaboolean increasingTriplet(int[] nums) { int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE; for (int x : nums) { if (x <= first) first = x; else if (x <= second) second = x; else return true; } return false; }6 Minimum deletions to make an array sorted
mediumElements you keep must form a non-decreasing subsequence, so the fewest deletions is n minus the longest non-decreasing subsequence. Use the fast method with an upper bound search so equal values are allowed to stack. Time O(n log n), space O(n). Edge cases: already sorted (0), strictly decreasing (n - 1), equal values count as sorted so use upper bound not lower bound.
pythonfrom bisect import bisect_right def min_deletions_sorted(a): tails = [] for x in a: i = bisect_right(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(a) - len(tails)javaint minDeletionsSorted(int[] a) { int[] tails = new int[a.length]; int len = 0; for (int x : a) { int lo = 0, hi = len; while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] <= x) lo = mid + 1; else hi = mid; } tails[lo] = x; if (lo == len) len++; } return a.length - len; }7 Maximum sum increasing subsequence
mediumSame structure as the quadratic LIS, but dp[i] stores the largest sum of an increasing subsequence ending at i: a[i] plus the best dp[j] with a[j] < a[i]. The answer is the maximum dp value. Length no longer matters, so the O(n log n) tails trick does not apply directly. Time O(n^2), space O(n). Edge cases: negative values (starting fresh may beat extending), a single element, all decreasing (maximum single element).
pythondef max_sum_increasing(a): dp = a[:] for i in range(len(a)): for j in range(i): if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + a[i]) return max(dp, default=0)javalong maxSumIncreasing(int[] a) { long[] dp = new long[a.length]; long best = Long.MIN_VALUE; for (int i = 0; i < a.length; i++) { dp[i] = a[i]; for (int j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + a[i]); best = Math.max(best, dp[i]); } return a.length == 0 ? 0 : best; }8 Longest arithmetic subsequence with a given difference
mediumWith a fixed difference d, the best subsequence ending at value x extends the best one ending at x - d. Keep a hash map from value to the best length and set dp[x] = dp.get(x - d, 0) + 1 as you scan. No inner loop is needed. Time O(n), space O(n). Edge cases: d equal to 0 (counts of equal values), negative d, duplicates overwriting with a later, never worse, length.
pythondef longest_subsequence(arr, d): dp = {} for x in arr: dp[x] = dp.get(x - d, 0) + 1 return max(dp.values(), default=0)javaint longestSubsequence(int[] arr, int d) { Map<Integer, Integer> dp = new HashMap<>(); int best = 0; for (int x : arr) { int len = dp.getOrDefault(x - d, 0) + 1; dp.put(x, len); best = Math.max(best, len); } return best; }9 Largest divisible subset
mediumIf numbers are sorted, a chain where each element divides the next is automatically pairwise divisible. Sort, then dp[i] is the longest chain ending at i with a parent pointer to the previous element, over j with a[i] % a[j] == 0. Follow the parents from the best end. Time O(n^2), space O(n). Edge cases: duplicates are not allowed by the problem, a single number, 1 divides everything, empty input.
pythondef largest_divisible_subset(nums): nums.sort() n = len(nums) if n == 0: return [] dp, parent = [1] * n, [-1] * n best = 0 for i in range(n): for j in range(i): if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]: dp[i], parent[i] = dp[j] + 1, j if dp[i] > dp[best]: best = i out = [] while best != -1: out.append(nums[best]) best = parent[best] return out[::-1]javaList<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); int n = nums.length; List<Integer> out = new ArrayList<>(); if (n == 0) return out; int[] dp = new int[n], parent = new int[n]; Arrays.fill(dp, 1); Arrays.fill(parent, -1); int best = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; parent[i] = j; } if (dp[i] > dp[best]) best = i; } for (; best != -1; best = parent[best]) out.add(nums[best]); Collections.reverse(out); return out; }10 Longest bitonic subsequence
hardA bitonic subsequence rises and then falls. Compute inc[i], the LIS ending at i from the left, and dec[i], the longest decreasing subsequence starting at i (an LIS from the right). The answer is the maximum of inc[i] + dec[i] - 1, since index i is counted in both. Time O(n^2), space O(n). Edge cases: purely increasing or decreasing arrays (allowed, one side has length 1), a single element, subtracting the shared peak.
pythondef longest_bitonic(a): n = len(a) inc, dec = [1] * n, [1] * n for i in range(n): for j in range(i): if a[j] < a[i]: inc[i] = max(inc[i], inc[j] + 1) for i in range(n - 1, -1, -1): for j in range(n - 1, i, -1): if a[j] < a[i]: dec[i] = max(dec[i], dec[j] + 1) return max((inc[i] + dec[i] - 1 for i in range(n)), default=0)javaint longestBitonic(int[] a) { int n = a.length, best = 0; int[] inc = new int[n], dec = new int[n]; Arrays.fill(inc, 1); Arrays.fill(dec, 1); for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (a[j] < a[i]) inc[i] = Math.max(inc[i], inc[j] + 1); for (int i = n - 1; i >= 0; i--) for (int j = n - 1; j > i; j--) if (a[j] < a[i]) dec[i] = Math.max(dec[i], dec[j] + 1); for (int i = 0; i < n; i++) best = Math.max(best, inc[i] + dec[i] - 1); return best; }11 Russian doll envelopes: maximum nesting chain
hardAn envelope fits inside another only if both width and height are strictly smaller. Sort by width ascending and, for equal widths, by height descending, so envelopes of equal width can never chain. Then the answer is the strict LIS of the heights, computed in O(n log n). Time O(n log n), space O(n). Edge cases: equal widths (the descending height order is essential), a single envelope, identical envelopes, strictness on both dimensions.
pythonfrom bisect import bisect_left def max_envelopes(envelopes): envelopes.sort(key=lambda e: (e[0], -e[1])) tails = [] for _, h in envelopes: i = bisect_left(tails, h) if i == len(tails): tails.append(h) else: tails[i] = h return len(tails)javaint maxEnvelopes(int[][] env) { Arrays.sort(env, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1])); int[] tails = new int[env.length]; int len = 0; for (int[] e : env) { int lo = 0, hi = len; while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] < e[1]) lo = mid + 1; else hi = mid; } tails[lo] = e[1]; if (lo == len) len++; } return len; }
Frequently asked questions
What is the difference between a subarray and a subsequence?
A subarray is contiguous. A subsequence keeps the original order but may skip elements. LIS is about subsequences, which is why a simple sliding window does not solve it.
How does the O(n log n) LIS algorithm work?
It maintains an array where entry k is the smallest tail of any increasing subsequence of length k+1. Each new number replaces the first tail not smaller than it, or extends the array. The array length is the answer.
How do I get the LIS itself, not just its length?
Store indexes in tails and a parent array pointing to the previous element for each position. After the scan, follow parents from the last tail and reverse the result.
Is LIS common in coding rounds?
It appears regularly, often disguised as envelopes, box stacking or chain problems. The online assessment guide explains how such tests are typically structured.
Related guides
More in DSA Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions