673. Number of Longest Increasing Subsequence
Problem Description
The problem we're given involves an integer array called nums
. Our goal is to figure out how many subsequences of this array have the greatest length and are strictly increasing. A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Importantly, the condition here is that our subsequence must be strictly increasing, meaning that each element must be greater than the one before it.
Intuition
To address the problem, we consider a dynamic programming approach that allows us to build up the solution by considering the number of increasing subsequences ending at each element.
We use two arrays, dp
and cnt
. The dp
array will keep track of the length of the longest increasing subsequence that ends with nums[i]
for each element i
. The cnt
array, conversely, records the total number of such subsequences of maximum length ending with nums[i]
.
We need to iterate over each number in the nums
array and, for each element, iterate over all previous elements to check if a longer increasing subsequence can be created. When we find such an element nums[j]
that is less than nums[i]
(ensuring an increase), we have two cases:
- If the subsequence ending at
nums[j]
can be extended bynums[i]
to yield a longer subsequence, we updatedp[i]
and setcnt[i]
to be the same ascnt[j]
since we have identified a new maximum length. - If the extended subsequence has the same length as the current maximum subsequence ending at
nums[i]
, we increasecnt[i]
bycnt[j]
because we have found an additional subsequence of this maximum length.
As we move through the array, we maintain variables to keep track of the longest subsequence found so far (maxLen
) and the number of such subsequences (ans
). If a new maximum length is found, maxLen
is updated and ans
is set to the number of such subsequences up to nums[i]
. If we find additional sequences of the same maximum length, we add to ans
accordingly.
At the end of the iterations, ans
represents the total number of longest increasing subsequences present in the whole array nums
.
Learn more about Segment Tree and Dynamic Programming patterns.
Solution Approach
The solution uses a dynamic programming approach, which is a method for solving complex problems by breaking them down into simpler subproblems. It stores the results of these subproblems to avoid redundant work.
Here is a step-by-step breakdown of the approach:
-
Initialize two lists,
dp
andcnt
, both of sizen
, wheren
is the length of the input arraynums
. Each element ofdp
starts with a value of 1, because the minimum length of an increasing subsequence is 1 (the element itself). Similarly,cnt
starts with 1s because there's initially at least one way to have a subsequence of length 1 (again, the element itself). -
Iterate over the array with two nested loops. The outer loop goes from
i = 0
toi = n - 1
, iterating through the elements ofnums
. The inner loop goes fromj = 0
toj < i
, considering elements prior toi
. -
Within the inner loop, compare the elements at indices
j
andi
. Ifnums[i]
is greater thannums[j]
, it meansnums[i]
can potentially extend an increasing subsequence ending atnums[j]
. -
Check if the increasing subsequence length at
j
plus 1 is greater than the current subsequence length ati
(dp[j] + 1 > dp[i]
). If it is, this means we've found a longer increasing subsequence ending ati
, so updatedp[i]
todp[j] + 1
, and setcnt[i]
tocnt[j]
because the number of ways to achieve this longer subsequence ati
is the same as the number atj
. -
If
dp[j] + 1
equalsdp[i]
, it indicates another subsequence of the same maximum length ending ati
, so incrementcnt[i]
bycnt[j]
. -
Keep track of the overall longest sequence length found (
maxLen
) and the number of such sequences (ans
). After processing eachi
, comparedp[i]
withmaxLen
. Ifdp[i]
is greater thanmaxLen
, updatemaxLen
todp[i]
and setans
tocnt[i]
. Ifdp[i]
equalsmaxLen
, addcnt[i]
toans
. -
Continue this process until all elements have been considered. At the end, the variable
ans
will contain the number of longest increasing subsequences innums
.
By using dynamic programming, this solution effectively builds up the increasing subsequences incrementally and keeps track of their counts without having to enumerate each subsequence explicitly, which would be infeasible due to the exponential number of possible subsequences.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose the given integer array nums
is [3, 1, 2, 3, 1, 4]
.
-
We initialize
dp
andcnt
arrays as[1, 1, 1, 1, 1, 1]
since each element by itself is a valid subsequence of length 1 and there is at least one way to make a subsequence of one element. -
Start iterating with
i
from index 0 to the end of the array, and for eachi
, we iterate withj
from 0 toi-1
. -
When
i = 2
(element is2
), we find thatnums[2] > nums[0]
(2 > 3). However, as 2 is not greater than 3, no updates are done. Then we comparenums[2]
withnums[1]
(2 > 1), this is true, and sincedp[1] + 1 > dp[2]
, we updatedp[2]
todp[1] + 1 = 2
, also updatingcnt[2]
tocnt[1]
. -
Moving to
i = 3
(element is3
), we compare with all previous elements one by one. Forj = 0
,nums[3]
(3) is not greater thannums[0]
(3). Forj = 1
,nums[3]
(3) is greater thannums[1]
(1), anddp[1] + 1 > dp[3]
so we updatedp[3]
andcnt[3]
to 2. Forj = 2
,nums[3]
(3) is greater thannums[2]
(2), anddp[2] + 1 = 3
which is greater than the currentdp[3]
(2). So we updatedp[3]
to 3, andcnt[3]
tocnt[2]
. -
Continue this process for
i = 4
andi = 5
. When we reachi = 5
(element is4
) andj = 3
, sincenums[5]
(4) is greater thannums[3]
(3) anddp[3] + 1 > dp[5]
(4 > 1), we updatedp[5]
to 4, andcnt[5]
tocnt[3]
. -
We keep track of the
maxLen
andans
throughout the process. Initially,maxLen
is 1 andans
is 6 (because we have six elements, each a subsequence of length 1). After updating alldp[i]
andcnt[i]
, we findmaxLen
to be 4 (subsequences ending at index 5) andans
will be updated to the count of the longest increasing subsequences ending withnums[5]
, which in this case is 1.
At the end of this process, the dp
array is [1, 1, 2, 3, 1, 4]
and the cnt
array is [1, 1, 1, 1, 1, 1]
. We conclude that the length of the longest increasing subsequence is 4 and the number of such subsequences is 1 (ending with the element 4
in the original array).
This walk-through illuminates the step-by-step application of our dynamic programming solution to find the total number of the longest increasing subsequences present in the array nums
.
Solution Implementation
1class Solution:
2 def findNumberOfLIS(self, nums: List[int]) -> int:
3 # Initialize variables
4 max_length = 0 # The length of the longest increasing subsequence
5 answer = 0 # The number of longest increasing subsequences
6 num_elements = len(nums) # Number of elements in the input list
7 dp = [1] * num_elements # dp[i] will store the length of the LIS ending at nums[i]
8 count = [1] * num_elements # count[i] will store the number of LIS's ending at nums[i]
9
10 # Iterate through the list to populate dp and count arrays
11 for i in range(num_elements):
12 for j in range(i):
13 # Check if the current element is greater than the previous ones to form an increasing sequence
14 if nums[i] > nums[j]:
15 # If we found a longer increasing subsequence ending at i
16 if dp[j] + 1 > dp[i]:
17 dp[i] = dp[j] + 1
18 count[i] = count[j]
19 # If we found another LIS of the same length as the longest found ending at i
20 elif dp[j] + 1 == dp[i]:
21 count[i] += count[j]
22
23 # Update the global maximum length and the number of such sequences
24 if dp[i] > max_length:
25 max_length = dp[i]
26 answer = count[i]
27 elif dp[i] == max_length:
28 answer += count[i]
29
30 # Return the total number of longest increasing subsequences
31 return answer
32
1class Solution {
2 public int findNumberOfLIS(int[] nums) {
3 int maxLength = 0; // Store the length of the longest increasing subsequence
4 int numberOfMaxLIS = 0; // Store the count of longest increasing subsequences
5 int n = nums.length; // The length of the input array
6
7 // Arrays to store the length of the longest subsequence up to each element
8 int[] lengths = new int[n]; // dp[i] will be the length for nums[i]
9 int[] counts = new int[n]; // cnt[i] will be the number of LIS for nums[i]
10
11 for (int i = 0; i < n; i++) {
12 lengths[i] = 1; // By default, the longest subsequence at each element is 1 (the element itself)
13 counts[i] = 1; // By default, the count of subsequences at each element is 1
14
15 // Check all elements before the i-th element
16 for (int j = 0; j < i; j++) {
17 // If the current element can extend the increasing subsequence
18 if (nums[i] > nums[j]) {
19 // If a longer subsequence is found
20 if (lengths[j] + 1 > lengths[i]) {
21 lengths[i] = lengths[j] + 1; // Update the length for nums[i]
22 counts[i] = counts[j]; // Update the count for nums[i]
23 } else if (lengths[j] + 1 == lengths[i]) {
24 counts[i] += counts[j]; // If same length, add the count of subsequences from nums[j]
25 }
26 }
27 }
28
29 // If a new maximum length of subsequence is found
30 if (lengths[i] > maxLength) {
31 maxLength = lengths[i]; // Update the maxLength with the new maximum
32 numberOfMaxLIS = counts[i]; // Reset the count of LIS
33 } else if (lengths[i] == maxLength) {
34 // If same length subsequences are found, add the count to the total
35 numberOfMaxLIS += counts[i];
36 }
37 }
38
39 // Return the total count of longest increasing subsequences
40 return numberOfMaxLIS;
41 }
42}
43
1class Solution {
2public:
3 // Function to find the number of longest increasing subsequences
4 int findNumberOfLIS(vector<int>& nums) {
5 int n = nums.size(); // Size of the nums array
6 if (n <= 1) return n; // If array is empty or has one element, return n
7
8 int maxLength = 0; // Variable to store length of longest increasing subsequence
9 int numberOfLIS = 0; // Variable to store number of longest increasing subsequences
10 vector<int> lengths(n, 1); // DP array - lengths[i] will store the length of LIS ending with nums[i]
11 vector<int> counts(n, 1); // Array to store the count of LIS of the same length ending with nums[i]
12
13 // Iterate over the array
14 for (int i = 0; i < n; ++i) {
15 // Check all previous numbers
16 for (int j = 0; j < i; ++j) {
17 // If nums[i] can be appended to the LIS ending with nums[j]
18 if (nums[i] > nums[j]) {
19 // If a longer subsequence ending with nums[i] is found
20 if (lengths[j] + 1 > lengths[i]) {
21 lengths[i] = lengths[j] + 1; // Update the length of LIS for nums[i]
22 counts[i] = counts[j]; // Reset the count for nums[i] to the counts of nums[j]
23 } else if (lengths[j] + 1 == lengths[i]) {
24 // If another LIS of the same length ending with nums[i] is found
25 counts[i] += counts[j]; // Increment the count for nums[i]
26 }
27 }
28 }
29 // Update global max length and count of the LIS
30 if (lengths[i] > maxLength) {
31 maxLength = lengths[i]; // Update the maximum length
32 numberOfLIS = counts[i]; // Update the number of LIS
33 } else if (lengths[i] == maxLength) {
34 numberOfLIS += counts[i]; // If same length, add the count for nums[i] to global count
35 }
36 }
37 return numberOfLIS; // Return the number of longest increasing subsequences
38 }
39};
40
1// Define types for better code readability
2type NumberArray = number[];
3
4// Function to find the number of longest increasing subsequences
5function findNumberOfLIS(nums: NumberArray): number {
6 let n: number = nums.length; // Size of the nums array
7 if (n <= 1) return n; // If array is empty or has one element, return n
8
9 let maxLength: number = 0; // Variable to store length of longest increasing subsequence
10 let numberOfLIS: number = 0; // Variable to store number of longest increasing subsequences
11 let lengths: NumberArray = new Array(n).fill(1); // DP array to store lengths of LIS up to nums[i]
12 let counts: NumberArray = new Array(n).fill(1); // Array to store counts of LIS of same length at nums[i]
13
14 // Iterate over the array to build up lengths and counts
15 for (let i = 0; i < n; ++i) {
16 // Check all elements before i
17 for (let j = 0; j < i; ++j) {
18 // If current element nums[i] can extend the LIS ending at nums[j]
19 if (nums[i] > nums[j]) {
20 // Found a longer subsequence ending at nums[i]
21 if (lengths[j] + 1 > lengths[i]) {
22 lengths[i] = lengths[j] + 1; // Update the LIS length at i
23 counts[i] = counts[j]; // Reset counts at i to those at j
24 } else if (lengths[j] + 1 === lengths[i]) {
25 // Found another LIS of the same length ending at i
26 counts[i] += counts[j]; // Increment counts at i
27 }
28 }
29 }
30 // Update maxLength and numberOfLIS if needed
31 if (lengths[i] > maxLength) {
32 maxLength = lengths[i]; // Update max length with the new longest found
33 numberOfLIS = counts[i]; // Set the number of LIS to the count at i
34 } else if (lengths[i] === maxLength) {
35 numberOfLIS += counts[i]; // Another LIS found - increase the number of LIS
36 }
37 }
38
39 return numberOfLIS; // Return the number of longest increasing subsequences found
40}
41
Time and Space Complexity
The given Python function findNumberOfLIS
calculates the number of Longest Increasing Subsequences (LIS) in an array of integers. Analyzing the time complexity involves examining the nested loop structure, where the outer loop runs n
times (once for each element in the input list nums
) and the inner loop runs at most i
times for the ith
iteration of the outer loop. Consequently, in the worst case, the inner loop executes 1 + 2 + 3 + ... + (n - 1)
times, which can be expressed as the sum of the first n-1
natural numbers, resulting in a time complexity of O(n^2)
.
The space complexity of the function is determined by the additional memory allocated for the dynamic programming arrays dp
and cnt
, each of size n
. Therefore, the space complexity of the function is O(n)
, which is linear with respect to the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!