Longest Increasing Subsequence

return length of longest increasing subsequence

Longest Increasing Subsequence

Problem

You are given an integer array nums. Return the length of the longest strictly increasing subsequence.

A subsequence is made by deleting some elements (or none) from the array. The order of the remaining elements does not change. "Strictly increasing" means each number must be bigger than the one before it.

Examples

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4

• The longest increasing subsequence is [2,3,7,101].
• Its 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

• All numbers are the same, so we cannot make a strictly increasing sequence.
• We can only pick one number, so the answer is 1.

Constraints

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Main Idea

At each index, we decide: should I pick this number or not? To decide this, we need to remember the previous picked number. So we track two things:

• index: the current position in the array.
• prev: the index of the last number we picked. We use -1 when we have not picked anything yet.

On each step, we have two choices:

• Not pick: Skip the current number. We move to index + 1 and prev stays the same.
• Pick: We can pick the current number only if it is bigger than the previous picked number (or if we have not picked anything yet). We add 1 to the length. Then we move to index + 1 and prev becomes index.

We take the maximum of both choices.

Base Case

• If index === n, the array is finished. Return 0.

Example: How It Works

Let us take nums = [2, 5, 3, 7].

• Pick 2. Then pick 5. Then skip 3 (it is smaller than 5). Then pick 7. Length = 3.
• Pick 2. Then skip 5. Then pick 3. Then pick 7. Length = 3.
• Skip 2. Pick 5. Then pick 7. Length = 2.

The best length is 3.

Solution 1: Plain Recursion

This is the simple version. It tries all choices and has no saving of answers. So it solves the same problem again and again.

var lengthOfLIS = function (nums) {
    let n = nums.length;

    function recurr(index, prev) {
        // array is finished
        if (index == n) {
            return 0;
        }

        // skip the current number
        let notPick = recurr(index + 1, prev);

        // pick the current number, only if it is bigger than the previous one
        let pick = -Infinity;
        if (prev == -1 || nums[index] > nums[prev]) {
            pick = 1 + recurr(index + 1, index);
        }

        return Math.max(pick, notPick);
    }

    return recurr(0, -1);
};

Complexity

• Time Complexity: O(2^n)
  • On each number, we make two choices: pick or not pick.
  • Many sub-problems are solved again and again.
• Space Complexity: O(n)
  • There is no extra table.
  • The recursion stack can go as deep as n.

Solution 2: Memoization (Top-Down)

Now we save each answer in a table, so we never solve the same problem twice.

The value of prev can be -1, but an array cannot have a negative index. So we shift prev by 1 and use prev + 1 as the column index.

var lengthOfLIS = function (nums) {
    let n = nums.length;
    let dp = Array.from({ length: n + 1 }, () => Array(n + 1));

    function recurr(index, prev) {
        // array is finished
        if (index == n) {
            return 0;
        }

        // answer is already saved
        if (dp[index][prev + 1] !== undefined) {
            return dp[index][prev + 1];
        }

        // skip the current number
        let notPick = recurr(index + 1, prev);

        // pick the current number, only if it is bigger than the previous one
        let pick = -Infinity;
        if (prev == -1 || nums[index] > nums[prev]) {
            pick = 1 + recurr(index + 1, index);
        }

        return (dp[index][prev + 1] = Math.max(pick, notPick));
    }

    return recurr(0, -1);
};

Complexity

• Time Complexity: O(n * n), which is O(n²)
  • There are about n * n different states, and each state is solved only once.
• Space Complexity: O(n²)
  • The dp table has (n + 1) * (n + 1) cells.
  • The recursion stack also uses O(n) extra space.

Solution 3: Tabulation (Bottom-Up)

In this method, we do not use recursion. We start from the last index and move to the first index.

Here, dp[index][prev_index + 1] means: the length of the longest increasing subsequence from index to the end, when the previous picked index is prev_index.

function solve(arr, n) {
    // Create a 2D DP array of size (n + 1) x (n + 1)
    let dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

    // Go backwards from n - 1 to 0
    for (let index = n - 1; index >= 0; index--) {
        // prev_index goes from index - 1 down to -1
        for (let prev_index = index - 1; prev_index >= -1; prev_index--) {
            // Option 1: Do not take
            let len = 0 + dp[index + 1][prev_index + 1];

            // Option 2: Take (if the number is bigger)
            if (prev_index === -1 || arr[index] > arr[prev_index]) {
                len = Math.max(len, 1 + dp[index + 1][index + 1]);
            }

            dp[index][prev_index + 1] = len;
        }
    }

    // Start at index 0 with prev_index = -1 (shifted by 1 becomes 0)
    return dp[0][0];
}

Complexity

• Time Complexity: O(n²)
  • We use two loops, one inside the other.
  • Each cell is filled in constant time.
• Space Complexity: O(n²)
  • The dp table has (n + 1) * (n + 1) cells.
  • There is no recursion stack.

Solution 4: Tabulation with a 1D Array

There is a simpler way. We use only one array called dp.

Here, dp[i] means: the length of the longest increasing subsequence that ends at index i.

• At the start, every dp[i] = 1, because each number alone is a sequence of length 1.
• For each i, we check all earlier numbers prev.
• If arr[prev] < arr[i], we can add arr[i] after arr[prev]. So dp[i] = max(dp[i], 1 + dp[prev]).
• The final answer is the biggest value in dp.

function lis(arr, n) {
    let dp = new Array(n).fill(1);
    let maxLen = 1;

    for (let i = 0; i < n; i++) {
        for (let prev = 0; prev < i; prev++) {
            if (arr[prev] < arr[i]) {
                dp[i] = Math.max(dp[i], 1 + dp[prev]);
            }
        }

        // keep the biggest length
        maxLen = Math.max(maxLen, dp[i]);
    }

    return maxLen;
}

Complexity

• Time Complexity: O(n²)
  • We use two loops, one inside the other.
• Space Complexity: O(n)
  • We use only one dp array of size n.

Solution 5: Print the LIS (Trace Back)

Sometimes we need the actual subsequence, not only its length. For this, we add one more array called hash.

• dp[i] is the length of the LIS that ends at index i.
• hash[i] stores the index of the previous number in that LIS.
• At the start, hash[i] = i. It means the number has no previous number.
• We also remember lastIndex, which is the index where the longest LIS ends.

After we fill the arrays, we start from lastIndex and follow hash backwards. We stop when hash[index] === index. At the end, we reverse the result, because we collected the numbers from last to first.

function printLIS(arr, n) {
    let dp = new Array(n).fill(1);
    let hash = new Array(n).fill(0);

    // each number points to itself at the start
    for (let i = 0; i < n; i++) {
        hash[i] = i;
    }

    let lastIndex = 0;
    let maxLen = 1;

    // find the LIS length and save the previous index
    for (let i = 0; i < n; i++) {
        for (let prev = 0; prev < i; prev++) {
            if (arr[prev] < arr[i] && 1 + dp[prev] > dp[i]) {
                dp[i] = 1 + dp[prev];
                hash[i] = prev;
            }
        }

        // remember where the longest subsequence ends
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            lastIndex = i;
        }
    }

    // build the LIS using the hash array
    let lis = [];
    lis.push(arr[lastIndex]);

    while (hash[lastIndex] !== lastIndex) {
        lastIndex = hash[lastIndex];
        lis.push(arr[lastIndex]);
    }

    // reverse to get the correct order
    return lis.reverse();
}

Example Run

For arr = [10, 9, 2, 5, 3, 7, 101, 18]:

• The LIS ends at index 6 (value 101).
• We follow hash backwards: 101 -> 7 -> 5 -> 2.
• After reversing, we get [2, 5, 7, 101].

This is a different answer from [2, 3, 7, 101], but it is also correct. Both have length 4, and a problem can have more than one valid LIS.

Complexity

• Time Complexity: O(n²)
  • We use two loops, one inside the other.
  • Building the result takes only O(n).
• Space Complexity: O(n)
  • We use the dp array, the hash array and the result array. Each has size at most n.

Solution 6: Binary Search (Optimal)

This is the fastest solution. It runs in O(n log n) time.

Intuition

In the earlier solutions, we asked: "what is the longest sequence that ends at this number?" Here, we ask a different question:

"For each length, what is the smallest number that can end an increasing subsequence of that length?"

We keep these numbers in an array called temp.

• temp[0] is the smallest ending number of any increasing subsequence of length 1.
• temp[1] is the smallest ending number of any increasing subsequence of length 2.
• temp[2] is the smallest ending number of any increasing subsequence of length 3.
• And so on.

Why do we want the smallest ending number? Because a smaller ending number gives us more chances to add bigger numbers after it later.

Because of this rule, the temp array is always sorted (from small to big). This is why we can use binary search on it.

Steps

For each number arr[i], we do this:

• Case 1: arr[i] is bigger than the last number in temp.
  • We can add it to the end of the longest sequence. So we push it into temp. The LIS becomes longer by 1.
• Case 2: arr[i] is not bigger than the last number in temp.
  • It cannot make the sequence longer. But it can make an ending number smaller.
  • We use binary search to find the first number in temp that is greater than or equal to arr[i].
  • We replace that number with arr[i].

At the end, the length of temp is the length of the LIS.

Important: The temp array is not always the real LIS. It only helps us find the correct length. Its values may come from different subsequences.

Why >= and not >?

The problem needs a strictly increasing sequence. So equal numbers are not allowed in a sequence.

• If temp already has a number equal to arr[i], we find that same number and replace it with itself.
• So the length does not grow by mistake.
• This is why [7,7,7,7,7,7,7] gives the answer 1.

How the Binary Search Works

• left = 0 and right = temp.length - 1.
• We find mid.
  • If temp[mid] >= arr[i], the answer can be mid or something on the left. So we set right = mid.
  • Otherwise, the answer is on the right. So we set left = mid + 1.
• When left === right, we found the first position where temp[left] >= arr[i].
• We know such a position exists, because arr[i] is not bigger than the last number in temp.

Code

var lengthOfLIS = function (arr) {
    if (arr.length === 0) return 0;

    // temp[k] is the smallest ending number of an
    // increasing subsequence of length k + 1
    let temp = [arr[0]];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > temp[temp.length - 1]) {
            // bigger than all numbers, so the LIS grows
            temp.push(arr[i]);
        } else {
            // find the first number in temp that is >= arr[i]
            let left = 0;
            let right = temp.length - 1;

            while (left < right) {
                let mid = Math.floor((left + right) / 2);

                if (temp[mid] >= arr[i]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            // replace it with a smaller (or equal) number
            temp[left] = arr[i];
        }
    }

    // the length of temp is the length of the LIS
    return temp.length;
};

Example Run

Let us take arr = [10, 9, 2, 5, 3, 7, 101, 18].

The length of temp is 4. So the answer is 4.

Why temp Is Not the Real LIS

Let us take arr = [3, 4, 1].

• 3 gives temp = [3].
• 4 gives temp = [3, 4].
• 1 replaces 3, so temp = [1, 4].

The array [1, 4] is not a real subsequence of arr, because 1 comes after 4. But the length 2 is still correct. This is because temp stores the smallest possible endings, not the real sequence.

If you need the real sequence, use Solution 5.

Complexity

• Time Complexity: O(n log n)
  • We go through the array once. This takes O(n).
  • For each number, we do one binary search on temp. This takes O(log n).
• Space Complexity: O(n)
  • The temp array can grow up to size n, when the whole array is increasing.

Comparison

Summary

• This is a dynamic programming problem.
• In the 2D approach, we track the current index and the previous picked index. On each step, we pick or not pick.
• We can pick a number only if it is bigger than the previous picked number.
• We shift prev by 1 so we can use -1 as an index.
• The 1D approach is simpler and uses less space. Here, dp[i] is the LIS length ending at i.
• To print the LIS, we store the previous index in a hash array and trace back from the last index.
• The binary search approach keeps the smallest ending number for each length in a sorted array temp.
  • If the number is bigger than the last one, we push it.
  • Otherwise, we replace the first number that is greater than or equal to it.
  • The length of temp is the answer, but temp itself may not be a real LIS.
• Binary search is the fastest approach, with O(n log n) time and O(n) space.
• With n up to 2500, even an O(n²) solution is fast enough. But binary search is the best choice for bigger inputs.