Problem

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

Examples

Example 1:

1
2
3

Input: A = [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:

1
2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

1
2

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Solution

A very common problem in computer programming is finding the longest increasing (decreasing) subsequence in a sequence of numbers (usually integers). Actually this is a typical dynamic programming problem.

Method 1 - Using Recursion OR Brute Force šŸŒ

We need to find maximum increasing subsequence length. In the brute-force approach, we can model this problem as -

  1. If the current element is greater than the previous element, then we can either pick it or dont pick it because we may get a smaller element somewhere ahead which is greater than previous and picking that would be optimal. So we try both options.
  2. If the current element is smaller or equal to previous element, it can’t be picked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solutio {

	public int lengthOfLIS(int[] nums) {
		return findLIS(nums, 0, Integer.MIN_VALUE);
	}

	private int dfs(int[] nums, int idx, int prev) {
		if (idx == nums.length) {
			return 0;
		}

		int pick = 0;

		if (nums[idx] > prev) {
			// we pick curr element as it is more than prev for now
			pick = 1 + dfs(nums, idx + 1, nums[idx]);
		}
		// this time we dont pick the element
		// 0 indicates length will not be updated
		int dontPick = 0 + dfs(nums, idx + 1, prev);
		return Math.max(pick, dontPick);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int lengthOfLIS(int[] nums) {
	solve(nums, 0, Integer.MIN_VALUE);
}
private int solve(int[] nums, int idx, int prev) {
	if(idx == size(nums)) {return 0;}

	int pick = 0;
	if (nums[idx] > prev) {
		
		pick = 1 + solve(nums , idx + 1 , arr[idx]);
	}
	
	int dontPick = 0 + solve(nums , idx + 1 , prev);
	return Math.max(pick , dontPick);
}

Complexity

  • ā° Time complexity:Ā O(2^n)
  • šŸ§ŗ Space complexity:Ā O(n) assuming recursion stack

Method 2 - Top Down DP Memoization

There are many unnecessary repeated calculations in the brute-force approach. We can observe that the length of increasing subsequence starting atĀ ith element with previously picked elementĀ prevĀ will always be the same. So we can useĀ dynamic programmingĀ to store the results for this state and reuse again in the future.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int lengthOfLIS(int[] nums) {
	solve(nums, 0, Integer.MIN_VALUE, new HashMap<int[], Integer>());
}
private int solve(int[] nums, int idx, int prev, Map<int[], Integer> cache) {
	if(idx == size(nums)) {return 0;}
	int[] key = new int[idx, prev];
	if(cache.containsKey(key)) {
		return cache.get(key);
	}
	int pick = 0;
	if (nums[idx] > prev) {
		// we pick curr element as it is more than prev for now
		pick = 1 + solve(nums , idx + 1 , arr[idx], cache);
	}
	// this time we dont pick the element
	// 0 indicates length will not be updated
	int dontPick = 0 + solve(nums , idx + 1 , prev, cache);
	int ans = Math.max(pick , dontPick);
	cache.put(key, ans);
	return ans;
}
 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

public Solution {

	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		solve(nums, 0, -1, new Integer[n][n + 1]);
	}

	private int solve(int[] nums, int idx, int prevIdx, Integer[][] memo) {
		if (idx == nums.length) {
			return 0;
		}

		if (memo[idx][prevIdx + 1] != null) {
			return memo[idx][prevIndex + 1];
		}

		int pick = 0;

		if (prevIdx == -1 || nums[idx] > nums[prevIdx]) {
			// we pick curr element as it is more than prev for now
			pick = 1 + solve(nums, idx + 1, idx, memo);
		}
		// this time we dont pick the element
		// 0 indicates length will not be updated
		int dontPick = 0 + solve(nums, idx + 1, prevIdx, memo);
		int ans = Math.max(pick, dontPick);
		memo[idx, prevIdx + 1] = ans;
		return ans;
	}
}

Complexity

  • ā° Time complexity:Ā O(n^2)
  • šŸ§ŗ Space complexity:Ā O(n^2)

Method 3 - Top Down DP with Memo Space Optimized

We can do better and further reduce the state stored using DP. It’s redundant to store states for allĀ iĀ havingĀ prevĀ as its previous element index. The length will always be greatest for the stateĀ (prev, prev)Ā since no more elements beforeĀ prevĀ can be taken. So we can just use a linear DP whereĀ dp[i]Ā denotes the LIS starting at indexĀ i

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int lengthOfLIS(int[] nums) {
	int n = nums.length;
	solve(nums, 0, -1, new Integer[n+1]);
}
private int solve(int[] nums, int idx, int prevIdx, int[] memo) {
	if(idx == nums.length) {return 0;}
	if (memo[prevIdx+1] != null ) {
		return dp[idx];
	}

	int pick = 0;
	if (prevIdx == -1 || nums[idx] > nums[prevIdx]) {
		// we pick curr element as it is more than prev for now
		pick = 1 + solve(nums , idx + 1 , idx, memo);
	}
	// this time we dont pick the element
	// 0 indicates length will not be updated
	int dontPick = 0 + solve(nums , idx + 1 , prevIdx, memo);
	int ans = Math.max(pick , dontPick);
	memo[prevIdx+1] = ans;
	return ans;
}

Complexity

  • ā° Time complexity:Ā O(n^2)
  • šŸ§ŗ Space complexity:Ā O(n)

Method 4 - Bottom Up DP with Tabulation

Let max[i] represent the length of the longest increasing subsequence so far. If any element before i is smaller than nums[i], then max[i] = max(max[i], max[j]+1). Here is an example:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;

    int[] max = new int[nums.length];

    for (int i = 0; i < nums.length; i++) {
        max[i] = 1; // initially LIS is 1
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max[i] = Math.max(max[i], max[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < max.length; i++) {
	    ans = Math.max(ans, max[i]);
    }
    return ans;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int lengthOfLIS(int[] nums){
	int n = nums.length;
	int[] dp = new int[n];
	int ans = 0;
	
	for(int i = 0 ; i < n ; i++){
		dp[i] = 1;
		for(int j = 0 ; j < i; j++){
			if(nums[i] > nums[j]){
				max = Math.max(dp[i] , dp[j] + 1);
			}
		}
		ans = Math.max(ans , dp[i]);
	}
	return ans;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
	int n = nums.length;
    int[] max = new int[n];

    for (int i = n - 1; i >= 0; i--) {
        max[i] = 1; // initially LIS is 1
        for (int j = i+1; j < n; j++) {
            if (nums[i] < nums[j]) {
                max[i] = Math.max(max[i], max[j] + 1);
            }
        }
    }

    int result = 0;
    for (int i = 0; i < max.length; i++) {
	    result = Math.max(result, max[i]);
    }
    return result;
}

Complexity

  • ā° Time complexity:Ā O(n^2)
  • šŸ§ŗ Space complexity:Ā O(n)

Method 5 - Using Binary Search

In the brute-force approach, we were not sure if an element should be included or not to form the longest increasing subsequence and thus we explored both options. The problem lies in knowing if an element must be included in the sequence formed till now. Let’s instead try an approach where we include element whenever possible to maximize the length and if it’s not possible, then create a new subsequence and include it.

Algo

  1. Traverse from 0 to n-1, the DP array keep the longest sequence.
  2. if the val is bigger than largest in the dp array, add it to the end;
  3. if it is among the sequence, return the idx that bigger than pres, update the array with this position if val is smaller than dp[idx]; This is to keep the sequence element with the smallest number.

For example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

nums = [10, 9, 2, 5, 3, 7, 101, 18]

10 
9
2
2,5
2,3
2,3,7
2,3,7,101
2,3,7,18

Code

 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
35

 public int lengthOfLIS(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int len = 0;
	for (int i = 1; i<nums.length; i++) {
		int pos = binarySearch(dp, 0, len, nums[i]);
		if (nums[i]<dp[pos]) {
			dp[pos] = nums[i];
		}
		if (pos > len) {
			len = pos;
			dp[len] = nums[i];
		}
	}
	return len + 1;
}

private int binarySearch(int[] dp, int left, int right, int val) {
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (dp[mid] == val) {
			return mid;
		} else {
			if (dp[mid]<val) {
				left = mid;
			} else {
				right = mid;
			}
		}
	}
	return left;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int lengthOfLIS(int[] nums) {            
	int[] dp = new int[nums.length];
	int len = 0;

	for(int x : nums) {
		int i = Arrays.binarySearch(dp, 0, len, x);
		if(i < 0) i = -(i + 1);
		dp[i] = x;
		if(i == len) len++;
	}

	return len;
}
 
1
2
3
4
5
6
7
8
9

nums = [9, 1, 3, 7, 5, 6, 20]

9
1
1 3
1 3 7
1 3 5
1 3 5 6
1 3 5 6 20

Complexity

  • ā° Time complexity:Ā O(n log n)
  • šŸ§ŗ Space complexity:Ā O(n)

Method 6 - Using Graph Theory and DP

You can solve the Longest Increasing Subsequence (LIS) problem using graph theory by constructing a directed acyclic graph (DAG) where each node represents an element of the array, and there’s a directed edge from node (i) to node (j) if (nums[i] < nums[j]) and (i < j).

The task then becomes finding the longest path in this DAG, which corresponds to the LIS.

This is how the graph look for:

1

nums = [9, 1, 3, 7, 5, 6, 20]

graph LR;
I(9) ---> S(20)
A(1) ---> C(3)
A(1) ---> G(7)
A(1) ---> E(5)
A(1) ---> F(6)
A(1) ---> S
C ---> G & E & F & S
G ---> S
E ---> F & S
F ---> S

style A fill:#FF9933
style C fill:#FF9933
style E fill:#FF9933
style F fill:#FF9933
style S fill:#FF9933

linkStyle 1 stroke:#6f6
linkStyle 7 stroke:#6f6
linkStyle 11 stroke:#6f6
linkStyle 13 stroke:#6f6

The path marked is longest increasing subsequence or longest path in the DAG.

Here are the steps:

  1. Graph Construction:

    • Represent the array elements as nodes in a graph.
    • For each pair of elements ((nums[i], nums[j])) where (i < j) and (nums[i] < nums[j]), add a directed edge from node (i) to node (j).

  2. Longest Path in DAG using Dynamic Programming:

    • Initialize aĀ dpĀ array of the same length as the input array, with each element initially set to 1 (dp[i] = 1). The valueĀ dp[i]Ā represents the length of the longest increasing subsequence ending at indexĀ i.
    • For each node (i) (from (0) to (n-1)):
      • For each node (j) (from (0) to (i-1)):
        • If there’s an edge from (j) to (i) (nums[j] < nums[i]), updateĀ dp[i]: [dp[i] = \max(dp[i], dp[j] + 1)]
    • The length of the longest increasing subsequence is the maximum value in theĀ dpĀ array.

Code

 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
35
36

class Solution {

	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		List<Integer> [] graph = new List[n];

		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (nums[i]<nums[j]) {
					graph[i].add(j);
				}
			}
		}

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

		for (int i = 0; i < n; i++) {
			for (int j: graph[i]) {
				dp[j] = Math.max(dp[j], dp[i] + 1);
			}
		}

		int ans = 1;

		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, dp[i]);
		}

		return ans;
	}
}

Method 7 - Using Graph Theory and Toposort

This is similar to previous problem, but instead of DP, we use topological sort.

Here are the steps:

  1. Construct the Graph:
    • Initialize a list of adjacency lists (graph) to represent the DAG.
    • Add directed edges according to the conditionsĀ nums[i] < nums[j]Ā andĀ i < j.
  2. Topological Sort:
    • Perform topological sorting of the graph. Topological sorting is used to linearize the order of nodes so that all edges go from left to right.
  3. Find the Longest Path in the DAG:
    • Use dynamic programming on the topologically sorted nodes to find the longest path.

Code

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

public class Solution {

	public int lengthOfLIS(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}

		int n = nums.length;

		// Step 1: Create the graph representation
		List<Integer> [] graph = new List[n];

		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}

		// Add the edges
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (nums[i]<nums[j]) {
					graph[i].add(j);
				}
			}
		}

		// Step 2: Perform a topological sort on the graph
		List<Integer> topoSort = topologicalSort(graph);

		// Step 3: Find the longest path in the DAG
		int[] dp = new int[n];
		Arrays.fill(dp, 1);

		int maxLen = 1;

		for (int node: topoSort) {
			for (int neighbor: graph[node]) {
				dp[neighbor] = Math.max(dp[neighbor], dp[node] + 1);
				maxLen = Math.max(maxLen, dp[neighbor]);
			}
		}

		return maxLen;
	}

	private List<Integer> topologicalSort(List<Integer> [] graph) {
		int n = graph.length;
		int[] inDegree = new int[n];

		for (int i = 0; i < n; i++) {
			for (int neighbor: graph[i]) {
				inDegree[neighbor]++;
			}
		}

		Queue<Integer> queue = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			if (inDegree[i] == 0) {
				queue.offer(i);
			}
		}

		List<Integer> topoOrder = new ArrayList<>();

		while (!queue.isEmpty()) {
			int node = queue.poll();
			topoOrder.add(node);

			for (int neighbor: graph[node]) {
				inDegree[neighbor]--;

				if (inDegree[neighbor] == 0) {
					queue.offer(neighbor);
				}
			}
		}

		return topoOrder;
	}
}

Complexity

  • ā° Time complexity:Ā O(n^2) - because we have nested loops to construct the graph, which processes every pair of nodes.
  • šŸ§ŗ Space complexity:Ā O(n^2) - due to the storage required for the adjacency list of the graph in the worst case.