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.

Video explanation

Here is the video explaining below methods in detail.

Please check it out at here for dynamic programming based approach:

and below one for binary search based approach:

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.

Video

Please checkout the video here explaining this method:

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 Solution {

	public int lengthOfLIS(int[] nums) {
		return dfs(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
16
17
18
19
20
21

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        @lru_cache(None)  # Memoization decorator
        def dfs(idx: int, prev: int) -> int:
            # Base condition: when we reach the end of the array
            if idx == len(nums):
                return 0
            
            # Option 1: Pick the current element if it's greater than prev
            pick = 0
            if nums[idx] > prev:
                pick = 1 + dfs(idx + 1, nums[idx])
            
            # Option 2: Skip the current element
            dont_pick = dfs(idx + 1, prev)
            
            # Return the maximum of both options
            return max(pick, dont_pick)
        
        # Start recursion with initial values
        return dfs(0, float('-inf'))

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.

Video

Please checkout the video here explaining this method:

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 class Solution {
    public int lengthOfLIS(int[] nums) {
        return dfs(nums, 0, Integer.MIN_VALUE, new HashMap<>());
    }

    private int dfs(int[] nums, int idx, int prev, Map<String, Integer> memo) {
        // Base condition: when we go beyond the array, return 0
        if (idx == nums.length) {
            return 0;
        }

        // Create a unique key for the current state
        String key = idx + "," + prev;

        // Check if the result for this state is already computed
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Option 1: Pick the current element if it's greater than prev
        int pick = 0;
        if (nums[idx] > prev) {
            pick = 1 + dfs(nums, idx + 1, nums[idx], memo);
        }

        // Option 2: Skip the current element
        int dontPick = dfs(nums, idx + 1, prev, memo);

        // Compute and store the result in the memo table
        int result = Math.max(pick, dontPick);
        memo.put(key, result);

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

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        @lru_cache(None)  # Memoization decorator
        def dfs(idx: int, prev: int) -> int:
            # Base condition: when we reach the end of the array
            if idx == len(nums):
                return 0
            
            # Option 1: Pick the current element if it's greater than prev
            pick = 0
            if nums[idx] > prev:
                pick = 1 + dfs(idx + 1, nums[idx])
            
            # Option 2: Skip the current element
            dont_pick = dfs(idx + 1, prev)
            
            # Return the maximum of both options
            return max(pick, dont_pick)
        
        # Start recursion with initial values
        return dfs(0, float('-inf'))

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] memo = new int[n];  // Memoization array to track solved subproblems
        Arrays.fill(memo, -1);    // Initialize memo array

        return dfs(nums, 0, -1, memo);  // Start DFS with idx = 0 and prevIdx = -1
    }

    private int dfs(int[] nums, int idx, int prevIdx, int[] memo) {
        // Base case: when we go beyond the array
        if (idx == nums.length) {
            return 0;
        }

        // Check the result for this index in the memo array
        if (prevIdx != -1 && memo[prevIdx] != -1) {
            return memo[prevIdx];
        }

        // Option 1: Skip the current element
        int dontPick = dfs(nums, idx + 1, prevIdx, memo);

        // Option 2: Pick the current element (if valid)
        int pick = 0;
        if (prevIdx == -1 || nums[idx] > nums[prevIdx]) {
            pick = 1 + dfs(nums, idx + 1, idx, memo);
        }

        // Update the memo array for the previous index (prevIdx) and return the result
        int result = Math.max(pick, dontPick);
        if (prevIdx != -1) {
            memo[prevIdx] = result;
        }
        return result;
    }
}
 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:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        memo = [-1] * n  # Memoization array to store results for each index

        def dfs(idx: int, prev_idx: int) -> int:
            # Base case: when we reach the end of the array
            if idx == n:
                return 0
            
            # Check if the result is already computed for this state
            if prev_idx != -1 and memo[prev_idx] != -1:
                return memo[prev_idx]

            # Option 1: Skip the current element
            dont_pick = dfs(idx + 1, prev_idx)

            # Option 2: Pick the current element (if valid)
            pick = 0
            if prev_idx == -1 or nums[idx] > nums[prev_idx]:
                pick = 1 + dfs(idx + 1, idx)

            # Store the result in memo for the previous index (prev_idx)
            result = max(pick, dont_pick)
            if prev_idx != -1:
                memo[prev_idx] = result
            return result

        # Start DFS with idx = 0 and prev_idx = -1
        return dfs(0, -1)

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:

Video

Please checkout the video here explaining this method:

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

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

            int n = nums.length;
            int[] dp = new int[n];
            int ans = 0;

            // Initialize dp array with 1s (at least each element can form a subsequence of length 1)
            for (int i = 0; i < n; i++) {
                  dp[i] = 1;  // Every element starts as an LIS of 1
            }

            // Iterate through each element
            for (int i = 0; i < n; i++) {
                  // Compare with all previous elements
                  for (int j = 0; j < i; j++) {
	                  if (nums[j] < nums[i]) {
	                        dp[i] = Math.max(dp[i], dp[j] + 1);  // Update dp[i] based on dp[j]
	                  }
                  }
                  // Update the overall maximum LIS length
                  ans = Math.max(ans, dp[i]);
            }

            return ans;  // Return the maximum value in dp array
      }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
      def lengthOfLIS(self, nums: List[int]) -> int:
            if not nums:  # Handle empty array case
                  return 0

            n: int = len(nums)
            dp: List[int] = [1] * n  # Initialize dp array with 1s (minimum LIS length for each element)
            ans: int = 0  # Variable to store the overall LIS length

            # Iterate through each element
            for i in range(n):
                  # Compare with all previous elements
                  for j in range(i):  # Check all elements before index i
	                  if nums[j] < nums[i]:
	                        dp[i] = max(dp[i], dp[j] + 1)  # Update dp[i] based on dp[j]
	                  ans = max(ans, dp[i])  # Update the overall maximum LIS length

            return ans  # Return the maximum value in dp array

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.

Lets look

 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

Example 2:

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

Video explanation

Here is the video explaining this method in detail. Please check it out:

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

class Solution {
      public int lengthOfLIS(int[] nums) {
            // List to represent the smallest end elements of increasing subsequences
            List<Integer> temp = new ArrayList<>();

            for (int num : nums) {
                  // Use binary search to find the position of num in temp
                  int idx = Collections.binarySearch(temp, num);

                  if (idx < 0) {
                        idx = -(idx + 1);  // Convert to insertion point if not found
                  }

                  // If num can replace an existing value
                  if (idx < temp.size()) {
                        temp.set(idx, num);
                  } else {  
                        // If num is greater than all elements, it extends the LIS
                        temp.add(num);
                  }
            }

            // The size of temp is the LIS length
            return temp.size();
      }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # List to represent the smallest end elements of increasing subsequences
        temp: List[int] = []

        for num in nums:
            # Use binary search to find the index where num fits in temp
            idx = bisect.bisect_left(temp, num)

            # If num can replace an existing value
            if idx < len(temp):
                temp[idx] = num
            else:
                # If num is greater than all elements, it extends the LIS
                temp.append(num)

        # The size of temp is the LIS length
        return len(temp)

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 approach, 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.