Path Existence Queries in a Graph II | Leetcode 3534 | Binary Lifting | Concepts & Questions - 5

Whatsapp Community Link : https://www.whatsapp.com/channel/0029... 📹 Video Introduction Hi Everyone, this is the 5th video of our playlist “Binary Lifting – DP on Trees – Concepts & Questions” by codestorywithMIK. Binary Lifting -    • Introduction | Binary Lifting | DP On Tree...   Part I -    • Path Existence Queries in a Graph I | Mult...   In this video we tackle the LeetCode 3534 – “Path Existence Queries in a Graph II”. The problem can be solved elegantly with the Binary‑Lifting (Power‑of‑Two Jump) pattern - the same machinery used for k‑th ancestors and LCA. You will see the step‑by‑step reasoning that converts naïve approaches into an efficient solution, a complete dry‑run, and a ready‑to‑copy C++ and Java implementation (the Java version is identical). 🎯 What the Video Covers Three brute‑force approaches which will give TLE Intuition on why to Sort the nums and storing in arr Why we need efficient Jumping and what to store in ancestor table Building ancestor table using Binary Search and same recurrence relation Full story‑to‑code walkthrough (C++ / Java). 📂 Resources Video Name : Path Existence Queries in a Graph II | Leetcode 3534 | Binary Lifting Variation | Concepts & Questions - 5 | codestorywithMIK GitHub Code (C++/Java) : https://github.com/MAZHARMIK/Intervie... LeetCode Link : https://leetcode.com/problems/path-ex... Company Tags : Will update later 📚 Other Playlists (keep learning) DP Concepts Playlist :    • Roadmap for DP | How to Start DP ? | Topic...   Graph Concepts Playlist :    • Graph Concepts & Qns - 1 : Graph will no m...   Segment Tree Concepts Playlist :    • Segment Tree | Introduction | Basics | Bui...   Recursion Concepts Playlist :    • Introduction | Recursion Concepts And Ques...   Trie Playlist :    • Word Search II | Leetcode 212 | Detailed |...   Difference‑Array Technique :    • Introduction | What | How | Difference Arr...   Line‑Sweep Technique :    • Introduction | What | Why | Line Sweep Tec...   Top K from Sorted Structures Pattern :    • Introduction | Top K from Sorted Structure...   Small Dopamine Java Videos :    • Small Java Dopamine Videos | codestorywithMIK   GitHub Repo (full interview prep) : https://github.com/MAZHARMIK/Intervie... Social - Instagram :   / codestorywithmik   Facebook :   / 100090524295846   Twitter :   / cswithmik   Subscribe :    / @codestorywithmik   ╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗ ║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣ ╠╗║╚╝║║╠╗║╚╣║║║║║═╣ ╚═╩══╩═╩═╩═╩╝╚╩═╩═╝ 📝 Video Summary Building the graph directly is impossible — with n up to 1e5, close-in-value nodes create up to O(n²) edges — so instead sort the nodes by value; once sorted, everything reachable from a node forms a contiguous range. Pre-process into a binary-lifting table where ancestorTable[node][j] stores the farthest sorted position reachable from node in exactly 2^j maximal hops. Column 0 (one hop) is found with binary search - the rightmost position whose value is within maxDiff of value[node]; every higher column is built with the doubling recurrence ancestorTable[node][j] = ancestorTable[ ancestorTable[node][j-1] ][j-1]. For each query, map both original nodes to their sorted positions, swap so we always move right, then greedily take the largest jump that stays strictly before b, accumulating 2^j into the hop count each time. The answer is jumps + 1 if one final single hop reaches b; otherwise a value gap wider than maxDiff blocks the path and the answer is -1 (and 0 when a equals b). Complexities – Pre-processing: O(N log N) time & O(N log N) space. Each query: O(log N) time, O(1) extra space. ✨ Timelines✨ 00:00 - Introduction 00:10 - Motivation 03:46 - Problem Explanation + Brute Forces 19:57 - Why Binary Lifting ? 28:23 - Building Ancestor Table 44:08 - Applying Binary Lifting for query 01:00:49 - Coding it up #BinaryLifting #DPOnTrees #AncestorTable #KthAncestor #LCA #TreeQueries #Heap #PriorityQueue #CodingInterview #LeetCode #Hackerrank #DataStructures #Algorithms #InterviewPrep #TechInterview #CodestorywithMIK #Hinglish #CompetitiveProgramming #SoftwareEngineer #LearningTogether #100DaysOfCode #GrowthMindset #YouTubeEducation #ContentCreator #MIK #mik #TopK #TopKPatterns #coding #leetcode #dsa #dsalgo #interviewpreparation #algorithms #priorityqueue #heappatterns #topkproblems #bestfirstsearch #matrixproblems #pairsums #subarraysums #mergeksortedlists #kthsmallest #codestorywithmik #developers #careergoals #careerdevelopment #youtubeeducation #contentcreator #BinaryLifting #DPOnTrees #AncestorTable #LCA #NumberOfWays #BinaryLiftingTemplate #CodingInterview #LeetCode #Hackerrank #DataStructures #Algorithms