Whenever I can't follow official editorial, I go for Neetcode. You're superb in explain algorithm thought flow, and more importantly, you code according!
There is a O(n logn) solution for this using patience sort but it is considerably trickier to code. Also, you can store a tuple, instead of a list as dp's value.
@@NeetCode The explanation was more or less like a 2 pass approach but you did it in one pass. Had to think through carefully and walk through the example with the code before getting the exact concept of the code. Thank you very much. You are helping a lot.
Java code for this - class Solution { public int findNumberOfLIS(int[] nums) { int n = nums.length; int dp_len[] = new int[n]; //store length of LIS starting at each index int dp_count[] = new int[n]; //store count of such LIS of length starting and each index. Arrays.fill(dp_len, 1); Arrays.fill(dp_count, 1); int lenLIS = 0; //length of longest LIS int totalCount = 0; //total no. of longest LIS for(int i = n - 1; i >= 0; i --) { //start from right to left int curMax = 1; int curCount = 1; for(int j = i + 1; j < n; j ++) { //for each ele, check if LIS exists on right if(nums[j] > nums[i]) { //increasing order int len = dp_len[j]; int count = dp_count[j]; if(len + 1 > curMax) { curMax = len + 1; curCount = count; } else if(len + 1 == curMax) { curCount += count; } } } if(curMax > lenLIS) { lenLIS = curMax; totalCount = curCount; } else if(curMax == lenLIS) { totalCount += curCount; } dp_len[i] = curMax; dp_count[i] = curCount; } return totalCount;
nice, but no need to fill the arrays with 1 since we already do that by default if we need to when setting curMax = curCount = 1 and there are no numbers greater than the number after
Thanks, another version: class Solution { public int findNumberOfLIS(int[] nums) { int n = nums.length; int[] LIS = new int[n]; int[] count = new int[n]; Arrays.fill(LIS, 1); int maxLIS = Integer.MIN_VALUE; for (int i = n-1; i >= 0; --i) { int curMax = 0; int curCount = 1; for (int j = i+1; j < n; ++j) { if (nums[j] > nums[i]) { if (LIS[j] > curMax) { curMax = LIS[j]; curCount = count[j]; } else if (LIS[j] == curMax) { //dups produce many LISequences //sum up all counters of dups curCount+=count[j]; } } } //dp LIS[i] = 1 + curMax; count[i] = Math.max(curCount, 1); maxLIS = Math.max(maxLIS, LIS[i]); } int numberOfLIS = 0; for (int i = 0; i < count.length; ++i) { if (LIS[i] == maxLIS) { numberOfLIS+=count[i]; } } return numberOfLIS; } }
nice explaination and and way you update maxLen and maxCnt in 1 loop, never though of that because I afraid something wrong and not clear, so I do 2 seperated loops.
couldn’t we solve this in O(n) time? by using the closing window approach and keeping track of the max length and count in a map, then increment that count in the map every time another LIS is found (while we are iterating the array)
I love your videos and they are super super helpful!!! However, sometimes I do find your explanations just a little on the wordy side.. the best explanation still though!
Whenever I can't follow official editorial, I go for Neetcode. You're superb in explain algorithm thought flow, and more importantly, you code according!
How is this a medium? It kills me
Hard Q kills u many times
This should definitely be a hard question! 😂
OMG YES NEETCODE!! Thank you for doing solution! Really appreciate it!
I dont do a leetcode question if there is no NeetCode video for it LOL
There is a O(n logn) solution for this using patience sort but it is considerably trickier to code. Also, you can store a tuple, instead of a list as dp's value.
But i dont think you can get the number of LIS from that, it would be useful for getting the length or to retrieve any one of the LIS
I get so happy when I see your knew vids 😊
Bro, you're the best, and funny 😂 1000 bucks 😂 Keep it up 💪🏻
Excellent Explanation Sir Please Keep Going
Thanks and for sure!!
@@NeetCode The explanation was more or less like a 2 pass approach but you did it in one
pass. Had to think through carefully and walk through the example with the code before getting
the exact concept of the code.
Thank you very much.
You are helping a lot.
Java code for this -
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int dp_len[] = new int[n]; //store length of LIS starting at each index
int dp_count[] = new int[n]; //store count of such LIS of length starting and each index.
Arrays.fill(dp_len, 1);
Arrays.fill(dp_count, 1);
int lenLIS = 0; //length of longest LIS
int totalCount = 0; //total no. of longest LIS
for(int i = n - 1; i >= 0; i --) { //start from right to left
int curMax = 1;
int curCount = 1;
for(int j = i + 1; j < n; j ++) { //for each ele, check if LIS exists on right
if(nums[j] > nums[i]) { //increasing order
int len = dp_len[j];
int count = dp_count[j];
if(len + 1 > curMax) {
curMax = len + 1;
curCount = count;
} else if(len + 1 == curMax) {
curCount += count;
}
}
}
if(curMax > lenLIS) {
lenLIS = curMax;
totalCount = curCount;
} else if(curMax == lenLIS) {
totalCount += curCount;
}
dp_len[i] = curMax;
dp_count[i] = curCount;
}
return totalCount;
}
}
nice, but no need to fill the arrays with 1 since we already do that by default if we need to when setting curMax = curCount = 1 and there are no numbers greater than the number after
Thanks, another version:
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] LIS = new int[n];
int[] count = new int[n];
Arrays.fill(LIS, 1);
int maxLIS = Integer.MIN_VALUE;
for (int i = n-1; i >= 0; --i) {
int curMax = 0;
int curCount = 1;
for (int j = i+1; j < n; ++j) {
if (nums[j] > nums[i]) {
if (LIS[j] > curMax) {
curMax = LIS[j];
curCount = count[j];
} else if (LIS[j] == curMax) {
//dups produce many LISequences
//sum up all counters of dups
curCount+=count[j];
}
}
}
//dp
LIS[i] = 1 + curMax;
count[i] = Math.max(curCount, 1);
maxLIS = Math.max(maxLIS, LIS[i]);
}
int numberOfLIS = 0;
for (int i = 0; i < count.length; ++i) {
if (LIS[i] == maxLIS) {
numberOfLIS+=count[i];
}
}
return numberOfLIS;
}
}
Excellent job!
nice explaination and and way you update maxLen and maxCnt in 1 loop, never though of that because I afraid something wrong and not clear, so I do 2 seperated loops.
I hope you’ll be doing Advent of Code solutions in a few days!
Best explanation!! Thank you so much for this!
Woah!!!
Best explanation!
wow this problem ruined my life
I was doing the same ques !
but I solved it :) but your explanation makes it crystal clear !
Wonderful explanation. I’m kind of new to problem solving. What’s a cache?
How will look the solution using BIT or segment tree?
Thanks 🙏 I needed this
You github link is not working anymore
couldn’t we solve this in O(n) time? by using the closing window approach and keeping track of the max length and count in a map, then increment that count in the map every time another LIS is found (while we are iterating the array)
nevermind, apparently increasing subsequence does not have to be contiguous in this problem
I love the energy
I love your videos and they are super super helpful!!! However, sometimes I do find your explanations just a little on the wordy side.. the best explanation still though!
can u make video for 332 Reconstruct Itinerary
Appreciated
so I think this is a bottom up dp?
please make a telegram group where we can ask doubt