Please share anything you think it may help us to understand how to play the interview games! I was very sacry about interviews until I started watching yours. So I believe everything you shared did help!
@@arihantsinghrana2173 there is plenty of work in cpp ofc, but you have to be very good at it if you want a job for it, dsa c++ barely scratches the surface of how skilled one needs to be with cpp to get a job.
omg, my initial intuition had this solution but i disregarded it and thought, no way we combine lists and compare distances every level. Theres probably a smarter solution :/
Add this line :- if d1 >= distance : continue before the for loop of d2. This will improve the time complexity significantly. My submission beats % went from 37 to 95 by this single change.
I submitted 10+ times, at last my submission was accepted. I discovered a technique with iteration. I will calculate the distances while doing dfs itself.
I originally made the bfs graph solution with the optimization you made at 19:50. After including that optimization the time complexity would be O(n(2^d)), right? This would be better than O(n^2).
Honestly I think I would reject this graph solution if I were an interviewer. I don't think building a whole new graph from a tree is a proper solution here.
i don't know why we require to return list, i mean we can customize the function and only return number of leaf nodes which have depth less than equal to distance and then for multiply left and right and then add to the totalPairs
I was thinking the same and then asked ChatGPT, which helped with understanding that just returning the leaf nodes isn't correct because we need the distance between the leaf nodes and not the count. Following is what chatGPT gave: Let's take an example: 1 / \ 2 3 / \ \ 4 5 6 Leaf Nodes and Distances Leaf nodes: 4, 5, 6 Distances from the root: Distance from 1 to 4: 2 Distance from 1 to 5: 2 Distance from 1 to 6: 2 Given Distance = 3 Now, let's try counting pairs of leaf nodes such that the distance between them is less than or equal to 3. Direct Multiplication of Counts If we only count the number of leaf nodes in each subtree and multiply them directly: Leaf nodes in the left subtree (nodes 2, 4, 5): 2 (nodes 4 and 5) Leaf nodes in the right subtree (nodes 3, 6): 1 (node 6) Multiplying these counts: Pairs=2×1=2 However, this approach fails to consider the actual distances between leaf nodes. The correct count should be based on valid distances between the pairs. Correct Pair Counting with Distances Using the distances: Distances from leaf nodes in the left subtree to the root (1): [2, 2] Distances from leaf nodes in the right subtree to the root (1): [2] Now we need to check the pairs: Pair (4, 6): Distance = 2 + 2 = 4 (not a valid pair since 4 > 3) Pair (5, 6): Distance = 2 + 2 = 4 (not a valid pair since 4 > 3) None of these pairs are valid according to the given distance constraint (3). Correct Solution By considering actual distances, the number of valid pairs is 0, not 2.
I'm sorry but the hash_map solution seem weird, isn't we just need to remove all the value d + 1 that surpass distance ? Anyway, about all_dist[d + 1] = left_dict[ d + 1] feel so wrong, left_dict[d + 1] should be 0 right ?
its all about practise and we need to solve a certain amount of problems to get that level of intuition its just a matter of time and practise you could come up with such unique approaches. Try solving neetcode 150 problems it really helped me to build a intuition for the new problems.
I solved it with 10*n^2 time complexity and it gave me time limit exceed but it gets accepted for n^3 why? Can somebody tell me if I am right about my time and space complexity? here's the code: /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} distance * @return {number} */ var countPairs = function(root, distance) { // create parent binding // get all the leaf node in pre-order-traversal order. // try to get each node to the right of it and see if it's a good node. // a bfs helper function which takes src and target and gives as all the possible good nodes. const bindTree = (root) => { const dfs = (node, pre) => { if(!node) return; node.parent = pre; dfs(node.left, node); dfs(node.right, node); } dfs(root, null); } const getLeafNodes = (root) => { const leafNodes = []; const dfs = (node) => { if(!node.left && !node.right) { leafNodes.push(node); return; } node.left && dfs(node.left); node.right && dfs(node.right); } dfs(root); return leafNodes; } const shortestPath = (src, target, limit) => { const bfs = (node) => { const q = new Queue(); const visited = new Set(); q.enqueue([src, 0]); while(!q.isEmpty()) { const [node, currDistance] = q.dequeue(); visited.add(node);
If you wanna declare a class variable, you don't need to use self. So your original code would work, if you deleted self from the topmost declaration of pairs variable
btw I finally launched Python for coding interviews 🚀🚀 should i do Java for coding interviews next?
neetcode.io
Definitely yes
Please share anything you think it may help us to understand how to play the interview games!
I was very sacry about interviews until I started watching yours. So I believe everything you shared did help!
Is C++ also required by the industries ? or is it just helpful for competitive programming?
@@arihantsinghrana2173 there is plenty of work in cpp ofc, but you have to be very good at it if you want a job for it, dsa c++ barely scratches the surface of how skilled one needs to be with cpp to get a job.
cpp
Even first solution is super clever. Incredible. i tried to crack this problem for 2 hours. and made very complex and slow solution
Thanks for including the BFS version also. I think it really enhances the learning & understanding.
omg, my initial intuition had this solution but i disregarded it and thought, no way we combine lists and compare distances every level. Theres probably a smarter solution :/
Add this line :-
if d1 >= distance :
continue
before the for loop of d2. This will improve the time complexity significantly. My submission beats % went from 37 to 95 by this single change.
You are right! This one is actually pretty good! Helped the solution reach 90ms from 124 ms.
@@rahulsbhatt yeah, we are skipping useless iterations in this case.
I am really happy that I almost solved it on my own with optimized solution. There was a little bug but your video helped me fix it.
I submitted 10+ times, at last my submission was accepted. I discovered a technique with iteration. I will calculate the distances while doing dfs itself.
Best professor
Waking up in the morning to your video is one of the best things I do the whole day!! Thanks for your Daily uploads and keep up the great work!!
Thanks for including the last solution, can someone tell me what was the time and space complexity of the last one?
Thank you bro. You save my day.
Can u make a playlist and explain the Data structure and algorithms?
Because there are not much good resources out there
First!!🎉
And the award goes to....
Great explaination as always
I originally made the bfs graph solution with the optimization you made at 19:50. After including that optimization the time complexity would be O(n(2^d)), right?
This would be better than O(n^2).
Or it's O(n*max(n,2^d))
can you please make a video on optimal account balancing i am so confused!!!!
I think graph solution is not appropriate for that problem, because it doesn't state that node values are unique. Thank you for the solution!
Honestly I think I would reject this graph solution if I were an interviewer. I don't think building a whole new graph from a tree is a proper solution here.
It does work with repeated nodes bcs python gives diffrent hashes for diffrent objects even if they have the same structure
Thanks man!!
i don't know why we require to return list, i mean we can customize the function and only return number of leaf nodes which have depth less than equal to distance and then for multiply left and right and then add to the totalPairs
I was thinking the same and then asked ChatGPT, which helped with understanding that just returning the leaf nodes isn't correct because we need the distance between the leaf nodes and not the count.
Following is what chatGPT gave:
Let's take an example:
1
/ \
2 3
/ \ \
4 5 6
Leaf Nodes and Distances
Leaf nodes: 4, 5, 6
Distances from the root:
Distance from 1 to 4: 2
Distance from 1 to 5: 2
Distance from 1 to 6: 2
Given Distance = 3
Now, let's try counting pairs of leaf nodes such that the distance between them is less than or equal to 3.
Direct Multiplication of Counts
If we only count the number of leaf nodes in each subtree and multiply them directly:
Leaf nodes in the left subtree (nodes 2, 4, 5): 2 (nodes 4 and 5)
Leaf nodes in the right subtree (nodes 3, 6): 1 (node 6)
Multiplying these counts:
Pairs=2×1=2
However, this approach fails to consider the actual distances between leaf nodes. The correct count should be based on valid distances between the pairs.
Correct Pair Counting with Distances
Using the distances:
Distances from leaf nodes in the left subtree to the root (1): [2, 2]
Distances from leaf nodes in the right subtree to the root (1): [2]
Now we need to check the pairs:
Pair (4, 6): Distance = 2 + 2 = 4 (not a valid pair since 4 > 3)
Pair (5, 6): Distance = 2 + 2 = 4 (not a valid pair since 4 > 3)
None of these pairs are valid according to the given distance constraint (3).
Correct Solution
By considering actual distances, the number of valid pairs is 0, not 2.
A Biggg Yesss for java
I'm sorry but the hash_map solution seem weird, isn't we just need to remove all the value d + 1 that surpass distance ?
Anyway, about all_dist[d + 1] = left_dict[ d + 1] feel so wrong,
left_dict[d + 1] should be 0 right ?
thaks khushi :)) you are so genius. ya thats me
I didn't understand O(N * D^2) optimization
Can anyone tell me how does one come up with a recursive solution for a problem like this
its all about practise and we need to solve a certain amount of problems to get that level of intuition its just a matter of time and practise you could come up with such unique approaches. Try solving neetcode 150 problems it really helped me to build a intuition for the new problems.
I solved it with 10*n^2 time complexity and it gave me time limit exceed but it gets accepted for n^3 why? Can somebody tell me if I am right about my time and space complexity? here's the code:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} distance
* @return {number}
*/
var countPairs = function(root, distance) {
// create parent binding
// get all the leaf node in pre-order-traversal order.
// try to get each node to the right of it and see if it's a good node.
// a bfs helper function which takes src and target and gives as all the possible good nodes.
const bindTree = (root) => {
const dfs = (node, pre) => {
if(!node) return;
node.parent = pre;
dfs(node.left, node);
dfs(node.right, node);
}
dfs(root, null);
}
const getLeafNodes = (root) => {
const leafNodes = [];
const dfs = (node) => {
if(!node.left && !node.right) {
leafNodes.push(node);
return;
}
node.left && dfs(node.left);
node.right && dfs(node.right);
}
dfs(root);
return leafNodes;
}
const shortestPath = (src, target, limit) => {
const bfs = (node) => {
const q = new Queue();
const visited = new Set();
q.enqueue([src, 0]);
while(!q.isEmpty()) {
const [node, currDistance] = q.dequeue();
visited.add(node);
if(currDistance > limit) continue;
if(node === target) return true;
// add neighbor nodes.
if(node.left && !visited.has(node.left)) {
q.enqueue([node.left, currDistance+1]);
}
if(node.right && !visited.has(node.right)) {
q.enqueue([node.right, currDistance+1]);
}
if(node.parent && !visited.has(node.parent)) {
q.enqueue([node.parent, currDistance+1]);
}
}
return false;
}
if(bfs(src)) return true;
return false;
}
bindTree(root);
const leafNodes = getLeafNodes(root);
let goodPairs = 0;
for(let i = 0; i < leafNodes.length; i++) {
const srcNode = leafNodes[i];
for(let j = i+1; j < leafNodes.length; j++) {
const targetNode = leafNodes[j];
if(shortestPath(srcNode, targetNode, distance)) {
goodPairs++;
}
}
}
return goodPairs;
};
It's not what it looks like
-neetcode 2024
alright my trees and recursion is a mess
What tool do you use to explain the solution?
i believe its one note
paint 3D
If you wanna declare a class variable, you don't need to use self. So your original code would work, if you deleted self from the topmost declaration of pairs variable
Day 2 of asking #987 explanation
"leaf nodeS pairS" 🤣🤣🤣
shame shame shame!!!! NO JAVA However course corrected so all good