How to Solve: Longest Increasing Subsequence (LIS) – Complete Guide for FAANG Interviews

How to Solve: Longest Increasing Subsequence (LIS) – Complete Guide for FAANG Interviews

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—nail it and you prove you can optimize dynamic programming problems under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling LIS, ensure you understand: 1. Dynamic Programming (DP) – Memoization, tabulation, and state transitions. 2. Binary Search – Efficiently finding insertion points in sorted arrays. 3. Time Complexity Analysis – Recognizing O(n²) vs. O(n log n) trade-offs.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see an LIS problem:

1. Clarify the Problem
2. Is the sequence strictly increasing (nums[i] < nums[j]) or non-decreasing (nums[i] ≤ nums[j])?
3. Do we need the length or the actual sequence?

4. Are there constraints (e.g., no duplicates, circular array)?

5. Choose the Right Approach

6. Small input (n ≤ 10³)? → DP (O(n²))
7. Large input (n > 10³)? → Greedy + Binary Search (O(n log n))

8. Follow-up (return sequence)? → Backtrack with parent pointers

9. Implement DP (If Applicable)

10. Initialize dp = [1] n (each element is a subsequence of length 1).
11. For each i from 1 to n-1:
    • For each j from 0 to i-1:
    • If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).

12. Return max(dp).

13. Implement Greedy + Binary Search (If Applicable)

14. Initialize tails = [].
15. For each num in nums:
    • Use bisect_left to find the first index in tails where tails[i] ≥ num.
    • If index == len(tails), append num to tails.
    • Else, replace tails[index] = num.

16. Return len(tails).

17. Handle Follow-Ups

18. Return the sequence? → Track parent indices during DP or use tails + backtracking.
19. Circular array? → Solve twice (once for nums, once for nums[1:] + nums[:1]).

20. Non-strictly increasing? → Adjust comparisons (≤ instead of <).

21. Optimize Space (If Needed)

22. DP: Can we reduce dp to O(n) or O(1)? (Usually not, but tails is O(n).)

23. Greedy: tails is already O(n).

24. Test Edge Cases

25. Empty array → Return 0.
26. Single element → Return 1.
27. All elements equal → Return 1 (strict) or n (non-strict).
28. Strictly decreasing → Return 1.

? WORKED EXAMPLES

Example 1 – Basic (DP Approach)

Problem: Given an integer array nums, return the length of the longest strictly increasing subsequence.

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 (LIS: [2, 3, 7, 101])

Step-by-Step Solution

1. Clarify: Strictly increasing, return length only.
2. Choose Approach: DP (n = 8, small input).
3. Initialize dp = [1] 8 (each element is a subsequence of length 1).
4. Fill dp:
5. i=1 (nums[1]=9): No j where nums[j] < 9 → dp[1]=1.
6. i=2 (nums[2]=2): j=0 (nums[0]=10 > 2), j=1 (nums[1]=9 > 2) → dp[2]=1.
7. i=3 (nums[3]=5): j=2 (nums[2]=2 < 5) → dp[3] = max(1, dp[2]+1) = 2.
8. i=4 (nums[4]=3): j=2 (nums[2]=2 < 3) → dp[4] = max(1, dp[2]+1) = 2.
9. i=5 (nums[5]=7): j=2 (nums[2]=2 < 7), j=3 (nums[3]=5 < 7), j=4 (nums[4]=3 < 7) → dp[5] = max(1, dp[2]+1, dp[3]+1, dp[4]+1) = 3.
10. i=6 (nums[6]=101): j=2 (nums[2]=2 < 101), j=3 (nums[3]=5 < 101), j=4 (nums[4]=3 < 101), j=5 (nums[5]=7 < 101) → dp[6] = 4.
11. i=7 (nums[7]=18): j=2 (nums[2]=2 < 18), j=3 (nums[3]=5 < 18), j=4 (nums[4]=3 < 18), j=5 (nums[5]=7 < 18) → dp[7] = 4.
12. Result: max(dp) = 4.

Python Code (DP)

def lengthOfLIS(nums):

    if not nums:

        return 0

    dp = [1]  len(nums)

    for i in range(1, len(nums)):

        for j in range(i):

            if nums[j] < nums[i]:

                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Time Complexity: O(n²) Space Complexity: O(n)

Why This Works: - dp[i] stores the length of the LIS ending at nums[i]. - For each i, we check all previous j to see if nums[j] can extend the subsequence.

Example 2 – Medium (Greedy + Binary Search)

Problem: Same as above, but nums can be large (n ≤ 10⁵).

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4

Step-by-Step Solution

1. Clarify: Strictly increasing, large input → use greedy + binary search.
2. Initialize tails = [] (stores smallest possible tail for LIS of length i+1).
3. Iterate through nums:
4. num=10: tails = [10].
5. num=9: Replace tails[0] (first ≥ 9) → tails = [9].
6. num=2: Replace tails[0] → tails = [2].
7. num=5: Append (no ≥ 5) → tails = [2, 5].
8. num=3: Replace tails[1] → tails = [2, 3].
9. num=7: Append → tails = [2, 3, 7].
10. num=101: Append → tails = [2, 3, 7, 101].
11. num=18: Replace tails[3] → tails = [2, 3, 7, 18].
12. Result: len(tails) = 4.

Python Code (Greedy + Binary Search)

import bisect

def lengthOfLIS(nums):

    tails = []

    for num in nums:

        idx = bisect.bisect_left(tails, num)

        if idx == len(tails):

            tails.append(num)

        else:

            tails[idx] = num

    return len(tails)

Time Complexity: O(n log n) Space Complexity: O(n)

Why This Works: - tails maintains the smallest possible tail for each LIS length. - Binary search (bisect_left) finds where to place num in O(log n) time.

Example 3 – Hard (Return the Actual LIS)

Problem: Return the longest increasing subsequence itself (not just length).

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: [2, 3, 7, 101] (or [2, 5, 7, 101], etc.)

Step-by-Step Solution

1. Clarify: Return the sequence, not just length.
2. Approach: DP + backtracking (or greedy + parent pointers).
3. DP Approach:
4. Compute dp as in Example 1.
5. Track parent array to reconstruct the sequence.
6. Backtrack:
7. Find the index of max(dp).
8. Follow parent pointers to build the sequence.

Python Code (DP + Backtracking)

def lengthOfLIS(nums):

    if not nums:

        return []

    dp = [1]  len(nums)

    parent = [-1]  len(nums)

    for i in range(1, len(nums)):

        for j in range(i):

            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:

                dp[i] = dp[j] + 1

                parent[i] = j

    max_len = max(dp)

    max_idx = dp.index(max_len)

    res = []

    while max_idx != -1:

        res.append(nums[max_idx])

        max_idx = parent[max_idx]

    return res[::-1]

Time Complexity: O(n²) Space Complexity: O(n)

Why This Works: - parent[i] stores the index of the previous element in the LIS ending at i. - Backtracking from max_idx reconstructs the sequence.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For LIS problems, start by clarifying: strict or non-strict? Length or sequence? Small or large input? If it’s small (n ≤ 10³), use DP—initialize dp = [1] n, fill it with nested loops, and return max(dp). For large inputs, switch to greedy + binary search: maintain a tails array, use bisect_left to find insertion points, and return len(tails). If they ask for the sequence, track parent pointers during DP or backtrack from tails. Watch out for edge cases—empty array, single element, duplicates—and adjust comparisons for non-strict LIS. Practice both approaches, and you’ll crush this in any interview. Good luck!

? Final Notes

• Practice Problems:
• LeetCode 300. Longest Increasing Subsequence
• LeetCode 673. Number of Longest Increasing Subsequence
• LeetCode 354. Russian Doll Envelopes (2D LIS)
• Key Takeaway: Master both DP and greedy + binary search. Know when to use each.