Longest Increasing Subsequence

---

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
• -10^4 <= nums[i] <= 10^4

---

Try this Problem on your own or check similar problems:

1. Number of Longest Increasing Subsequence
2. Maximum Length of Pair Chain
3. Increasing Triplet Subsequence
4. Russian Doll Envelopes

Solution:

Java

public int lengthOfLIS(int[] nums) {
    List<Integer> piles = new ArrayList<>();

    for(int num : nums){
        int index = ~Collections.binarySearch(piles, num);

        if(index >= 0){
          if(index == piles.size()){
            piles.add(num);
          }else{
            piles.set(index, num);
          }
        }
    }
    return piles.size();
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const piles = [];

  for (const num of nums) {
    const index = binarySearch(piles, num);

    if (index === piles.length) {
      piles.push(num);
    } else {
      piles[index] = num;
    }
  }

  return piles.length;
};

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }

  return left;
}

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
      piles = []

      for num in nums:
          index = bisect.bisect_left(piles, num)

          if index == len(piles):
              piles.append(num)
          else:
              piles[index] = num

      return len(piles)

C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
      vector<int> piles;

      for (const int num : nums) {
          const int index = lower_bound(piles.begin(), piles.end(), num) - piles.begin();

          if (index == piles.size()) {
              piles.push_back(num);
          } else {
              piles[index] = num;
          }
      }

      return piles.size();
    }
};

---

Time/Space Complexity:

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

---

Explanation:

The brute force DP solution is O(n^2), for each number in the input array we iterate over all numbers that come before it and see if they can form a strictly increasing sequence (numbers before the current element strictly smaller than it), while keeping the dp array of max sequence lengths for each of the elements (e.g. if a number can form a sequence with the numbers before it will lead to dp[i] = dp[j] + 1 where j < i, in other words we're extending our sequence). But can we do better? Yes we can implement a O(n logn) algorithm. Let me first go through the code and then explain the logic behind it:

• for each number in the input array we're checking where we can place it in the piles list using ~Collections.binarySearch(piles, num);
• Collections.binarySearch will either return positive index (element found), or it will return (-insertPoint-1) (e.g. [1,2,3,4], if we want number 5, it will return -5)
• ~ will give us positive and 0-indexed index, in the example above we would return -(-5)-1 = 4 which is exactly the right index we can place 5
• so, if the index is negative after all these transformations, we have found duplicate (element is already there in piles list), so we can just skip it
• otherwise, if the placement index is larger than the current list size, we extend it with that element
• or if the index is in range 0..size-1 we override the current element at the position
• finally we return the piles.size()

The core of the algorithm is based on Patience solitaire game or Patience sorting, in essence what we do is that for each element we place it at leftmost position (or pile) and we keep doing that until we're out of cards, the total number of piles is our longest increasing sequence. For each element we can either extend our sequence (or add an extra pile) or we can find the right pile (leftmost pile with top card larger than the current element/card).