Longest Increasing Subsequence

Q: How do you solve Longest Increasing Subsequence?

Implement a top-down recursive DP with memoization. For each index i, compute dp(i) by checking all previous indices j < i where nums[j] < nums[i], and take the maximum dp(j) + 1. The final answer is the maximum dp(i) over all indices. This approach runs in O(n^2) time and O(n) space.

Q: What is the time complexity of Longest Increasing Subsequence?

O(n^2). For each index i, the algorithm checks all previous indices j < i, resulting in a nested loop behavior. Memoization ensures each dp(i) is computed once, leading to O(n^2) total computations.

Q: What pattern does Longest Increasing Subsequence use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: When a problem asks for an optimal subsequence or substructure that depends on previous states, define a recursive function representing the solution for a subproblem and cache results to avoid redundant work, transforming exponential recursion into polynomial time.

Medium Dynamic Programming

Problem

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

1 ≤ nums.length ≤ 2500
−10⁴ ≤ nums[i] ≤ 10⁴

Example

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

Output: 4

The longest increasing subsequence is [2,3,7,101], which has length 4. The algorithm uses recursion with memoization to compute the LIS ending at each index. For example, at index 6 (value 101), it checks all previous indices with smaller values (like 7 at index 5) and builds upon their LIS lengths. The critical moment is recognizing that the LIS ending at index 6 is 1 plus the maximum LIS among all indices with smaller values before it. Memoization avoids redundant recomputation by caching results for each index.

Approach

Straightforward Solution

A brute-force approach tries all subsequences, which is exponential in time and infeasible for large inputs.

Core Observation

The length of the longest increasing subsequence ending at position i depends on the lengths of all increasing subsequences ending at positions before i with smaller values. This exhibits optimal substructure and overlapping subproblems, making it a natural fit for dynamic programming.

Path to Optimal

Preview

Recognizing the problem's optimal substructure allows defining a recursive function dp(i) that returns the LIS length ending at index i. For each i, dp(i) is 1 plus the maximum dp(j) for all j < i where nums[j] < nums[i]…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a top-down recursive DP with memoization. For each index i, compute dp(i) by checking all previous indices j < i where nums[j] < nums[i], and take the maximum dp(j) + 1…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

For each index i, the algorithm checks all previous indices j < i, resulting in a nested loop behavior. Memoization ensures each dp(i) is computed once, leading to O(n^2) total computations.

Space

O(n)

The memo dictionary stores one entry per index, and the recursion stack depth is at most n, resulting in O(n) auxiliary space.

Pattern Spotlight

Dynamic Programming (Top-Down Memoization)

When a problem asks for an optimal subsequence or substructure that depends on previous states, define a recursive function representing the solution for a subproblem and cache results to avoid redundant work, transforming exponential recursion into polynomial time.

Solution

Python

1class Solution:
  def lengthOfLIS(self, nums: list[int]) -> int:
      memo = {}
4
      def dp(i):
          if i in memo:
              return memo[i]
          
          max_len = 1 
          for j in range(i):
              if nums[i] > nums[j]:
                  max_len = max(max_len, 1 + dp(j))
          
          memo[i] = max_len
          return max_len
16
      if not nums:
          return 0
      return max(dp(i) for i in range(len(nums)))

Step-by-Step Solution

Handle Empty Input Edge Case

17if not nums:
18    return 0

Objective

To immediately return 0 if the input array is empty, as no subsequence exists.

Key Insight

An empty input means there are no elements to form any subsequence, so the longest increasing subsequence length is zero. Handling this edge case upfront prevents unnecessary recursion and potential errors.

Interview Quick-Check

State & Boundaries

Check if nums is empty before any processing to handle trivial input cases correctly.

Compute LIS Lengths Using Memoized Recursion

To recursively compute the length of the longest increasing subsequence ending at each index, caching results to avoid redundant work.

Aggregate Final Result from All Subproblems

To find the overall longest increasing subsequence length by taking the maximum dp(i) over all indices.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 6 Critical

if i in memo:

Return cached result if dp(i) has been computed before.

This memoization check prevents repeated work and is the key optimization that reduces time complexity from exponential to polynomial.

Line 12 Critical

max_len = max(max_len, 1 + dp(j))

Update max_len by considering the LIS ending at j plus nums[i].

This line embodies the core DP recurrence: the LIS ending at i is 1 plus the maximum LIS ending at any smaller previous element, capturing optimal substructure.

Line 7 Critical

return memo[i]

Return the cached LIS length for index i.

Returning the cached value immediately avoids unnecessary recursion and ensures correctness by reusing previously computed results.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why does memoization significantly improve the performance of the recursive LIS solution?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest Increasing Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Increasing Subsequence drill

or drill a free problem

1	`class Solution:`
2	`def lengthOfLIS(self, nums: list[int]) -> int:`
3	`memo = {}`
4
5	`def dp(i):`
6	`if i in memo:`
7	`return memo[i]`
8
9	`max_len = 1`
10	`for j in range(i):`
11	`if nums[i] > nums[j]:`
12	`max_len = max(max_len, 1 + dp(j))`
13
14	`memo[i] = max_len`
15	`return max_len`
16
17	`if not nums:`
18	`return 0`
19	`return max(dp(i) for i in range(len(nums)))`