Smallest Range Covering Elements from K Lists

Given k sorted lists, find the smallest range that includes at least one number from every list. If multiple ranges have the same length, choose the one with the smaller start value.

Input Format

lists = array of sorted integer arrays

Output Format

smallest range [start,end] covering all lists

Constraints

  • 1 <= k <= 3500
  • 1 <= total elements <= 10^5
  • -10^5 <= values <= 10^5

Examples

Example 1:

Input:

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

Output:

[20,24]

Explanation:

The range [20,24] contains 20, 24, and 22 from the three lists.

Example 2:

Input:

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

Output:

[1,1]

Explanation:

The value 1 appears in every list, so the smallest possible range is [1,1].

Loading...
Smallest Range Covering Elements from K Lists