educative.io

Kth Smallest Number in M Sorted Lists

Courses
,
#1

How is this code working?

public static int findKthSmallest(List<Integer[]> lists, int k) {

PriorityQueue<Node> minHeap = new PriorityQueue<Node>(

    (n1, n2) -> lists.get(n1.arrayIndex)[n1.elementIndex] - lists.get(n2.arrayIndex)[n2.elementIndex]);

// put the 1st element of each array in the min heap

for (int i = 0; i < lists.size(); i++)

  if (lists.get(i) != null)

    minHeap.add(new Node(0, i));

// take the smallest (top) element form the min heap, if the running count is equal to k return the number

// if the array of the top element has more elements, add the next element to the heap

int numberCount = 0, result = 0;

while (!minHeap.isEmpty()) {

  Node node = minHeap.poll();

  result = lists.get(node.arrayIndex)[node.elementIndex];

  if (++numberCount == k)

    break;

  node.elementIndex++;

  if (lists.get(node.arrayIndex).length > node.elementIndex)

    minHeap.add(node);

}

return result;

}

I am not getting this part of node.elementindex

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Kth Smallest Number in M Sorted Lists (Medium) - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @chaitanya_manral
In this, the node.elementindex means that where the element is placed in the array. Like in “l3” the element “3” has arrayIndex = “2” and elementIndex = “1”

1 Like
#3

hi @Rabia_Nouman_Siddiq thanks for the explanation.
I got it.
One more question though-
If possible, can you explain how this works?
for (int i = 0; i < lists.size(); i++)
if (lists.get(i) != null)
minHeap.add(new Node(0, i));

when i is 0 lists.get(0) will be 2 since lists is { 2, 6, 9, 2, 3, 6, 7,1, 3, 4 } then what will be minheap.add(new Node(0,0)) ?
I am getting stuck here.

1 Like
#4

Hi @chaitanya_manral
Actually, in the main, we are creating three lists that are:

  • l1 = { 2, 6, 8 }
  • l2 = { 3, 6, 7 }
  • l3 = { 1, 3, 4 }

Then we create a list of type integer array named “lists.”
After that, we add l1, l2, and l3 to the lists.
So the index 0 of “lists” refer to “l1” and “l1” is an array { 2, 6, 8 } with “2” at index “0”, “6” at index “1”, and “8” at index “2”.

for (int i = 0; i < lists.size(); i++)
{
if (lists.get(i) != null)
{
minHeap.add(new Node(0, i));
}
}

In the above loop, we add the first element of l1, l2, and l3 in the minHeap.
So, when i is 0 lists.get(0) will be 2 then minheap.add(new Node(0,0)) = 2 as “l1” is at “0” index of “lists” and on “0” index of “l1”, “2” is placed.

So, to check what is added in minHeap on a specified index like at Node(0,0). Kindly write the following three lines in the "if statement " of the code mentioned above:

for (int i = 0; i < lists.size(); i++)
{
if (lists.get(i) != null)
{
minHeap.add(new Node(0, i));
Node n = minHeap.poll();
int r = lists.get(n.arrayIndex)[n.elementIndex];
System.out.println(n.elementIndex +"," + n.arrayIndex +","+ r);
}
}
This will display you the index of the array, the index of the element, and the element value.