LeetCode 300 Longest Increasing Subsequence

Overview

I have been bashing my head to understand how to get the optimum solution for this question in LeetCode:
https://leetcode.com/problems/longest-increasing-subsequence/

The problem statement is this:

Given an unsorted array of integers, find the length of longest increasing subsequence.

Here's a brief explanation of the question:

Example 1
Let's say you have an input array of the following.
Input: [10, 9, 2, 5, 3, 7, 101, 18]

The longest increasing sub array would be:
[2, 3, 7, 101] or
[2, 3, 7, 18]

The length of either of them would be 4, so the answer is 4.

Example 2
Let's take a look at another example:
Input: [1, 2, 6, 4, 5]

The answer is also 4, but in this case, we only have 1 possible subarray:
[1, 2, 4, 5]

---

First Intuition: O(n²) with Dynamic Programming

The first intuition to solve this question is a solution with O(n²) performance.

The solution described here: https://leetcode.com/problems/longest-increasing-subsequence/solution/
isn't too hard to understand. It is the Approach 3, it even comes with a nice animation, so I will not be discussing this here.

O(n log n) Solution with Dynamic Programming + Binary Search

Even after reading the Solution I couldn't grasp it at first. After running the code in an IDE and visualizing it, I finally understand how it works.

So the official Solution as Approach 4 looks like this:

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

Instead of explaining the solution inside out, which is to explain what the code is doing. I find it easier to explain what we are trying to achieve first, and you will eventually understand what the code is doing.

This solution requires us to make an array called dp. The definition of this arrray explain in my words would be:

The position of the array represents the length of the longest increasing subsequence.
The value of the array represents the smallest value that is needed to be surpassed,
in order to make the length of longest increasing subsequence longer.

This sentence itself might not make much sense, so let's modify the code in order to see how the array is made up.

Modify the solution to make it runnable with test cases:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] nums = {10, 9, 2, 5, 6, 3, 4, 7, 101, 18};
        int[] nums = {1, 2, 6, 4, 5};

        int answer = solution.lengthOfLIS(nums);
        System.out.println("answer = " + answer);

    }
}

class Solution {
    int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            // System.out.println("found = " + i);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
            printNums(dp);
        }
        return len;
    }

    private void printNums(int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length - 1; i++) {
            sb.append(array[i]);
            sb.append(", ");
        }
        sb.append(array[array.length - 1]);

        System.out.println(sb.toString());
        System.out.println("-----");
    }
}

I added printNums() so that we can see how dp is built up in each steps.

The test input I used is Input = [1, 2, 6, 4, 5].

Running the code will produce the following result:

1, 0, 0, 0, 0
-----
1, 2, 0, 0, 0
-----
1, 2, 6, 0, 0
-----
1, 2, 4, 0, 0
-----
1, 2, 4, 5, 0
-----
answer = 4

Let's walk through the result to understand the meaning behind it.

---

when num = 1

1, 0, 0, 0, 0
-----

Explanation
Since '1' is occupying index 0, it means:

1. the longest string we can now form is now, length = (index + 1) = 1
2. the minimum value needed to surpass in order to make the string longer than 1, is 1

---

when num = 2

1, 2, 0, 0, 0
-----

Explanation
Since '2' is occupying index 1, it means:

1. the longest string we can now form is now, length = (index + 1) = 2
2. the minimum value needed to surpass in order to make the string longer than 2, is 2

---

when num = 6

1, 2, 6, 0, 0
-----

Explanation
Since '6' is occupying index 2, it means:

1. the longest string we can now form is now, length = (index + 1) = 3
2. the minimum value needed to surpass in order to make the string longer than 3, is 6.

---

when num = 4

1, 2, 4, 0, 0
-----

Explanation
Since '4' is occupying index 2, it means:

1. the longest string we can now form is now, length = (index + 1) = 3
2. the minimum value needed to surpass in order to make the string longer than 3, is 4.

Remarks
This is where it gets interesting. Notice that 4 is replacing 6, that is because it's [1,2,6] and [1,2,4] both are able to form an increasing string with length 3. However, it would be better to choose [1,2,4] over [1,2,6] since it is easier to form a longer string with the former. So we can remove 6 and replace it with 4.

---

when num = 5

1, 2, 4, 5, 0
-----

Explanation
Since '5' is occupying index 3, it means:

1. the longest string we can now form is now, length = (index + 1) = 4
2. the minimum value needed to surpass in order to make the string longer than 4, is 5.

---

That's the end of the input array.

So the largest longest increasing array is 4!

This is achieved by Arrays.binarySearch(array, start, end, target) (doc).

In every loop, the num is placed into the correct placement in dp.

That's it!

Hope it helps anyone working on this question. 😃