300. Longest Increasing Subsequence - Detailed Explanation

Problem Statement

You are given an integer array nums. An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order, and in which every element is strictly greater than its preceding element.

Task:
Return the length of the longest strictly increasing subsequence.

Example 1:

• Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
• Output: 4
• Explanation:
  One longest increasing subsequence is [2, 3, 7, 101], so the answer is 4.

Example 2:

• Input: nums = [0, 1, 0, 3, 2, 3]
• Output: 4
• Explanation:
  The longest increasing subsequence is [0, 1, 2, 3] (there can be multiple valid answers).

Example 3:

• Input: nums = [7, 7, 7, 7, 7, 7, 7]
• Output: 1
• Explanation:
  Every element is the same, so the longest strictly increasing subsequence has length 1.

Constraints:

• The length of nums is at least 1.
• The elements of nums can be any integers.
• The subsequence does not need to be contiguous.

Hints

1. Dynamic Programming (DP) Insight:
   Think about each position in the array as a potential ending of an increasing subsequence. Ask yourself: “What is the longest increasing subsequence that ends here?”
   Then, for each element, check all previous elements to see if you can extend an existing subsequence.

2. Binary Search Optimization:
   Once you have a DP solution, consider if you can optimize it. A well-known method uses a temporary array (often called tails) where each element represents the smallest tail value of an increasing subsequence of a given length. By using binary search to update this array, you can reduce the complexity to O(n log n).

Approaches to Solve the Problem

Approach 1: Dynamic Programming (O(n²) Time Complexity)

Idea:

• Create an array dp where dp[i] is the length of the longest increasing subsequence ending at index i.
• Initialize each value of dp to 1 (every element is an increasing subsequence of length 1 by itself).
• For each element at index i, loop through indices 0 to i-1:
  • If nums[j] < nums[i], update dp[i] as max(dp[i], dp[j] + 1).
• The final answer is the maximum value in the dp array.

Step-by-Step Walkthrough:

• Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]
  • Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1].
  • For index 1 (value 9): 10 is not less than 9, so dp[1] remains 1.
  • For index 2 (value 2): neither 10 nor 9 is less than 2, so dp[2] remains 1.
  • For index 3 (value 5): check previous elements; 2 is less than 5, so update dp[3] = dp[2] + 1 = 2.
  • Continue this process; eventually, you find that the longest subsequence ending at index 6 (value 101) has length 4.

Complexity:

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

Approach 2: Optimized Solution Using Binary Search (O(n log n) Time Complexity)

Idea:

• Maintain an array tails where tails[i] is the smallest possible tail value for an increasing subsequence of length i + 1.
• For each number in nums, use binary search on the tails array to determine where it can be placed (or replace an existing value) to keep tails as small as possible.
• The size of tails at the end will be the length of the longest increasing subsequence.

Step-by-Step Walkthrough:

• Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]
  1. Start with an empty tails.
  2. Process 10 → tails = [10].
  3. Process 9 → binary search finds index 0; replace 10 with 9 → tails = [9].
  4. Process 2 → replace 9 with 2 → tails = [2].
  5. Process 5 → 5 is greater than 2; append → tails = [2, 5].
  6. Process 3 → binary search finds index 1; replace 5 with 3 → tails = [2, 3].
  7. Process 7 → append → tails = [2, 3, 7].
  8. Process 101 → append → tails = [2, 3, 7, 101].
  9. Process 18 → binary search finds index 3; replace 101 with 18 → tails = [2, 3, 7, 18].
• The length of tails is 4, which is the answer.

Complexity:

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

Code Implementation

Python Code