# 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:

- the longest string we can now form is now, length = (index + 1) = 1
- 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:

- the longest string we can now form is now, length = (index + 1) = 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:

- the longest string we can now form is now, length = (index + 1) = 3
- 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:

- the longest string we can now form is now, length = (index + 1) = 3
- 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:

- the longest string we can now form is now, length = (index + 1) = 4
- 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. 😃

**Enjoyed the post?**

Clap to support the author, help others find it, and make your opinion count.