Longest Increasing Subsequence

Question

Find the length of the longest strictly increasing subsequence. Explore O(n^2) DP and O(n log n) binary search approaches. A common Google DP question.

Codemia · Accepted Answer

The Longest Increasing Subsequence (LIS) problem can be approached using the dynamic programming (DP) technique due to its optimal substructure property. The key observation is that for any element in the array, we can determine the longest subsequence ending at that element by examining all previous elements. This leads us to consider pairs of elements, where we can build the solution incrementally. The problem also allows for optimization using binary search, which is especially useful for reducing the time complexity from O(n^2) to O(n log n) by leveraging a technique similar to patience sorting.

We will implement two solutions:

1. **O(n^2) DP Approach**:
   - Create a DP array where `dp[i]` represents the length of the longest increasing subsequence that ends with the element at index `i`.
   - Initialize each `dp[i]` to 1 since the minimum length of an increasing subsequence ending at any element is 1 (the element itself).
   - For each element at index `i`, iterate through all previous elements (from 0 to `i-1`). If the current element is greater than a previous element, we can extend the increasing subsequence: `dp[i] = max(dp[i], dp[j] + 1)` where `j` < `i`.

**Example**: For the input array `[10, 9, 2, 5, 3, 7, 101, 18]`, the `dp` array evolves as follows:
   - Start with [1, 1, 1, 1, 1, 1, 1, 1]
   - After processing `2`, the `dp` becomes [1, 1, 1, 2, 1, 1, 1, 1]

2. **O(n log n) Approach**:
   - Maintain a list `tails` that will store the smallest tail for all increasing subsequences of different lengths. The length of this list will ultimately give the length of the longest increasing subsequence.
   - For each number, use binary search to determine its position in the `tails` list. If it is larger than all elements in `tails`, append it. If it can replace an existing element, replace it to maintain the smallest possible tail.
   
   **Example**: For the input `[10, 9, 2, 5, 3, 7, 101, 18]`, the `tails` list evolves as follows:
   - Start with []
   - Add `2`, `3`, `5`, `7`, and `101` sequentially, resulting in `tails = [2, 3, 5, 7, 101]`.

Here is the Python implementation for both approaches:

**O(n^2) DP Solution**:
```python
def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
```

**O(n log n) Optimized Solution**:
```python
import bisect

def lengthOfLIS(nums):
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)
```

1. **Time Complexity**:
   - The O(n^2) DP solution has a time complexity of O(n^2) due to the nested loops iterating over the array.
   - The O(n log n) approach has a time complexity of O(n log n) because each insertion operation into the `tails` list requires a binary search, which takes O(log n), and this is performed for each of the n elements.

2. **Space Complexity**:
   - Both solutions have a space complexity of O(n). The DP solution uses an extra array of size n, while the optimized solution uses a list that can grow up to n in the worst case.

1. **Empty Array**: If the input array is empty, the expected output should be 0.
   
2. **All Equal Elements**: For an input like `[5, 5, 5, 5]`, the output should be 1, as any single element can be considered the longest increasing subsequence.
   
3. **All Decreasing Elements**: For an input like `[9, 8, 7, 6]`, the output should again be 1, since the longest increasing subsequence can only consist of any single element.
   
4. **Increasing and Decreasing Mix**: For an input like `[1, 3, 6, 7, 9, 4, 10, 5, 6]`, the expected output is 6, corresponding to the subsequence `[1, 3, 6, 7, 9, 10]`.

Longest Increasing Subsequence

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string