Autocoder

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 DPO(n^2) time, O(n) space
Fast versionO(n log n) with binary search
Key distinctionSubsequence is not subarray
VariantsCount, 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

Longest Increasing Subsequence (LIS) Interview Questions: questions with worked answers

  1. 1

    Longest increasing subsequence in O(n^2)

    medium

    Let 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.

    python
    def 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)
    java
    int 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. 2

    Longest increasing subsequence in O(n log n)

    medium

    Keep 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.

    python
    from 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)
    java
    int 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. 3

    Print an actual longest increasing subsequence

    medium

    Extend 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.

    python
    def 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]
    java
    List<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. 4

    Number of longest increasing subsequences

    medium

    Track 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.

    python
    def 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)
    java
    int 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. 5

    Increasing triplet subsequence

    easy

    You 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.

    python
    def 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 False
    java
    boolean 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. 6

    Minimum deletions to make an array sorted

    medium

    Elements 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.

    python
    from 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)
    java
    int 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. 7

    Maximum sum increasing subsequence

    medium

    Same 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).

    python
    def 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)
    java
    long 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. 8

    Longest arithmetic subsequence with a given difference

    medium

    With 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.

    python
    def longest_subsequence(arr, d):
        dp = {}
        for x in arr:
            dp[x] = dp.get(x - d, 0) + 1
        return max(dp.values(), default=0)
    java
    int 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. 9

    Largest divisible subset

    medium

    If 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.

    python
    def 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]
    java
    List<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. 10

    Longest bitonic subsequence

    hard

    A 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.

    python
    def 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)
    java
    int 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. 11

    Russian doll envelopes: maximum nesting chain

    hard

    An 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.

    python
    from 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)
    java
    int 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

See all in this section