The constraints made me think of Snakes and Ladders. Q2 is the classic game where you are curently climbing a small ladder but you know that 3 or 4 steps ahead there was a bigger ladder that could shorten your journey from 0 to 100. On the other hand, Q3 is more like a modified game of SnL where no ladder paths overlap or maybe all ladders are sequentially placed except that they may start and end at same cells. Great Problem and great explanation.
You can actually do it in linear time by using a linked list and deleting nodes in the middle of two nodes between which a new edge is added because the points in between are useless now. Initially set the distance betweem the node 0 and node 'n-1' to be n-1. And as you delete each node in the linked list,You just decrement the distance counter. Since each node is deleted only once. The time complexity should be O(Q+N)
I also tried this but it is giving TLE , how did u delete the nodes in between in less than O(N) , because even for the intervals which are already deleted we have to check if they exist in the ll or not . Please explain
@@krrishnichanii3046 Actually i didnt use linked list, but used the same idea and did it without linked lists in linear time: C++ code : int pointsTo[100000]; bool gone[100000]; class Solution { public: vector shortestDistanceAfterQueries(int n, vector& queries) { int shortest = n - 1, left, right; vector answers(queries.size()); for (int i = 1; i < n; ++i) { pointsTo[i - 1] = i; gone[i] = false; } for (int q = 0; q != queries.size(); ++q) { left = queries[q][0]; right = queries[q][1]; if (gone[left] || pointsTo[left] > right) { answers[q] = shortest; continue; } while (pointsTo[left] != right) { gone[pointsTo[left]] = true; pointsTo[left] = pointsTo[pointsTo[left]]; --shortest; } answers[q] = shortest; } return answers; } };
Here is a simple solution using Map. Trying to mock the behavior of a LinkedList. public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] ans = new int[queries.length]; int iAns = 0; //Maintain currNode to nextNode map Map connectionMap = new HashMap(); for (int i = 0; i < n-1; i++) { connectionMap.put(i, i+1); } for (int[] query : queries) { int u = query[0]; int v = query[1]; //Update connections if (connectionMap.containsKey(u)) { int temp = connectionMap.get(u); while (temp < v) { int next = connectionMap.get(temp); connectionMap.remove(temp); connectionMap.put(u, next); temp = next; } }
21:54 i think its because we cannot iterate on a set or a map and delete elements from it at the same time. I think it changes the structure of the tree in the internal implementation or something like that, which causes a runtime error. I am not completely sure tho...Please correct me if i am wrong ..
Thanks that condition make this problem easy. Solved it after watching half video.
The constraints made me think of Snakes and Ladders. Q2 is the classic game where you are curently climbing a small ladder but you know that 3 or 4 steps ahead there was a bigger ladder that could shorten your journey from 0 to 100. On the other hand, Q3 is more like a modified game of SnL where no ladder paths overlap or maybe all ladders are sequentially placed except that they may start and end at same cells. Great Problem and great explanation.
Same as always Awesome lecture ❤
Great explanation 💯
You can actually do it in linear time by using a linked list and deleting nodes in the middle of two nodes between which a new edge is added because the points in between are useless now. Initially set the distance betweem the node 0 and node 'n-1' to be n-1. And as you delete each node in the linked list,You just decrement the distance counter. Since each node is deleted only once. The time complexity should be O(Q+N)
I also tried this but it is giving TLE , how did u delete the nodes in between in less than O(N) , because even for the intervals which are already deleted we have to check if they exist in the ll or not . Please explain
@@krrishnichanii3046 Actually i didnt use linked list, but used the same idea and did it without linked lists in linear time: C++ code :
int pointsTo[100000];
bool gone[100000];
class Solution {
public:
vector shortestDistanceAfterQueries(int n, vector& queries) {
int shortest = n - 1, left, right;
vector answers(queries.size());
for (int i = 1; i < n; ++i) {
pointsTo[i - 1] = i;
gone[i] = false;
}
for (int q = 0; q != queries.size(); ++q) {
left = queries[q][0];
right = queries[q][1];
if (gone[left] || pointsTo[left] > right) {
answers[q] = shortest;
continue;
}
while (pointsTo[left] != right) {
gone[pointsTo[left]] = true;
pointsTo[left] = pointsTo[pointsTo[left]];
--shortest;
}
answers[q] = shortest;
}
return answers;
}
};
Yes, nice catch!
Here is a simple solution using Map. Trying to mock the behavior of a LinkedList.
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
int[] ans = new int[queries.length];
int iAns = 0;
//Maintain currNode to nextNode map
Map connectionMap = new HashMap();
for (int i = 0; i < n-1; i++) {
connectionMap.put(i, i+1);
}
for (int[] query : queries) {
int u = query[0];
int v = query[1];
//Update connections
if (connectionMap.containsKey(u)) {
int temp = connectionMap.get(u);
while (temp < v) {
int next = connectionMap.get(temp);
connectionMap.remove(temp);
connectionMap.put(u, next);
temp = next;
}
}
ans[iAns++] = connectionMap.size();
}
return ans;
}
please make solution to yesterday's 4th ques
21:54 i think its because we cannot iterate on a set or a map and delete elements from it at the same time. I think it changes the structure of the tree in the internal implementation or something like that, which causes a runtime error. I am not completely sure tho...Please correct me if i am wrong ..
Yes correct.
pls make solution video yesterdays biweekly contest 4th question bhaiya:)
This is one of the underrated channels. Very good explanation. Also if you do
while(it!=all.end() && *it
Where r u incrementing the pointer?
ngl, i actually thought of this approach, but noob me thought this will be an obvious TLE, so i just skipped this idea and went towards graphs.
Happens to all of us.
Next time before tracking back, try to write the rough pseudocode and it would help avoid these kind of issues to some extent.