A-C | Leetcode Weekly Contest 409 Editorials | Shortest Distance After Road Addition Queries

Subscribe to the channel for Amazing Coding and Competitive Programming Content.

👉🏻 Coding Profiles

👉🏻 Connect with Me

coding
programming
competitive programming
software developer
software engineer
interview preparation
interview experience
dsa

Leetcode Weekly Contest 409 Editorials
Leetcode Weekly Contest 409
Leetcode Weekly Contest 409 solutions
3244. Shortest Distance After Road Addition Queries II
3244. Shortest Distance After Road Addition Queries II leetcode
3244. Shortest Distance After Road Addition Queries II leetcode solution
3244. Shortest Distance After Road Addition Queries II leetcode editorial
3244. Shortest Distance After Road Addition Queries II editorial
3244. Shortest Distance After Road Addition Queries II solution
3243. Shortest Distance After Road Addition Queries I
3243. Shortest Distance After Road Addition Queries I leetcode
3243. Shortest Distance After Road Addition Queries I leetcode solution
3243. Shortest Distance After Road Addition Queries I leetcode editorial
3243. Shortest Distance After Road Addition Queries I editorial
3243. Shortest Distance After Road Addition Queries I solution
3242. Design Neighbor Sum Service
3242. Design Neighbor Sum Service leetcode
3242. Design Neighbor Sum Service leetcode editorial
3242. Design Neighbor Sum Service leetcode solution
3242. Design Neighbor Sum Service editorial
3242. Design Neighbor Sum Service solution

00:00 Introduction
01:00 Design Neighbor Sum Service
03:57 Shortest Distance After Road Addition Queries I
08:00 Shortest Distance After Road Addition Queries II
13:28 Outro

[TanmayKhandelwal-zv]

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<=3 or x<=3&&y>=7

[nikhil_squats]

why dijkstra, use BFS, as edges are unit weights

[lucifer]

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.

[tanmoysaha]

Solutions were crisp and concise. easy to understand for a beginner too.

[yashtiwari]

I used brute force approach for question 4
But TLE maar gaya 😂
#include <vector>

using namespace std;

class Solution {
public:
vector<int> colors, vector<vector<int>>& queries) {
vector<int> 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 <= n) {
for (int start = 0; start < n; ++start) {
bool is_alternating = true;

for (int i = 0; i < k - 1; ++i) {
int current = (start + i) % n;
int next = (start + i + 1) % n;
if (colors[current] == colors[next]) {
is_alternating = false;
break;
}
}

if (is_alternating) {
++count;
}
}
}

ans.push_back(count);
}
}

return ans;
}
};

[tusharparakh]

what an amazing solution for the third one! your approaches are always intuitive and fresh!

[nik]

sir map toh 3 value ka liya h or dali usme index h
ki value h 3 value kha dali

[aviksain]

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

[beasttclub]

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

[yogeshrajput]

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

[Kaiser_Kroos]

Sir, can we solve the 3rd question using segment tree?

[ReeshuDigit]

Helpful. keep it bro..very helpful for people like us

[harchitgulati]

your approaches intuitive thnx a lot for uploading

[Ujvall]

Why we are finding lower bound and upper Bound

[indianathena]

Can we not solve 2 and 3 using approach for Jump game standard question?

If not, why?

[vaidehikoparde]

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.