The main observation in question 3 was ->There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]. as if there is a query 3,7 then no query will intersect its middle elements...means its like x,y
@@AbhinavAwasthi Great video editorial Sir!! But, what was the intuition of using a set in problem 3 ? The middle nodes are of no use to me for calculating the shortest path, that's OK, but how to proceed from this observation to actually implementing the solution ??
@@priyanshkumar17 because we only want unique paths + the paths are from 0 to n-1 therefore it makes more sense & the most important the way we are erasing the elements in between can only be done by set with small code size , inbuilt functions and without any heavy logic/implementation to perform this logic in comparison to using any other data structure . Simply , set for crispier , clearer & concise soln ; )
There is one differece between between question2 and 3 is that question2 can have overlapping edges in queries but question3 can't Thats way question3 solution 3 solution is not working for question2
you are not mention important condition in question3 , what if 2 queries are intersect to each other . this solution is only valid if no queries intersect each other.
If you see the constraints of the problem, it is already mentioned that: There are no two queries such that i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].
You can solve it by using DP but the problem is Time complexity. In Jump game problem you just traverse the array only once but here you need to traverse for each queries that has been added new...The nodes are just assumed like index you can indeed traverse..But again time complexity.. Problem 2 can be solved but problem 3 is heavy constraint...
i was expectiong solutions of 410th contest but i am really disappointed and i am still unable to solve 2nd problem of the contest please post solution of the contest if you really want to help the community
I used brute force approach for question 4 But TLE maar gaya 😂 #include using namespace std; class Solution { public: vector numberOfAlternatingGroups(vector& colors, vector& queries) { vector ans; int n = colors.size(); for (const auto& query : queries) { if (query[0] == 2) { colors[query[1]] = query[2]; } else if (query[0] == 1) { int k = query[1]; int count = 0; if (k
this is not actual or right explanation for b problem however code is right, and explanation is valid for c problem because question mention "There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]." but for b problem explanation is wrong ,suggests not go through this explanation
The lower and upper bound functions are implemented as follows : lower_bound(value): Returns an iterator pointing to the first element in the set that is not less than (i.e., greater or equal to) the given value. upper_bound(value): Returns an iterator pointing to the first element in the set that is greater than the given value. We aren't finding upper_bound of 8 or lower_bound of 3, instead, if you observe the parameters passed to the functions carefully, we find the upper bound of 7 which is in this case 7, and the lower bound of 4 which is 4 in this case. Please don't encourage students to blindly copy solutions without understanding them. And as an educator, it is your most crucial responsibility to share the correct information. Please do not rob students of an opportunity to deepen their conceptual understanding and learn accurate facts.
Hey, I think you watched the incomplete video, I corrected my mistake later in the video I think, an educator can also make some mistakes sometimes, but I have fixed it later, can you please watch completely Also, I totally understand the meaning of lower and upper bound
The main observation in question 3 was ->There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]. as if there is a query 3,7 then no query will intersect its middle elements...means its like x,y
Kuch doubt ke answer comment me mil jate hai 😃. i tested this 3rd solution in 2nd but wo queries wala samj hi nai aya us chakkar me it was WA.
Yes, right
Very Very Helpful...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Glad you loved it, thanks
Thanks for 3rd explanation sir !!
Welcome
@@AbhinavAwasthi Great video editorial Sir!! But, what was the intuition of using a set in problem 3 ? The middle nodes are of no use to me for calculating the shortest path, that's OK, but how to proceed from this observation to actually implementing the solution ??
@@priyanshkumar17 because we only want unique paths + the paths are from 0 to n-1 therefore it makes more sense & the most important the way we are erasing the elements in between can only be done by set with small code size , inbuilt functions and without any heavy logic/implementation to perform this logic in comparison to using any other data structure . Simply , set for crispier , clearer & concise soln ; )
@@RajeevCanDev thanks 🙏
Solutions were crisp and concise. easy to understand for a beginner too.
Thanks a lot
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Glad you loved it, thanks
Tq for the explanation ❤
Glad you loved it, welcome
your approaches intuitive thnx a lot for uploading
Glad you loved it, thanks
what an amazing solution for the third one! your approaches are always intuitive and fresh!
Glad you loved it, thanks
It was very helpful!!
Glad you loved it, thanks
Helpful. keep it bro..very helpful for people like us
Glad you loved it, thanks
Nice Explanation Sir !!
Thanks bhai
great work
Glad you loved it, thanks
There is one differece between between question2 and 3 is that
question2 can have overlapping edges in queries but question3 can't
Thats way question3 solution 3 solution is not working for question2
Right!!
you are not mention important condition in question3 , what if 2 queries are intersect to each other . this solution is only valid if no queries intersect each other.
If you see the constraints of the problem, it is already mentioned that:
There are no two queries such that i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].
Sir, can we solve the 3rd question using segment tree?
Actually I tried solving, maybe it can be done, but it's not required because better ways are present
why dijkstra, use BFS, as edges are unit weights
Why we are finding lower bound and upper Bound
Can we not solve 2 and 3 using approach for Jump game standard question?
If not, why?
You can solve it by using DP but the problem is Time complexity. In Jump game problem you just traverse the array only once but here you need to traverse for each queries that has been added new...The nodes are just assumed like index you can indeed traverse..But again time complexity.. Problem 2 can be solved but problem 3 is heavy constraint...
Can you share the complete logic
i was expectiong solutions of 410th contest but i am really disappointed and i am still unable to solve 2nd problem of the contest
please post solution of the contest if you really want to help the community
I used brute force approach for question 4
But TLE maar gaya 😂
#include
using namespace std;
class Solution {
public:
vector numberOfAlternatingGroups(vector& colors, vector& queries) {
vector ans;
int n = colors.size();
for (const auto& query : queries) {
if (query[0] == 2) {
colors[query[1]] = query[2];
}
else if (query[0] == 1) {
int k = query[1];
int count = 0;
if (k
Due to n3
Ohh, yeah time complexity is higher
this is not actual or right explanation for b problem however code is right, and explanation is valid for c problem because question mention "There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]." but for b problem explanation is wrong ,suggests not go through this explanation
sir map toh 3 value ka liya h or dali usme index h
ki value h 3 value kha dali
How to come up with intuition for q3?
It was an observation based solution, so try to write things on paper and think
The lower and upper bound functions are implemented as follows :
lower_bound(value): Returns an iterator pointing to the first element in the set that is not less than (i.e., greater or equal to) the given value.
upper_bound(value): Returns an iterator pointing to the first element in the set that is greater than the given value.
We aren't finding upper_bound of 8 or lower_bound of 3, instead, if you observe the parameters passed to the functions carefully, we find the upper bound of 7 which is in this case 7, and the lower bound of 4 which is 4 in this case. Please don't encourage students to blindly copy solutions without understanding them. And as an educator, it is your most crucial responsibility to share the correct information. Please do not rob students of an opportunity to deepen their conceptual understanding and learn accurate facts.
Hey, I think you watched the incomplete video, I corrected my mistake later in the video
I think, an educator can also make some mistakes sometimes, but I have fixed it later, can you please watch completely
Also, I totally understand the meaning of lower and upper bound
@@AbhinavAwasthi I always see your editorials sir..Your explainations are best..Please dont mind his /her language..You explaination is correct..
watch complete video bro