Evaluate Division - Leetcode 399 - Python
Vložit
- čas přidán 8. 07. 2024
- Solving leetcode 399 - evaluate division, today's daily leetcode problem on may 19.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/evaluat...
0:00 - Read the problem
1:30 - Drawing Explanation
10:15 - Coding Explanation
leetcode 399
#neetcode #leetcode #python
This should be a "HARD" problem. Very important one though - many variations.
People have already thanked you for doing the daily LeetCode problems, but I just wanted to emphasize how truly helpful it is. I do each daily problem, and regardless of whether I can solve the problem myself or not, I come to watch your solution to get a better understanding. Your videos are helping me grow as a programmer and I greatly appreciate that. Thank you!
15:22 we are not doing it for fun got me
I am very happy that I solved such a tough problem on my own and that too the same way he explained😊
There is a more intuitive way to look at this problem (which leads to the same solution). Instead of a/b=2, b/c=3 consider equations a=2*b, b=3*c. And instead of solving the equation a/c=x, solve this one: a=x*c. The solution is quite intuitive: a = 2 * b = 2 * (3 * c) = 6 * c. The opposite direction is the same with different coefficients: c = 1/3 * b = 1/3 * (1/2 * a) = 1/6 * a.
Thank you for the daily leetcode problems!
Thanks man, your solutions are really high quality and well explained. Sometimes I think I don't really have to take LC premium and just solve the questions that you've solved already.
For anyone wants a DFS solution:
The idea is the same, mainly the base case, once we reach src == dst, we return 1, means we found the match.
And, if the src is not in the adjs, we'll return -1 immediately, another case is if the nei is not in the src's adjs, then we'll return -1 at the end of the for loop as well.
vector calcEquation(vector& equations, vector& values, vector& queries) {
unordered_map adjs;
for (int i = 0; i < equations.size(); i++) {
adjs[equations[i][0]].push_back({equations[i][1], values[i]});
adjs[equations[i][1]].push_back({equations[i][0], 1 / values[i]});
}
vector res;
for (auto q: queries) {
unordered_set visited;
double val = dfs(q[0], q[1], adjs, visited);
res.push_back(val);
}
return res;
}
double dfs(string src, string dst, unordered_map& adjs, unordered_set& visited) {
if (adjs.find(src) == adjs.end()) {
return -1;
}
// match found
if (src == dst) {
return 1;
}
visited.insert(src);
double res = 1;
for (auto nei: adjs[src]) {
// avoid loop, a -> b, b -> a.
if (visited.count(nei.first)) {
continue;
}
double t = dfs(nei.first, dst, adjs, visited);
if (t != -1) {
res = t * nei.second;
return res;
}
}
return -1;
}
thanks!
I watched it three times. I wouldn't know if I would be able to solve this problem without your explanation. maybe, after putting a lot of time into it. It's really awesome. Thanks a lot
Flawless explanation Sir!!
liked before watching, this problem drives me crazy :(
Very satisfying problem and nicely explained solution. Thank you!
class Solution {
public double[] calcEquation(List equations, double[] values, List queries) {
Map adj = new HashMap();
for (int i = 0; i < equations.size(); i++) {
List eq = equations.get(i);
String a = eq.get(0);
String b = eq.get(1);
double value = values[i];
adj.putIfAbsent(a, new ArrayList());
adj.putIfAbsent(b, new ArrayList());
adj.get(a).add(new Pair(b, value));
adj.get(b).add(new Pair(a, 1 / value));
}
double[] results = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
List q = queries.get(i);
String src = q.get(0);
String target = q.get(1);
results[i] = bfs(adj, src, target);
}
return results;
}
private double bfs(Map adj, String src, String target) {
if (!adj.containsKey(src) || !adj.containsKey(target)) {
return -1.0;
}
Queue queue = new LinkedList();
Set visited = new HashSet();
queue.add(new Pair(src, 1.0));
visited.add(src);
while (!queue.isEmpty()) {
Pair pair = queue.poll();
String node = pair.getKey();
double weight = pair.getValue();
if (node.equals(target)) {
return weight;
}
for (Pair neighbor : adj.get(node)) {
String nei = neighbor.getKey();
double neiWeight = neighbor.getValue();
if (!visited.contains(nei)) {
queue.add(new Pair(nei, weight * neiWeight));
visited.add(nei);
}
}
}
return -1.0;
}
}
i did this problem and came up with the exact logical approach you did using weights of the denominator stored in a dictionary. looks like your videos have rubbed off on me haha. i used dfs but i like your bfs version it seems easier to step through in an interview
Yours video is really helpful!! ❤ Thank you
Thanks to you I was able to better understand it and I finished it 5 minutes before the deadline.
God bless you!
Thank you
Yea im really weirded out by the x/x. My initial code can handle and return 1.
am i growing dumber by the day or are these medium questions becoming harder and harder. I couldn't even think of a brute-force solution :(
@NeetCodeIO were you able to solve this question on your own ?
no, i think this one is harder than usual mediums
U a Math God
Hi guys, just wondering how this gonna solev such edge cases:
1) [a/bc] = 2, query [a/cb] -- answer is 2, income is valid, but how we knew 'bc' is the same as 'cb'?
2) [ab/bc] = 2, query[a/c]. -- answer is 2, income is valid, how this approach solve it?
@NeetCodeIO pls help
Reading the desc gave me a headache 🤯🤯
If the interviewer, thinks that i came up with this solution by my own in the interview. Then i am not sure who is more dumb among us.
Great explanation! However, seems like variable visit was not maintained when BFS
2:12: me after getting the idea i can use graphs but dk how to code bfs/dfs for weighted directed graph
Could you please also post this today problem using union find, if possible.
Yeah, a solution for this problem with union find will be much appreciated
Bhai bfs se hi mushkil se huva abb union find kaha se lagaye
class Solution {
public:
typedef pairipair;
typedef double ll;
bool dfs(int node,int target,vectoradj,ll ans,vector&vis){
if(node==target)return 1;
vis[node]=1;
for(auto it:adj[node]){
ll child=it.first;
ll wt=it.second;
if(vis[child])continue;
ans*=wt;
if(dfs(child,target,adj,ans,vis))return 1;
}
return 0;
}
vector calcEquation(vector& equations, vector& values, vector& queries) {
int m=equations.size();
vectoradj(m);
mapmp;
int node=0;
for(int i=0;i
8:39 it's reciprocal not inverse
this is similar to the jane street mock interview
just woooo😱
This was solved in 1.5x :)
hey, do you know hindi ?
Aliens 👽👽 attendance taken by here :) :) :)
in test case : 1 the reason i think [ "x, "x" ] is -1.0 is because "x" doesn't exist in any of the equations.
java version here:
class Solution {
public double bfs(String src,String target,Map graph)
{
if(!graph.containsKey(src) || !graph.containsKey(target))
return -1.0;
if(src.equals(target)) {
return 1.0;
}
Queue q = new LinkedList();
q.add(new Pair(src,1.0));
Map visited = new HashMap();
while(!q.isEmpty())
{
Pair pair = q.poll();
String n = pair.getKey();
double w = pair.getValue();
visited.put(n,true);
if(n.equals(target)) return w;
for(String nei :graph.get(n).keySet())
{
if(!visited.containsKey(nei))
{
q.offer(new Pair(nei, w * graph.get(n).get(nei)));
visited.put(nei,true);
}
}
}
return -1;
}
public double[] calcEquation(List equations, double[] values, List queries) {
Map graph = new HashMap();
for(int i = 0;i < equations.size();i++)
{
List eq = equations.get(i);
String a = eq.get(0);
String b = eq.get(1);
if(!graph.containsKey(a)) graph.put(a,new HashMap());
graph.get(a).put(b,values[i]);
if(!graph.containsKey(b)) graph.put(b,new HashMap());
graph.get(b).put(a,1 / values[i]);
}
double[] res = new double[queries.size()];
Arrays.fill(res,-1.0);
for(int i = 0;i < queries.size();i++)
{
List query = queries.get(i);
String a = query.get(0);
String b = query.get(1);
res[i] = bfs(a,b,graph);
}
return res;
}
}
I think regardless of whether the number is in the question or not, if the number isn’t zero(which the description confirms), said number divided by itself should be zero
@@ladydimitrescu1155 number divided by itself should be 1, not zero
There is 0 chance you could solve this at an interview without knowing it prior. Even with hints, the question is so poorly phrased.
I just watched related topics as graph and I immediately got the intuition and logic for the problem.