Shortest Range in K-sorted Lists | Algorithms

Shortest Range in K-sorted Lists | Algorithms

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:

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.

Read full article from Shortest Range in K-sorted Lists | Algorithms