3244. Shortest Distance After Road Addition Queries II

3244. Shortest Distance After Road Addition Queries II | Weekly Leetcode 409

Рет қаралды 1,328

Күн бұрын

Пікірлер: 18

@Nishit_369 5 ай бұрын

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.

@nikhilsoni2403 5 ай бұрын

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 ..

@codingmohan 5 ай бұрын

Yes correct.

@princenagar1686 4 ай бұрын

Thanks that condition make this problem easy. Solved it after watching half video.

@sudhadevi6692 5 ай бұрын

Same as always Awesome lecture ❤

@souravshaw8904 5 ай бұрын

Great explanation 💯

@anonymous10906 5 ай бұрын

please make solution to yesterday's 4th ques

@kashishchawla2754 5 ай бұрын

pls make solution video yesterdays biweekly contest 4th question bhaiya:)

@nikhilsoni2403 5 ай бұрын

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)

@krrishnichanii3046 5 ай бұрын

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

@NikhilSoni-f1j 5 ай бұрын

@@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; } };

@codingmohan 5 ай бұрын

Yes, nice catch!

@ruturaj_dm 5 ай бұрын

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; }