[LeetCode][300. Longest Increasing Subsequence] 3 Approaches: Backtrack, DP, Binary Search

By Long Luo

This article is the solution 3 Approaches: Backtrack, DP, Binary Search of Problem 300. Longest Increasing Subsequence.

Here shows 3 Approaches to slove this problem: Backtrack, DP, Binary Search.

Backtrack

The Brute Force approach, there are \(2^n\) subsequences, use Backtrack to find the answer.

TLE!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
int minCount = Integer.MAX_VALUE;

public int coinChange(int[] coins, int amount) {
if (amount <= 0) {
return 0;
}

minCount = Integer.MAX_VALUE;
dfs(coins, amount, 0);
return minCount == Integer.MAX_VALUE ? -1 : minCount;
}

private int dfs(int[] coins, int remain, int count) {
if (remain < 0) {
return -1;
}

if (remain == 0) {
minCount = Math.min(minCount, count);
return count;
}

for (int x : coins) {
dfs(coins, remain - x, count + 1);
}

return -1;
}
}

Analysis

  • Time Complexity: \(O(2^n)\)
  • Space Complexity: \(O(n)\)

DP

The equation:

\(dp[i] = \textit{max}(dp[j]) + 1, 0 \leq j < i and \textit{nums}[j] < \textit{nums}[i]\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len <= 1) {
return len;
}

int max = 1;
int[] dp = new int[len];
Arrays.fill(dp, 1);

for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}

max = Math.max(max, dp[i]);
}

return max;
}
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(n)\)

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len <= 1) {
return len;
}

int[] tail = new int[len];
tail[0] = nums[0];
int maxLen = 1;

for (int i = 1; i < len; i++) {
if (nums[i] > tail[maxLen - 1]) {
tail[maxLen] = nums[i];
maxLen++;
} else {
int left = 0;
int right = maxLen - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (tail[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}

tail[left] = nums[i];
}
}

return maxLen;
}
}

Analysis

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

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗