📅 GeeksforGeeks Problem of the Day | Smallest Range in K Lists | 16-May-2025 💻
🔍 Find the minimum window that includes at least one number from each of the K sorted lists!
📘 Concept: Min-Heap + Sliding Window + Range Tracking
⚡ Learn how to solve complex multi-list range problems using heaps, dry runs, and boundary handling.
📌 Problem:
Given a 2D array of K sorted lists (each of size N), find the smallest range [l, r] such that at least one element from each of the K lists lies in this range.
🧠 Examples:
Input:
[[4, 7, 9, 12, 15], [0, 8, 10, 14, 20], [6, 12, 16, 30, 50]]
Output: [6, 8]
Input:
[[1, 3, 5, 7, 9], [0, 2, 4, 6, 8], [2, 3, 5, 7, 11]]
Output: [1, 2]
✅ What you'll learn in this video:
Efficient approach using min-heap to track smallest elements
Maintaining current max across lists to form window
Conditions for updating smallest valid range
Complete dry run for intuitive understanding
Code walkthrough in both C++ and Java
Applications in streaming, merging, and K-way search problems
📂 GitHub Code: https://github.com/imnilesh18/GfG-POT...
🔗 Full Playlist: https://github.com/imnilesh18/GfG-POTD
📢 Don’t forget to Like, Comment, and Subscribe to keep up with daily DSA content and interview prep tips!
🔖 Tags:
#gfgpotd #smallestrange #minheap #kwaymerge #cpp #java #dryrun #interviewprep #codingchallenge #geeksforgeeks #NileshCodes
コメント