Problem

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

Examples

Example 1:

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:

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

Example 3:

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

Java
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);
	}
}

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

Java
DP with Map of (i, prev) as Key and Ans as Value

But it wouldn’t be scalable to store the state as (i, prev) because prev element can be any number in [-10^4, 10^4] meaning we would need to declare a matrix dp[n][1e8] which won’t be possible

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;
}
DP with array but using prevIndex instead

Instead, we could store the state of (i, prev), where prev denotes the index of previous chosen element. Thus we would use a dp matrix where dp[i][prevIndex] will denote the longest increasing subsequence from index i when previous chosen element’s index is prevIndex.

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

Java
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

Java
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;
}

We can merge 2 loops:

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;
}

We can also run DIP from behind. The last element will initally have LIS = 1. But then we check the element on the right is smaller than it or not. If yes, they both form LIS, hence we now have LIS = 2. And we continue.

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:

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

Java
 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;
}

We can also use Arrays.binarySearch(int[] array, int fromIndex, int toIndex, int target):

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;
}

Example 2:

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:

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

Java
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

Java
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.