Extracting elements from multiple sorted lists efficiently
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]