Problem Description

Given an integer array nums, you need to find the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is the array, then [3,6,7] is a subsequence (we deleted the element 2), but [6,3,7] is not a valid subsequence (the order was changed).

A strictly increasing subsequence means each element must be strictly greater than the previous one (not equal to).

For example:

• If nums = [10,9,2,5,3,7,101,18], the longest strictly increasing subsequence is [2,3,7,18] or [2,3,7,101], both with length 4.
• If nums = [0,1,0,3,2,3], the longest strictly increasing subsequence could be [0,1,2,3] with length 4.

The solution uses dynamic programming where f[i] represents the length of the longest increasing subsequence ending at index i. For each position i, it checks all previous positions j where nums[j] < nums[i], and updates f[i] to be the maximum of its current value or f[j] + 1. The final answer is the maximum value in the f array.

Intuition

Think about building the longest increasing subsequence step by step. At each position in the array, we need to make a decision: what's the longest increasing subsequence that can end at this position?

The key insight is that for any element at position i, we can extend any increasing subsequence that ends at a previous position j (where j < i) as long as nums[j] < nums[i]. This is because if we have an increasing subsequence ending at j, and nums[i] is greater than nums[j], we can simply append nums[i] to that subsequence to create a longer one.

For example, if we have nums = [2, 5, 3, 7]:

• At position 0 (value 2): The longest subsequence ending here has length 1 (just [2])
• At position 1 (value 5): We can extend the subsequence ending at position 0 since 2 < 5, giving us length 2 ([2, 5])
• At position 2 (value 3): We can extend the subsequence from position 0 since 2 < 3, giving us length 2 ([2, 3])
• At position 3 (value 7): We can extend subsequences from positions 0, 1, or 2. The best choice is extending from position 1 or 2, both giving length 3

This naturally leads to a dynamic programming approach where we track f[i] = the length of the longest increasing subsequence ending at position i. For each position, we look back at all previous positions, check if we can extend their subsequences (by comparing values), and take the best option. The overall answer is the maximum length found across all positions.

Solution Approach

The solution uses dynamic programming with a 1D array to track the longest increasing subsequence ending at each position.

Data Structure:

• Create an array f of size n where f[i] represents the length of the longest increasing subsequence ending at index i
• Initialize all values in f to 1, since each element by itself forms a subsequence of length 1

Algorithm Steps:

1. Initialization: Set f = [1] * n because the minimum length of any subsequence ending at any position is 1 (the element itself).

2. Fill the DP array: For each position i from 1 to n-1:

   • Check all previous positions j from 0 to i-1
   • If nums[j] < nums[i], it means we can extend the subsequence ending at j by adding nums[i]
   • Update f[i] = max(f[i], f[j] + 1) to keep the maximum length possible

3. Return the result: The answer is max(f), which gives us the maximum length among all possible ending positions.

Time Complexity: O(n²) where n is the length of the array, as we have two nested loops.

Space Complexity: O(n) for the DP array f.

Example walkthrough with nums = [10, 9, 2, 5, 3, 7]:

• Initial: f = [1, 1, 1, 1, 1, 1]
• At i=1: 9 is not greater than 10, so f[1] stays 1
• At i=2: 2 is not greater than 10 or 9, so f[2] stays 1
• At i=3: 5 > 2, so f[3] = f[2] + 1 = 2
• At i=4: 3 > 2, so f[4] = f[2] + 1 = 2
• At i=5: 7 > 2, 5, 3, best is from position 3 or 4, so f[5] = 3
• Final: f = [1, 1, 1, 2, 2, 3], return 3

Example Walkthrough

Let's walk through a small example with nums = [4, 2, 5, 3, 7] to illustrate the solution approach.

Step 1: Initialize DP array

• f = [1, 1, 1, 1, 1] (each element forms a subsequence of length 1)

Step 2: Process each position

Position i=1 (value=2):

• Check j=0: nums[0]=4 > nums[1]=2, cannot extend
• f[1] remains 1

Position i=2 (value=5):

• Check j=0: nums[0]=4 < nums[2]=5, can extend! f[2] = max(1, f[0]+1) = 2
• Check j=1: nums[1]=2 < nums[2]=5, can extend! f[2] = max(2, f[1]+1) = 2
• f[2] = 2 (subsequence could be [4,5] or [2,5])

Position i=3 (value=3):

• Check j=0: nums[0]=4 > nums[3]=3, cannot extend
• Check j=1: nums[1]=2 < nums[3]=3, can extend! f[3] = max(1, f[1]+1) = 2
• Check j=2: nums[2]=5 > nums[3]=3, cannot extend
• f[3] = 2 (subsequence is [2,3])

Position i=4 (value=7):

• Check j=0: nums[0]=4 < nums[4]=7, can extend! f[4] = max(1, f[0]+1) = 2
• Check j=1: nums[1]=2 < nums[4]=7, can extend! f[4] = max(2, f[1]+1) = 2
• Check j=2: nums[2]=5 < nums[4]=7, can extend! f[4] = max(2, f[2]+1) = 3
• Check j=3: nums[3]=3 < nums[4]=7, can extend! f[4] = max(3, f[3]+1) = 3
• f[4] = 3 (best subsequence is [2,5,7] or [2,3,7])

Step 3: Find maximum

• Final DP array: f = [1, 1, 2, 2, 3]
• Return max(f) = 3

The longest increasing subsequence has length 3, such as [2, 5, 7] or [2, 3, 7].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses two nested loops:

• The outer loop iterates from index 1 to n-1, executing n-1 iterations
• For each iteration i of the outer loop, the inner loop iterates from index 0 to i-1, executing i iterations
• The total number of operations is: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2
• Therefore, the time complexity is O(n²)

Space Complexity: O(n)

The algorithm uses:

• An array f of size n to store the length of the longest increasing subsequence ending at each index, requiring O(n) space
• A few constant variables (n, i, j) which require O(1) space
• Therefore, the overall space complexity is O(n)

Common Pitfalls

1. Empty Array Handling

The current implementation fails when the input array is empty. Calling max(dp) on an empty list will raise a ValueError.

Problem Example:

nums = []
# This will crash with: ValueError: max() arg is an empty sequence

Solution: Add an edge case check at the beginning:

def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums:
        return 0
  
    n = len(nums)
    dp = [1] * n
    # ... rest of the code

2. Confusion Between "Strictly Increasing" vs "Non-Decreasing"

A common mistake is using nums[j] <= nums[i] instead of nums[j] < nums[i], which would allow equal elements in the subsequence.

Problem Example:

nums = [1, 3, 3, 4]
# Wrong: Using <= would give length 4, treating [1,3,3,4] as valid
# Correct: Using < gives length 3, with subsequence [1,3,4]

Solution: Always use strict inequality (<) for strictly increasing subsequences:

if nums[j] < nums[i]:  # NOT nums[j] <= nums[i]
    dp[i] = max(dp[i], dp[j] + 1)

3. Performance Issue with Large Arrays

The O(n²) solution becomes inefficient for large arrays (n > 10⁴). This can cause time limit exceeded errors.

Problem Example:

nums = list(range(10000))  # Already sorted array with 10,000 elements
# This will perform 50 million comparisons

Solution: Use binary search optimization with an auxiliary array for O(n log n) complexity:

def lengthOfLIS(self, nums: List[int]) -> int:
    from bisect import bisect_left
  
    if not nums:
        return 0
  
    # tails[i] stores the smallest tail element for LIS of length i+1
    tails = []
  
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
  
    return len(tails)

4. Incorrect Initialization Value

Some might initialize dp with 0 instead of 1, forgetting that each element forms a subsequence of length 1 by itself.

Problem Example:

dp = [0] * n  # Wrong initialization
# This would give incorrect results as it assumes elements have length 0

Solution: Always initialize with 1:

dp = [1] * n  # Correct: each element is a subsequence of length 1