Iterator for a list of sorted lists using a priority queue

user_1065835 0
Viewed 1430

I found the following interview question here.

SortedIterator - consists of List of Lists with sorted int values in each list. You have to give next sorted value when call next().

have to implement methods * constructor * next() * hasNext()

[ [1, 4, 5, 8, 9], [3, 4, 4, 6], [0, 2, 8] ]

next() -> 0, 1, 2, 3, 4, 4, 4...

I wrote a quick implementation in Java:

package com.app;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class SortedIterator implements Iterator<Integer> {

    private final List<Integer> mFlattenedList;
    private final Iterator<Integer> mIntegerIterator;

    SortedIterator(final List<List<Integer>> lists) {
        mFlattenedList = flattenLists(lists);
        mIntegerIterator = mFlattenedList.iterator();
    }

    private List<Integer> flattenLists(final List<List<Integer>> lists) {
        final List<Integer> result = new ArrayList<>();
        for (List<Integer> list : lists) {
            for (int value : list) {
                result.add(value);
            }
        }
        Collections.sort(result);
        return result;
    }

    @Override
    public boolean hasNext() {
        return mIntegerIterator.hasNext();
    }

    @Override
    public Integer next() {
        return mIntegerIterator.next();
    }
}

Time: O (K * N) to flatten the input list of lists + O (N*K) to iterate over the flattened list = O (N * K)

Space: O (N * K) to store the flattened list.

N - number of lists.

K - number of elements in each list.

But the answer from the link says:

There is a solution with time complexity O(logN) using a priority queue. Maybe an interviewer expected something like that, I don't know.

How is O (log N) possible? If a priority queue is used, every time we call hasNext(), we'll need to check if the queue is empty (O(1)). Then we call next() which extracts the min element from the queue (O(log (N*K)) for any implementation) according to the table. Since we need to call next() N * K times, it takes us O(N * K * log (N*K) to iterate over all the elements.

priority-queue data-structures algorithm java
1 Answers

The solution's O(logN) complexity is the complexity per element, not the complexity to iterate over all values.

The solution looks something like this:

  • First define a new class called ListValue that stores a value as well as the index of the list it came from. These should be comparable to other ListValue objects using the value.

  • Constructor: Initialize a PriorityQueue<ListValue> called pq and place the first element from each of the N lists into pq.

  • next(): Pop the ListValue at the front of pq. The value inside is the value to be returned, but first, move the next element from that ListValue's list into pq. Complexity is O(log N), since we remove one element and add one element to pq, which contains at most N elements.

Note that the solution doesn't keep all N*K values in the priority queue at once, only the single "next" value from each of the N lists. Hence, the priority queue has (at most) N elements at all times, so its operations are all O(log N).

To understand why this works, recall that each list is already sorted, so the minimum unused value must appear at the "front" of some list (not including the values already consumed). Then, note that the priority queue contains precisely the "front" element of each list -- we force this to happen in next() when we add an element to pq from the same list as the element we removed. Therefore, at all times pq will contain the minimum unused value (until all values are exhausted).

user_95895930
Related