Extracting elements from multiple sorted lists efficiently

I was asked this interview question recently. I was able to come up with this which runs in \$O(k \log n)\$.


Given k <= n sorted arrays each of size n, there exists a data structure requiring \$O(kn)\$ preprocessing time and memory that answers iterated search queries in \$O(k + \log n)\$ time.

I have k sorted Lists, each of size \$n\$. I currently have hard-coded 5 sorted Lists each of size 3, but in general that can be a very high number.

I would like to search for a single element in each of the \$k\$ Lists. Obviously, I can binary search each array individually, which will result in \$O(k \log n)\$ where \$k\$ is number of sorted arrays.

Can I do it in \$O(k + \log n)\$ where \$k\$ is the number of sorted arrays? I think there might be some better way of doing it as we're doing the same searches \$k\$ times as of now.

private List> dataInput;

public SearchItem(final List> inputs) {
    dataInput = new ArrayList>();
    for (List input : inputs) {
        dataInput.add(new ArrayList(input));
    }
}

public List getItem(final Integer x) {
    List outputs = new ArrayList();
    for (List data : dataInput) {
        int i = Collections.binarySearch(data, x); // binary searching the item
        if (i > lists = new ArrayList>();

    List list1 = new ArrayList(Arrays.asList(3, 4, 6));
    List list2 = new ArrayList(Arrays.asList(1, 2, 3));
    List list3 = new ArrayList(Arrays.asList(2, 3, 6));
    List list4 = new ArrayList(Arrays.asList(1, 2, 3));
    List list5 = new ArrayList(Arrays.asList(4, 8, 13));

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);
    lists.add(list4);
    lists.add(list5);

    SearchItem search = new SearchItem(lists);
    System.out.println(dataInput);

    List dataOuput = search.getItem(5);

    System.out.println(dataOuput);
}

Whatever output I am seeing with my above code approach should come with the new approach as well which should work in \$O(k + \log n)\$. Is this possible to achieve? Can

This is sooo off-topic for CR... but, since it is related to a previous answer, and since I want to see a blown mind ....:

consider the following code:

class Value {
    private final T value;
    private final int[] arraypointers;
    private final int arraycursor = 0;

    Value(T value, int maxindex) {
        this.value = value;
        this.arraypointers = new int[maxindex];
    }

    public void addIndex(int pointer) {
        arraypointers[arraycursor++] = pointer;
    }

    ... some other stuff.
}

OK, the above class will be used as follows... consider the example data system, the value 4 appears in list1 and list5.

This would be stored as:

Value v = new Value(4, k);
v.addIndex(1);
v.addIndex(5);

Now, start with a LinkedList:

LinkedList> values = new LinkedList<>();

Then, iterator though each of your loops, and merge the values in to the linked list:

for (int datapointer = 0; datapointer > valit : values.listIterator();
    List = datalists.get(datapointer);
    for (Integer addval : data) {
        boolean found = false;
        while (valit.hasNext()) {
            if (addval.compareTo(valit.next().value) >= 0) {
                found = true;
                Value val = valit.previous();
                if (val.value.equals(addval) {
                    // update existing value
                    val.addIndex(datapointer);
                    // leave the iterator point backwards to 
                    // allow for dup values in the data.
                } else {
                    // add a new value
                    Value val = new Value(addval, k);
                    val.addIndex(datapointer);
                    valit.add(val);
                    // leave the iterator pointing backwards.
                    // but need to move it back one.
                    valit.previous();
                }
            }
        }
        if (!found) {
            Value val = new Value(addval, k);
            val.addIndex(datapointer);
            valit.add(val);
            valit.previous();
        }

    }
}

then, convert the LinkedList in to an ArrayList

List sortedvalues = new ArrayList>(values);

Right, here we now have a sorted list of Values. Each Value has pointers back to the list(s) they came from.

The space complexity for this is \$O(kn)\$ and we got there by doing a complexity \$O(kn)\$ nested loop (the inside while loop does not count because it is on an iterator that is outside the for loop, and it is part of the same complexity as the inner for loop)...

OK, so that is the \$O(kn)\$ preprocessing.

The lookup is a case of doing a binary search on the ArrayList (\$O(\log n)\$) and then iterating over the index pointers (\$O(k)\$).

Thus, the search is \$O(k + log n)\$.

Voila!

Working solution

Right, putting all the pieces together in a working solution:

Value.java

import java.util.Arrays;

class Value> implements Comparable> {

    private final T value;

    private final T[] indices;

    public Value(T value, T[] data) {
        super();
        this.value = value;
        this.indices = data;
    }

    public void setIndex(int index, T val) {
        if (indices[index] == null) {
            indices[index] = val;
        }
    }

    public T[] getIndices() {
        return Arrays.copyOf(indices, indices.length);
    }

    public int compareToValue(T o) {
        return value.compareTo(o);
    }

    @Override
    public int compareTo(Value o) {
        return value.compareTo(o.value);
    }

    @Override
    public int hashCode() {
        return value.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Value && value.equals(((Value)obj).value);
    }

    @Override
    public String toString() {
        return String.format("%s -> %s", value, Arrays.toString(indices));
    }
}

MultiListIndex.java

```
package listsearch;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class MultiListIndex> {

private final List> index;
private final Class clazz;
private final int width;

public MultiListIndex(Class clazz, Collection> data) {
this.clazz = clazz;
this.width = data.size();
this.index = preprocess(new ArrayList<>(data));
}

private final List> preprocess(List> data) {
LinkedList> processed = new LinkedList<>();
Value target = null;
for (int listid = 0; listid > valit = processed.listIterator();
Iterator datait = data.get(listid).iterator();
while (datait.hasNext()) {
final T toadd = datait.next();
boolean found = false;
while (valit.hasNext()) {
final int compare = (target = va

StackExchange Code Review Q#43006, answer score: 4