Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Shortest Range in K-sorted Lists

Objec­tive: You have k lists of sorted inte­gers. Find the small­est range that includes at least one num­ber from each of the k lists.

This is very nice and tricky solu­tion, This prob­lem was asked in the Google inter­view for soft­ware engi­neer position.

Exam­ple:

Shortest Range in K-sorted Lists - Example

Short­est Range in K-sorted Lists — Example

Small­est range will be 2, [1,3], it will con­tain 3 from list A[], 1 from list B[] and 2 from list C[].

Approach:

  • We will mod­ify the heap imple­men­ta­tion for this solu­tion. This approach will be quite sim­i­lar to “Merge k-sorted array” solu­tion we had discussed.
  • Cre­ate Min-Heap of type HeapN­ode.( HeapN­ode– Every Node will store the data and the list no from which it belongs).
  • Now take one ele­ment from each of the K list and cre­ate HeapN­ode object and insert into min-Heap.
  • While insert­ing keep track of max­i­mum value node inserted, call it as cur­rMax.
  • Extract the min­i­mum Node from the min-Heap call it as min, cal­cu­late the range = currMax-min.
  • The extracted node will also con­tain the list to which it belongs, insert the next ele­ment from that list into min-Heap.
  • Keep track of the min­i­mum range after every iter­a­tion of extract­ing min node and insert­ing new node into the heap.
  • If any point of time any list gets over, return the range, this will be the small­est range in K-list which con­tains at least one ele­ment from each list.
  • See the gif below for bet­ter understanding.
Shortest Range in K-sorted Lists

Short­est Range in K-sorted Lists

Com­plete Code:

Out­put:

Smallest Range is: 2 from 1 To 3

You may also like...