Number of Good Leaf Nodes Pairs - Leetcode 1530 - Python

0:00 - Read the problem
2:30 - Drawing Explanation
5:05 - Coding Explanation
16:25 - Solution 2

leetcode 1530

#neetcode #leetcode #python

[NeetCodeIO]

btw I finally launched Python for coding interviews 🚀🚀 should i do Java for coding interviews next?

neetcode.io

[JamesBond-mqpd]

Even first solution is super clever. Incredible. i tried to crack this problem for 2 hours. and made very complex and slow solution

[MadpolygonDEV]

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 :/

[fancypants]

Thanks for including the BFS version also. I think it really enhances the learning & understanding.

[pritz]

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.

[anandsrikumar]

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.

[freecourseplatformenglish]

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.

[arihantsinghrana]

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

[abdallaahmed]

Can u make a playlist and explain the Data structure and algorithms?
Because there are not much good resources out there

[business_central]

Thanks for including the last solution, can someone tell me what was the time and space complexity of the last one?

[IK-xkex]

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!

[Itsme-hrhw]

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

[PhanNghia]

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 ?

[ZaneMouakket]

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

[prinksters]

can you please make a video on optimal account balancing i am so confused!!!!

[rahulsbhatt]

I didn't understand O(N * D^2) optimization

[GeetainSaar]

thaks khushi :)) you are so genius. ya thats me

[nikhil]

It's not what it looks like
-neetcode 2024

[aadil]

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;

};

[susdoge]

alright my trees and recursion is a mess