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 &lt;= 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&lt;List&lt;Integer&gt;&gt; dataInput;

public SearchItem(final List&lt;List&lt;Integer&gt;&gt; inputs) {
    dataInput = new ArrayList&lt;List&lt;Integer&gt;&gt;();
    for (List&lt;Integer&gt; input : inputs) {
        dataInput.add(new ArrayList&lt;Integer&gt;(input));
    }
}

public List&lt;Integer&gt; getItem(final Integer x) {
    List&lt;Integer&gt; outputs = new ArrayList&lt;Integer&gt;();
    for (List&lt;Integer&gt; data : dataInput) {
        int i = Collections.binarySearch(data, x); // binary searching the item
        if (i &lt; 0)
            i = -(i + 1);
        outputs.add(i == data.size() ? null : data.get(i));
    }
    return outputs;
}

public static void main(String[] args) {
    List&lt;List&lt;Integer&gt;&gt; lists = new ArrayList&lt;List&lt;Integer&gt;&gt;();

    List&lt;Integer&gt; list1 = new ArrayList&lt;Integer&gt;(Arrays.asList(3, 4, 6));
    List&lt;Integer&gt; list2 = new ArrayList&lt;Integer&gt;(Arrays.asList(1, 2, 3));
    List&lt;Integer&gt; list3 = new ArrayList&lt;Integer&gt;(Arrays.asList(2, 3, 6));
    List&lt;Integer&gt; list4 = new ArrayList&lt;Integer&gt;(Arrays.asList(1, 2, 3));
    List&lt;Integer&gt; list5 = new ArrayList&lt;Integer&gt;(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&lt;Integer&gt; 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 anyone provide an example of how this would work based on my example?
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&lt;T&gt; {
    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&lt;Value&lt;Integer&gt;&gt; values = new LinkedList&lt;&gt;();


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

for (int datapointer = 0; datapointer &lt; datalists.size(); datapointer++) {
    ListIterator&lt;Value&lt;Integer&gt;&gt; valit : values.listIterator();
    List&lt;Integer&gt; = datalists.get(datapointer);
    for (Integer addval : data) {
        boolean found = false;
        while (valit.hasNext()) {
            if (addval.compareTo(valit.next().value) &gt;= 0) {
                found = true;
                Value&lt;Integer&gt; 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&lt;Integer&gt; 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&lt;Integer&gt; 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&lt;Value&lt;Integer&gt;&gt;(values);


Right, here we now have a sorted list of Values&lt;Integer&gt;. 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&lt;T extends Comparable&lt;T&gt;&gt; implements Comparable&lt;Value&lt;T&gt;&gt; {

    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&lt;T&gt; o) {
        return value.compareTo(o.value);
    }

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

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

    @Override
    public String toString() {
        return String.format("%s -&gt; %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&lt;T extends Comparable&lt;T&gt;&gt; {

    private final List&lt;Value&lt;T&gt;&gt; index;
    private final Class&lt;T&gt; clazz;
    private final int width;

    public MultiListIndex(Class&lt;T&gt; clazz, Collection&lt;List&lt;T&gt;&gt; data) {
        this.clazz = clazz;
        this.width = data.size();
        this.index = preprocess(new ArrayList&lt;&gt;(data));
    }

    private final List&lt;Value&lt;T&gt;&gt; preprocess(List&lt;List&lt;T&gt;&gt; data) {
        LinkedList&lt;Value&lt;T&gt;&gt; processed = new LinkedList&lt;&gt;();
        Value&lt;T&gt; target = null;
        for (int listid = 0; listid &lt; data.size(); listid++) {
            ListIterator&lt;Value&lt;T&gt;&gt; valit = processed.listIterator();
            Iterator&lt;T&gt; datait = data.get(listid).iterator();
            while (datait.hasNext()) {
                final T toadd = datait.next();
                boolean found = false;
                while (valit.hasNext()) {
                    final int compare = (target = valit.next()).compareToValue(toadd);
                    if (compare &gt;= 0) {
                        // we have a match, or gone past.
                        valit.previous();
                        found = true;
                        if (compare == 0) {
                            target.setIndex(listid, toadd);
                        } else {
                            Value&lt;T&gt; newtarget = new Value&lt;&gt;(toadd, Arrays.copyOf(target.getIndices(), width));
                            valit.add(newtarget);
                            newtarget.setIndex(listid, toadd);
                            if (newtarget != valit.previous()) {
                                throw new IllegalStateException("Bad math!");
                            }
                        }
                        break;
                    }
                    target.setIndex(listid, toadd);
                }
                if (!found) {
                    Value&lt;T&gt; newtarget = new Value&lt;&gt;(toadd, buildArray(clazz, width));
                    valit.add(newtarget);
                    newtarget.setIndex(listid, toadd);
                }
            }
        }
        return new ArrayList&lt;&gt;(processed);
    }


    @SuppressWarnings("unchecked")
    private static final &lt;T&gt; T[] buildArray(Class&lt;T&gt; clazz, int size) {
        return (T[])Array.newInstance(clazz, size);
    }

    public List&lt;T&gt; searchValues(T value) {
        Value&lt;T&gt; key = new Value&lt;&gt;(value, null);
        int pos = Collections.binarySearch(index, key);
        if (pos &lt; 0) {
            pos = -pos - 1;
        }
        if (pos &gt;= index.size()) {
            return Arrays.asList(buildArray(clazz, width));
        }
        return Arrays.asList(Arrays.copyOf(index.get(pos).getIndices(), width));
    }


}


MultiListMain.java

package listsearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MultiListMain {

    public static void main(String[] args) {
        List&lt;List&lt;Integer&gt;&gt; lists = new ArrayList&lt;List&lt;Integer&gt;&gt;();

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

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

        MultiListIndex&lt;Integer&gt; search = new MultiListIndex&lt;Integer&gt;(
                Integer.class, lists);
        // System.out.println(dataInput);

        System.out.println(search.searchValues(0));
        System.out.println(search.searchValues(1));
        System.out.println(search.searchValues(2));
        System.out.println(search.searchValues(5));

    }

}


Output


[3, 1, 2, 1, 4]
[3, 1, 2, 1, 4]
[3, 2, 2, 2, 4]
[6, null, 6, null, 8]