We create a merged list containing all elements from the input lists, each paired with the index of its originating list. This prepares for sorting and sliding window operations.
💡 Merging all elements into one list with their source indices allows us to handle all values uniformly and track coverage of each list.
Line:for i, lst in enumerate(nums):
for val in lst:
merged.append((val, i))
💡 This step sets up the data structure needed to apply the two-pointer sliding window technique across all lists simultaneously.
setup
Sort the merged list by element value
We sort the merged list by the element values to enable the sliding window to move over a sorted sequence, which is essential for finding the smallest range.
💡 Sorting ensures the window moves over elements in ascending order, making it easier to find minimal ranges.
Line:merged.sort(key=lambda x: x[0])
💡 Sorted order allows the two pointers to efficiently explore candidate ranges without missing smaller ones.
setup
Initialize pointers and counters
We initialize the left pointer at index 0, the right pointer will start moving from 0, and counters to track how many lists are covered in the current window.
💡 Setting up pointers and counters is crucial for managing the sliding window and coverage tracking.
Line:left = 0
count = Counter()
have = 0
need = k
min_range = float('inf')
res = []
💡 These variables control the window boundaries and track coverage to find valid ranges.
expand
Expand right pointer to include (0,1)
We move the right pointer to index 0, include element 0 from list 1, and update coverage count. Since this is the first element from list 1, coverage increases.
💡 Expanding right pointer adds elements to the window, increasing coverage of lists.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Including a new list's element increases 'have', moving closer to covering all lists.
expand
Expand right pointer to include (4,0)
Right pointer moves to index 1, adding element 4 from list 0. This is the first element from list 0, so coverage increases again.
💡 Each new list element included increases coverage until all lists are covered.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Coverage now includes lists 0 and 1, still missing list 2.
expand
Expand right pointer to include (5,2)
Right pointer moves to index 2, adding element 5 from list 2. This completes coverage of all three lists, so 'have' equals 'need'.
💡 Once all lists are covered, we can try to shrink the window to find smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 The window now covers all lists, enabling range evaluation and potential shrinking.
shrink
Evaluate and shrink window from left
Since all lists are covered, we check if the current window [0,2] is smaller than the previous best. It is, so we update the smallest range to [0,5]. Then we shrink from the left by removing element (0,1).
💡 Shrinking the window tries to find a smaller valid range while maintaining coverage.
Line:while have == need:
left_val, left_idx = merged[left]
if val - left_val < min_range:
min_range = val - left_val
res = [left_val, val]
count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
💡 Shrinking from left can reduce range size but risks losing coverage, so we track coverage carefully.
expand
Expand right pointer to include (9,1)
Right pointer moves to index 3, adding element 9 from list 1. Coverage for list 1 increases again, but since it was already covered, 'have' remains the same.
💡 Expanding right pointer continues to explore new ranges and possibly regain coverage lost by shrinking.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Adding elements from already covered lists keeps coverage stable but may help find smaller ranges.
shrink
Shrink window from left to [4,9]
We shrink the window by moving left pointer from index 1 to 2, removing element (4,0). Coverage for list 0 decreases but remains covered because count is still positive.
💡 Shrinking tries to minimize the range while maintaining coverage.
Line:count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
💡 Coverage counts allow safe shrinking without losing coverage prematurely.
expand
Expand right pointer to include (10,0)
Right pointer moves to index 4, adding element 10 from list 0. Coverage for list 0 increases again, maintaining full coverage.
💡 Expanding right pointer explores new elements to find potentially smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Coverage remains full, allowing further shrinking attempts.
shrink
Shrink window from left to [5,10]
We shrink the window by moving left pointer from index 2 to 3, removing element (5,2). Coverage for list 2 decreases but remains covered because count is still positive.
💡 Shrinking continues to try to minimize the range while keeping coverage intact.
Line:count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
💡 Coverage counts allow safe shrinking without losing coverage prematurely.
expand
Expand right pointer to include (12,1)
Right pointer moves to index 5, adding element 12 from list 1. Coverage for list 1 increases again, maintaining full coverage.
💡 Expanding right pointer explores new elements to find potentially smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Coverage remains full, allowing further shrinking attempts.
expand
Expand right pointer to include (15,0)
Right pointer moves to index 6, adding element 15 from list 0. Coverage for list 0 increases again, maintaining full coverage.
💡 Expanding right pointer explores new elements to find potentially smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Coverage remains full, allowing further shrinking attempts.
expand
Expand right pointer to include (18,2)
Right pointer moves to index 7, adding element 18 from list 2. Coverage for list 2 increases again, maintaining full coverage.
💡 Expanding right pointer explores new elements to find potentially smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
💡 Coverage remains full, allowing further shrinking attempts.
expand
Expand right pointer to include (20,1)
Right pointer moves to index 8, adding element 20 from list 1. Coverage remains full. We now check if the current window [3,8] gives a smaller range than before.
💡 When coverage is full, we evaluate the current window's range and update the smallest range if better.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
while have == need:
left_val, left_idx = merged[left]
if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
min_range = val - left_val
res = [left_val, val]
💡 We found a smaller valid range covering all lists, so we update the result.
shrink
Shrink window from left to [10,20]
We shrink the window by moving left pointer from index 3 to 4, removing element (9,1). Coverage remains full, so we update the smallest range to [10,20].
💡 Shrinking the window while coverage remains full helps find the minimal range.
Line:count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
min_range = val - left_val
res = [left_val, val]
💡 Shrinking can improve the range while maintaining coverage.
expand
Expand right pointer to include (22,2)
Right pointer moves to index 9, adding element 22 from list 2. Coverage remains full, so we check if the new window [4,9] gives a smaller range.
💡 Expanding right pointer explores new elements to find potentially smaller ranges.
Line:val, idx = merged[right]
count[idx] += 1
if count[idx] == 1:
have += 1
while have == need:
left_val, left_idx = merged[left]
if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
min_range = val - left_val
res = [left_val, val]
💡 We are approaching the optimal smallest range covering all lists.
shrink
Shrink window to [20,24]
We shrink the window by moving left pointer from index 4 to 10 through several steps, removing elements until the window covers [20,24]. This is the smallest range found that covers all lists.
💡 Final shrinking finds the minimal window covering all lists.
Line:while have == need:
left_val, left_idx = merged[left]
if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
min_range = val - left_val
res = [left_val, val]
count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
💡 The smallest valid range is [20,24], covering all lists with minimal width.
reconstruct
Final answer found
The algorithm finishes with the smallest range [20,24] that covers all lists. This range includes elements 24 (list 0), 20 (list 1), and 22 (list 2).
💡 The final range is the minimal window covering all lists, found by expanding and shrinking the sliding window.
Line:return res
💡 The two-pointer sliding window approach efficiently finds the smallest range covering all lists.
from collections import Counter
def smallestRangeTwoPointers(nums):
merged = []
k = len(nums)
for i, lst in enumerate(nums): # STEP 1
for val in lst:
merged.append((val, i))
merged.sort(key=lambda x: x[0]) # STEP 2
count = Counter()
have = 0
need = k
left = 0 # STEP 3
min_range = float('inf')
res = []
for right in range(len(merged)):
val, idx = merged[right] # STEP 4+ expanding right
count[idx] += 1
if count[idx] == 1:
have += 1
while have == need: # STEP 7+ shrinking left
left_val, left_idx = merged[left]
if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
min_range = val - left_val
res = [left_val, val]
count[left_idx] -= 1
if count[left_idx] == 0:
have -= 1
left += 1
return res
if __name__ == '__main__':
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
print(smallestRangeTwoPointers(nums))
📊
Smallest Range Covering K Lists - Watch the Algorithm Execute, Step by Step
Watching the algorithm step-by-step reveals how the sliding window expands and shrinks to cover all lists efficiently, which is hard to grasp from code alone.
Step 1/19
·Active fill★Answer cell
setup
(4,0)
0
(10,0)
1
(15,0)
2
(24,0)
3
(26,0)
4
(0,1)
5
(9,1)
6
(12,1)
7
(20,1)
8
(5,2)
9
(18,2)
10
(22,2)
11
(30,2)
12
Result: "[]"
setup
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[]"
setup
left
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[]"
expand
right
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[]"
expand
left
(0,1)
0
right
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[]"
expand
left
(0,1)
0
(4,0)
1
right
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[]"
shrink
(0,1)
0
left
(4,0)
1
right
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
left
(4,0)
1
(5,2)
2
right
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
shrink
(0,1)
0
(4,0)
1
left
(5,2)
2
right
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
(4,0)
1
left
(5,2)
2
(9,1)
3
right
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
shrink
(0,1)
0
(4,0)
1
(5,2)
2
left
(9,1)
3
right
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
(4,0)
1
(5,2)
2
left
(9,1)
3
(10,0)
4
right
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
(4,0)
1
(5,2)
2
left
(9,1)
3
(10,0)
4
(12,1)
5
right
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
(4,0)
1
(5,2)
2
left
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
right
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[0,5]"
expand
(0,1)
0
(4,0)
1
(5,2)
2
left
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
right
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[9,20]"
shrink
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
left
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
right
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[10,20]"
expand
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
left
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
right
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[10,20]"
shrink
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
right
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[20,24]"
record
(0,1)
0
(4,0)
1
(5,2)
2
(9,1)
3
(10,0)
4
(12,1)
5
(15,0)
6
(18,2)
7
(20,1)
8
(22,2)
9
(24,0)
10
(26,0)
11
(30,2)
12
Result: "[20,24]"
Key Takeaways
✓ Merging and sorting all elements from k lists allows a unified sliding window approach.
This insight is hard to see from code alone because it involves understanding the data transformation before the main algorithm.
✓ The two-pointer sliding window expands to cover all lists and shrinks to minimize the range.
Visualizing pointer movements clarifies how coverage and range size are balanced dynamically.
✓ Coverage counts track how many lists are included, controlling when to shrink or expand the window.
Seeing coverage counts change step-by-step reveals why the window moves as it does.
Practice
(1/5)
1. Given the following code for finding k pairs with smallest sums, what is the returned result when called with nums1 = [1,7,11], nums2 = [2,4,6], and k = 3?
easy
A. [[1, 2], [1, 4], [1, 6]]
B. [[1, 2], [7, 2], [1, 4]]
C. [[1, 2], [7, 2], [7, 4]]
D. [[1, 2], [1, 4], [7, 2]]
Solution
Step 1: Initialize min-heap with pairs (nums1[i] + nums2[0])
Pop (3,0,0) -> result [[1,2]], push (1+4,0,1) -> heap [(7,0,1),(9,1,0),(13,2,0)]
Pop (7,0,1) -> result [[1,2],[1,4]], push (1+6,0,2) -> heap [(7,1,0),(13,2,0),(7,0,2)]
Pop (7,1,0) -> result [[1,2],[1,4],[7,2]]
Final Answer:
Option D -> Option D
Quick Check:
Matches expected output from code trace [OK]
Hint: Heap pops smallest sum pairs in order [OK]
Common Mistakes:
Off-by-one in indexing nums2
Wrong order of pairs in result
Confusing heap push/pop order
2. You have K identical machines and a list of jobs, each with a start time and duration. You want to assign each job to a machine so that each machine processes jobs sequentially without overlap, always choosing the earliest available machine with the smallest index. Which algorithmic approach guarantees an optimal assignment minimizing waiting times and correctly handles job scheduling in chronological order?
easy
A. Greedy approach that assigns each job to the first machine found free by scanning all machines linearly.
B. Use a min-heap to track available machines by their next free time and assign jobs in order of start time, updating machine availability accordingly.
C. Dynamic programming that tries all possible assignments and picks the minimum total completion time.
D. Sort jobs by duration and assign them to machines in that order to minimize total processing time.
Solution
Step 1: Understand the problem constraints
The problem requires assigning jobs to machines so that each job starts no earlier than its start time, machines process jobs sequentially, and the earliest available machine with the smallest index is chosen.
Step 2: Identify the correct approach
Using a min-heap to track machine availability by next free time allows efficient retrieval of the earliest available machine. Sorting jobs by start time ensures chronological processing. This approach guarantees optimal scheduling and respects machine indices.
Final Answer:
Option B -> Option B
Quick Check:
Min-heap + sorting jobs by start time -> optimal scheduling [OK]
Hint: Min-heap tracks earliest available machine efficiently [OK]
Common Mistakes:
Using linear search for machine availability leads to O(nK) time
Sorting by duration ignores job start times and causes conflicts
DP approach is infeasible due to large state space
3. The following code attempts to merge k sorted arrays using divide and conquer. Which line contains a subtle bug that causes incorrect output when the number of arrays is odd?
medium
A. Line 5: for i in range(0, len(arrays), 2):
B. Line 8: merged_arrays.append(merge_two_arrays(arr1, arr2))
C. Line 7: arr2 = arrays[i+1]
D. Line 10: return arrays[0]
Solution
Step 1: Identify handling of odd number of arrays
When number of arrays is odd, accessing arrays[i+1] without check causes IndexError or misses last array.
Step 2: Correct fix
Use conditional: arr2 = arrays[i+1] if i+1 < len(arrays) else [] to handle last array properly.
Final Answer:
Option C -> Option C
Quick Check:
Line 7 lacks boundary check -> bug on odd arrays [OK]
Hint: Check array bounds when accessing pairs in loop [OK]
Common Mistakes:
Forgetting boundary check for last array
Merging empty array incorrectly
Returning wrong array index
4. What is the time complexity of the min-heap based algorithm to find the nth ugly number, and why?
medium
A. O(n^2) because each number can generate up to 3 new numbers and heap operations are costly.
B. O(n) because each number is processed only once and heap operations are constant time on average.
C. O(n log n) because each of the n ugly numbers is pushed and popped from the heap once, and heap operations take O(log n).
D. O(n log k) where k=3 because the heap size is limited to 3 elements at any time.
Solution
Step 1: Analyze heap operations per ugly number
Each ugly number is popped once and up to 3 new numbers are pushed. The heap size can grow up to O(n) in worst case.
Step 2: Calculate total complexity
Each push/pop operation costs O(log n), and there are O(n) such operations, so total time is O(n log n).
Final Answer:
Option C -> Option C
Quick Check:
Heap operations dominate with O(log n) per operation [OK]
Hint: Heap operations cost O(log n), not constant [OK]
Common Mistakes:
Assuming heap size is constant
Confusing n with k in complexity
Ignoring log factor in heap operations
5. Suppose the array elements can be reused multiple times (duplicates allowed and repeated). Which modification to the k-sorted array sorting algorithm is necessary to correctly handle this scenario?
hard
A. No modification needed; the existing min-heap approach works correctly with duplicates.
B. Use a max-heap instead of a min-heap to handle duplicates correctly.
C. Add a frequency map to track counts and adjust heap operations accordingly.
D. Sort the array fully using a standard sort to handle duplicates reliably.
Solution
Step 1: Understand duplicates in k-sorted array
Duplicates do not affect the heap property; min-heap handles equal elements correctly.
Step 2: Confirm no algorithmic change needed
Heap operations remain valid; duplicates are naturally ordered by heapq.
Final Answer:
Option A -> Option A
Quick Check:
Min-heap supports duplicates without extra data structures [OK]
Hint: Min-heap naturally supports duplicates without changes [OK]
Common Mistakes:
Thinking max-heap is needed for duplicates
Adding unnecessary frequency maps
Defaulting to full sort unnecessarily
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
