educative.io

Alternative solution to kth smallest number in m sorted list more efficient?

Courses
,
#1

I attempted to solve the kth smallest number problem and came up with a slightly alternative solution from how it suggests I was meant to solve the problem. However, from running some tests, I think the solution I came up with is faster (in terms of time complexity).

I didn’t particularly like my solution because it felt slightly hacky, but from my tests it feels like it is performing better. Have I just miscalculated this, or have I stumbled upon a more efficient solution?

My code is as follows:

public static int kSmallestNumber(List<List> lists, int k) {

    int numberOfLists = lists.size();
    // Maintain a list of pointers for each list to keep track of where we are
    int[] pointers = new int[numberOfLists];

    // Keep track of the currentSmallest number, and which array it's in
    int currentSmallest = 0;
    int prevSmallest = 0;
    int kthNumber = 0;
    int currentSmallestArray = 0;

    // Iterate k times
    while (kthNumber != k) {
        currentSmallest = Integer.MAX_VALUE;
        // Iterate over each list
        for (int i = 0; i < numberOfLists; i++) {
            if (pointers[i] > lists.get(i).size() - 1) {
                // If this list has already been exhausted, then continue
                continue;
            }
            int tempCurrentNumber = lists.get(i).get(pointers[i]);
            if (tempCurrentNumber <= currentSmallest) {
                // As we iterate, keep track of the next smallest number and which list it's in
                currentSmallest = tempCurrentNumber;
                currentSmallestArray = i;
                prevSmallest = tempCurrentNumber;
            }
        }
        // Increment the pointer for the array which had the smallest number so don't compare this number again
        pointers[currentSmallestArray] +=1;

        kthNumber++;
    }
    // Return the smallest number if it isn't max value (if the value of k is larger than all the list sizes)
    // Otherwise return the previous largest number
    return currentSmallest == Integer.MAX_VALUE ? prevSmallest : currentSmallest;
}

And the provided solution is as follows:

public static int kSmallestNumber2(List<List> lists, int k) {
// storing the length of lists to use it in a loop later
int listLength = lists.size();
// declaring a min-heap to keep track of smallest elements
PriorityQueue<int[]> kthSmallest = new PriorityQueue<>((a, b) → a[0] - b[0]);

    for (int index = 0; index < listLength; index++) {
        // if there are no elements in the input lists, continue
        if (lists.get(index).size() == 0) {
            continue;
        } else {
            // placing the first element of each list in the min-heap
            kthSmallest.offer(new int[]{lists.get(index).get(0), index, 0});
        }
    }

    // set a counter to match if our kth element
    // equals to that counter, return that number
    int numbersChecked = 0, smallestNumber = 0;
    while (!kthSmallest.isEmpty()) {  // iterating over the elements pushed in our min-heap
        // get the smallest number from top of heap and its corresponding list and index
        int[] smallest = kthSmallest.poll();
        smallestNumber = smallest[0];
        int listIndex = smallest[1];
        int numIndex = smallest[2];
        numbersChecked++;

        if (numbersChecked == k) {
            break;
        }

        // if there are more elements in list of the top element,
        // add the next element of that list to the min-heap
        if (numIndex + 1 < lists.get(smallest[1]).size()) {
            kthSmallest.offer(new int[]{lists.get(listIndex).get(numIndex + 1), listIndex, numIndex + 1});
        }
    }

    // return the Kth number found in input lists
    return smallestNumber;
}

Thank you for any help!

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Kth Smallest Number in M Sorted Lists

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Kth Smallest Number in M Sorted Lists

1 Like
#2

Hello @Jacotcher,

Thank you for reaching out and sharing your alternative solution for the kth smallest number problem. I appreciate your efforts and initiative in exploring different approaches. After reviewing your code (Solution 1) and conducting a time complexity analysis, we’d like to compare your solution’s time complexity and the already provided solution (Solution 2) in the lesson and see which is more efficient and follows the defined pattern of the problem.

In Solution 1, you use a nested loop to iterate over each element in the lists, and for each iteration, you find the smallest element. This results in a time complexity of O(k * n), where k is the value of k and n is the total number of elements in all lists combined. In the worst case, the inner loop can iterate up to k times.

On the other hand, Solution 2 uses a PriorityQueue (min-heap) to keep track of the smallest element from each list. The PriorityQueue ensures that the smallest element is always at the top, making it easy to extract the smallest element efficiently. The time complexity of Solution 2 is O((m + k) * log(m)), where m is the number of lists and k is the number of times we perform push or pop operations. This is because the PriorityQueue operations (inserting and extracting the minimum element) takes logarithmic time.

Therefore, in terms of time complexity, Solution 2 is more efficient, especially for large values of ‘k’ or when the number of elements in the lists is large. Hope this clarified your confusion regarding time complexity of both solutions.

Please feel free to share more suggestions and feedbacks. We’d be happy to help.

Happy learning!