Skip to main content

23. Smallest Range Covering Elements from K Lists

hardAsked at Confluent

Find the smallest range [a, b] containing at least one element from each of k sorted lists — Confluent uses it because k-way merge is the same shape as joining k partitions in a Kafka topic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given k sorted ascending integer lists, find the smallest range [a, b] such that at least one element from each list lies in [a, b]. Ties broken by smaller a.

Constraints

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -10^5 <= nums[i][j] <= 10^5

Examples

Example 1

Input
nums=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output
[20,24]

Example 2

Input
nums=[[1,2,3],[1,2,3],[1,2,3]]
Output
[1,1]

Approaches

1. Brute force enumeration

Try every pair of values across all lists and check coverage.

Time
O((kN)^2 * k)
Space
O(1)
// flatten and brute-force every pair (a,b); check that each list has an element in [a,b]

Tradeoff:

2. Min-heap k-way merge

Push the first element of each list with its list index into a min-heap and track the current max. The window [heap.min, max] always covers all lists; shrink by popping the min and pushing its successor, updating the best range.

Time
O(N log k)
Space
O(k)
function smallestRange(nums) {
  // heap of [value, listIdx, elementIdx], min-ordered by value
  const h = [];
  function up(i){while(i>0){const p=(i-1)>>1; if(h[p][0]<=h[i][0])break; [h[p],h[i]]=[h[i],h[p]]; i=p;}}
  function down(i){const n=h.length; for(;;){let l=2*i+1,r=l+1,s=i; if(l<n&&h[l][0]<h[s][0])s=l; if(r<n&&h[r][0]<h[s][0])s=r; if(s===i)break; [h[s],h[i]]=[h[i],h[s]]; i=s;}}
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    h.push([nums[i][0], i, 0]); up(h.length - 1);
    max = Math.max(max, nums[i][0]);
  }
  let best = [h[0][0], max];
  while (true) {
    const [v, li, ei] = h[0];
    if (ei + 1 === nums[li].length) break;
    const next = nums[li][ei + 1];
    max = Math.max(max, next);
    h[0] = [next, li, ei + 1]; down(0);
    if (max - h[0][0] < best[1] - best[0]) best = [h[0][0], max];
  }
  return best;
}

Tradeoff:

Confluent-specific tips

Confluent will reframe k lists as k Kafka partitions — describe how partition assignment plus exactly-once semantics let a single consumer maintain the heap while still surviving consumer-group rebalance.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Smallest Range Covering Elements from K Lists and other Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →