Get Kth smallest element in PriorityQueue (Java)

Question

I'm doing the following problem for fun / Java practice:

Write a method kthSmallest that takes in a PriorityQueue of integers as input and outputs the kth smallest integer. The internal state of the priority queue passed in should not be changed by the method. You may use ONLY one queue or stack as extra data. No other data structures allowed. k is 1-indexed (k = 1 means the smallest value).

Getting the kth element is simple: just remove k times since it's a priority queue. I figured that I could just pop off, put the elements on a stack for storage, and then add them back to the queue once I'm done. That doesn't work though since the elements get ordered differently in the priority queue.

Here's my code for curiosity:

public int kthSmallest(PriorityQueue<Integer> pq, int k) {
    Stack<Integer> s = new Stack<Integer>();

    for (int i = 1; i <= k; ++i) {
            s.push(pq.remove());
    }

    int kthValue = s.peek();

    while (!s.empty()) {
        pq.add(s.pop());
    }

    return kthValue;
}

So how can I do this while maintaining the internal state of the priority queue?

P.S. - You can view the problem yourself here

Answer 1

You can't guarantee anything about the underlying state: the only concept of order that a PriorityQueue has is the one provided by the Comparator you specify when creating it (or the natural ordering of its elements). You as the user know nothing beyond that, and it really shouldn't make any difference how the elements are stored so as long as the behavior of the queue is in accordance with what is expected based on its specification.