Longest Increasing Subsequence

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.

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: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/RScTdrx_6TU" frameborder="0" allowfullscreen></iframe></div>

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 -

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.
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: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/rFXiMjSCT8o" frameborder="0" allowfullscreen></iframe></div>

Code

Java

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

Python

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: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/rFXiMjSCT8o" frameborder="0" allowfullscreen></iframe></div>

Code

Java

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

Python

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

Java

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

Python

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: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/rFXiMjSCT8o" frameborder="0" allowfullscreen></iframe></div>

Code

Java

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

Python

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

Traverse from 0 to n-1, the DP array keep the longest sequence.
if the val is bigger than largest in the dp array, add it to the end;
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

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:

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

Java

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

Python

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:

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:

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).
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 approach, but instead of DP, we use topological sort.

Here are the steps:

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

Problem

Examples

Solution

Video explanation

Method 1 - Using Recursion OR Brute Force 🐌

Video

Code

Java

Python

Complexity

Method 2 - Top Down DP Memoization

Video

Code

Java

Python

Complexity

Method 3 - Top Down DP with Memo Space Optimized

Code

Java

Python

Complexity

Method 4 - Bottom Up DP with Tabulation

Video

Code

Java

Python

Complexity

Method 5 - Using Binary Search

Algo

Video explanation

Code

Java

Python

Complexity

Method 6 - Using Graph Theory and DP

Code

Java

Method 7 - Using Graph Theory and Toposort

Code

Java

Complexity

Comments