Longest Increasing Subsequence (Leetcode 300)

• Leetcode 300
• Video Walkthrough

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

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Examples

• 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

Solution

const lengthOfLIS = (nums) => {
  // keep track of each number checked and how many previous sequential numbers
  // nums ->        [0, 1, 0, 3, 2, 3]
  // resultsArr ->  [1, 1, 1, 1, 1, 1]  prefil it with 1's since that's the min sequence including itself
  // resultsArr ->  [1, 2, 1, 3, 3, 4]  -> 0 has max sequence of 1, 1 is greater than prev 0 so it has max of 2...
  const resultsArr = Array(nums.length).fill(1);

  for (let i = 0; i < nums.length; i++) {
    for (let x = i - 1; x >= 0; x--) {
      if (nums[x] < nums[i]) {
        if (resultsArr[x] + 1 > resultsArr[i]) {
          resultsArr[i] = resultsArr[x] + 1;
        }
      }
    }
  }
  return Math.max(...resultsArr);
};

const nums1 = [10, 9, 2, 5, 3, 7, 101, 18]; // 4
const nums2 = [0, 1, 0, 3, 2, 3]; // 4
const nums3 = [7, 7, 7, 7, 7, 7, 7]; // 1

console.log("nums1", lengthOfLIS(nums1));
console.log("nums2", lengthOfLIS(nums2));
console.log("nums3", lengthOfLIS(nums3));

Big O -> O(n^2)