{x}
blog image

Longest Increasing Subsequence

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

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution Explanation:

This problem asks for the length of the longest strictly increasing subsequence in a given integer array. There are two main approaches to solving this: dynamic programming and binary search.

Solution 1: Dynamic Programming

This approach uses dynamic programming to build up a solution. For each element in the input array nums, we maintain f[i], representing the length of the longest increasing subsequence ending at index i.

Algorithm:

  1. Initialization: Create an array f of the same size as nums, and initialize each element to 1 (since each element itself forms a subsequence of length 1).

  2. Iteration: Iterate through the nums array. For each element nums[i], iterate through the elements before it (nums[j] where j < i). If nums[j] < nums[i], it means we can extend the subsequence ending at j to include nums[i]. Update f[i] to be the maximum of its current value and f[j] + 1.

  3. Result: After iterating through all elements, the maximum value in the f array represents the length of the longest increasing subsequence.

Time Complexity: O(N^2), where N is the length of the input array. This is due to the nested loops in the iteration step.

Space Complexity: O(N) to store the f array.

Solution 2: Binary Search with Binary Indexed Tree (Fenwick Tree)

This approach leverages binary search and a Binary Indexed Tree (Fenwick Tree) to achieve O(N log N) time complexity.

Algorithm:

  1. Find Unique Elements: Create a sorted array s containing only the unique elements from nums. This will help us map the values in nums to indices in a binary indexed tree.

  2. Binary Indexed Tree: Create a Binary Indexed Tree (tree) with the size of the unique elements.

  3. Iteration: Iterate through nums. For each element x:

    • Use binary search to find the index of x in the sorted array s (or the index of the smallest element greater than or equal to x).
    • Query the Binary Indexed Tree to find the maximum length of an increasing subsequence ending at an index less than the index of x in s. This query is performed using a Fenwick Tree for efficiency.
    • Increment this length to find the length of the increasing subsequence ending at x and update the Binary Indexed Tree accordingly.

  4. Result: After processing all elements in nums, query the Binary Indexed Tree for the maximum length across all indices. This is the length of the longest increasing subsequence.

Time Complexity: O(N log N). Binary search takes O(log N) time for each element, and the Binary Indexed Tree operations (update and query) also take O(log N) time.

Space Complexity: O(N) to store the sorted unique array s and the Binary Indexed Tree.

Note: The Binary Indexed Tree is used to efficiently find the maximum value in a range, which is crucial for optimizing the time complexity of this algorithm. Without the BIT, the time complexity would still be O(N^2)

The provided code examples demonstrate both approaches in several programming languages. Choose the approach that best fits your needs and understanding; the dynamic programming solution is simpler to understand, while the binary search solution is more efficient for large input arrays.