Number Of Longest Increasing Subsequence Leetcode Problem 673 [Python]
In this blog post, we're going to tackle the LeetCode problem 673, Number Of Longest Increasing Subsequence This problem falls under the category of 1-D Dynamic Programming and is considered of medium difficulty.
We'll provide a detailed explanation of the problem, explore the efficient Python solution, discuss time and space complexity, and offer a comprehensive understanding of the problem's constraints.
So, whether you're a beginner or an experienced coder, this guide will provide you with all the information you need to tackle this problem.
If you want to check the original problem statement, you can find it here.
Problem Overview
Given an integer array nums, the task is to return the number of longest increasing subsequences.
It's essential to note that these subsequences must be strictly increasing.
In simpler terms, you need to find the count of the longest increasing subsequences in the given array.
Let's break down the problem using an example:
Example:
Input:
nums = [1, 3, 5, 4, 7]
Output:
2
Explanation:
The two longest increasing subsequences in the given array are [1, 3, 4, 7] and [1, 3, 5, 7].
Another example:
Input:
nums = [2, 2, 2, 2, 2]
Output:
5
Explanation:
The length of the longest increasing subsequence is 1, and there are five increasing subsequences of length 1 in the array, so the output is 5.
Constraints:
- 1 <=
nums.length<= 2000 - -10^6 <=
nums[i]<= 10^6
This problem challenges us to not only find the length of the longest increasing subsequence but also count how many such subsequences exist in the given array.
We'll explore an efficient Python solution to address this challenge.
Efficient Python Code Solution
We'll provide two efficient approaches to solve this problem.
Both approaches have a time complexity of O(n^2) and involve dynamic programming.
Let's go through each of them.
Approach 1: Recursive Solution with Caching
We'll start with a recursive approach while keeping track of our results using a cache (a dictionary).
The basic idea is to consider each element in the array as the starting point of a subsequence and then recursively explore the elements that come after it to find the longest increasing subsequence.
Here is the Python code for this approach:
def findNumberOfLIS(self, nums: List[int]) -> int:
# Initialize a cache to store computed results
dp = {} # key = index, value = [length of LIS, count]
lenLIS, res = 0, 0 # length of LIS, count of LIS
def dfs(i):
if i in dp:
return dp[i]
maxLen, maxCnt = 1, 1 # length and count of LIS
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]: # Ensure increasing order
length, count = dfs(j)
if length + 1 > maxLen:
maxLen, maxCnt = length + 1, count
elif length + 1 == maxLen:
maxCnt += count
nonlocal lenLIS, res
if maxLen > lenLIS:
lenLIS, res = maxLen, maxCnt
elif maxLen == lenLIS:
res += maxCnt
dp[i] = [maxLen, maxCnt]
return dp[i]
for i in range(len(nums)):
dfs(i)
return res
In this approach, we define a cache (dp) to store the length and count of the longest increasing subsequences starting from each index.
We use a recursive function (dfs) to explore all possible subsequences.
The results are cached to avoid redundant computations.
Approach 2: Dynamic Programming
In this approach, we'll use dynamic programming to solve the problem efficiently.
We'll create a similar cache (dp) to store the length and count of the longest increasing subsequences.
We'll iterate through the array in reverse order, starting from the last element and working our way to the first element.
Here is the Python code for this approach:
def findNumberOfLIS(self, nums: List[int]) -> int:
dp = {} # key = index, value = [length of LIS, count]
lenLIS, res = 0, 0 # length of LIS, count of LIS
for i in range(len(nums) - 1, -1, -1):
maxLen, maxCnt = 1, 1 # Length and count of LIS starting from i
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]: # Ensure increasing order
length, count = dp[j] # Length and count of LIS starting from j
if length + 1 > maxLen:
maxLen, maxCnt = length + 1, count
elif length + 1 == maxLen:
maxCnt += count
if maxLen > lenLIS:
lenLIS, res = maxLen, maxCnt
elif maxLen == lenLIS:
res += maxCnt
dp[i] = [maxLen, maxCnt]
return res
This approach uses a bottom-up dynamic programming approach, similar to the recursive solution but without the need for recursion.
We start at the end of the array and work our way backward, calculating the length and count of the longest increasing subsequences for each element.
Time and Space Complexity
Now, let's analyze the time and space complexity of the efficient Python solution:
Time Complexity:
Both of the efficient approaches have a time complexity of O(n^2) because they involve nested loops.
We iterate through the array twice, once to explore each element as the starting point of a subsequence, and once to compare it with other elements to find the longest increasing subsequences.
Space Complexity:
The space complexity of both approaches is O(n).
This is because we use a cache (dp) to store the results for each index in the array.
The size of the cache is proportional to the size of the input array, so the space complexity is linear.
Reasoning Behind Our Approach
The core idea behind our approach is to use dynamic programming to find the length and count of the longest increasing subsequences starting from each index in the array.
By exploring the elements in reverse order and maintaining a cache of results, we can efficiently compute the desired values without redundant computations.
Our approach allows us to tackle the problem step by step, finding the longest increasing subsequences and their counts, and updating the maximum values as we progress through the array.
The use of caching (dp) prevents us from recalculating results for the same index, significantly improving the efficiency of our solution.
Related Interview Questions By Company:
- Design Linked List LeetCode
- Find First And Last Position Of Element In Sorted Array LeetCode
- Check If Move Is Legal LeetCode
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Conclusion
In
this blog post, we discussed the LeetCode problem 673, Number Of Longest Increasing Subsequence We explored the problem statement, outlined the constraints, and provided two efficient Python solutions.
These solutions involve dynamic programming and utilize a cache to store results, which helps in minimizing redundant computations and improving efficiency.
By understanding and implementing these solutions, you'll be well-prepared to tackle this problem and similar ones that involve finding the number of longest increasing subsequences in an array.
