Mr. Blue Mr. Blue - 1 year ago 72
Java Question

Java smallest partition of common elements (in the same order) of two or more lists

I'm looking for a quick and smart way to find up until where two lists are equal. In other words I need to find the smallest partition containing common elements in the same order of two or more lists.
It might sound a bit confusing but here is an example of what I want to achieve:

List 1: A, B, C, L, M Z
List 2: A, B, C, K, F
Output -> List 3: A, B, C

I need to use this in a recursive method which should be called with large inputs and all the solutions I've come up with are a bit too slow.

Thanks for your answers in advance

Please excuse me for being unclear. This is my first question and english is not my first language.

Let me explain the problem in a better way. I need to find the intersection of two or more lists starting from the first element of the lists. Please note that elements must be in the same order so it's not exactly an intersection but more like a partition.

the "recursive" thing was just to say that I need to include this in a recursive method which will run many times so I would like the solution to be as fast as possibile as to not lose a lot of time.

Working on an answer that appears to have been deleted I came up with my own solution:

List<String> list1 = new ArrayList<>(Arrays.asList("ciao", "come"));
List<String> list2 = new ArrayList<>(Arrays.asList("ciao", "come", "va"));
List<String> list3 = new ArrayList<>(Arrays.asList("ciao", "come", "va", "?", "tutto", "ok"));
List<List<String>> allLists = new ArrayList<>();
allLists.addAll(Arrays.asList(list1, list2, list3));

int min = Integer.MAX_VALUE;
int listIndex = 0;
for(List<String> list : allLists){
if(min > list.size()){
min = list.size();
listIndex = allLists.indexOf(list);

int index = 0;
boolean same = true;
while(index<min && same == true) {
String element = allLists.get(listIndex).get(index);
for(List<String> list : allLists){
same = false;
element = allLists.get(listIndex).get(index);
if(same == true) ++index;
System.out.println("OUTPUT:" + allLists.get(listIndex).subList(0, index));
----> Output: ciao, come


And also garnful's solution works like a charm and I find it way clearer than mine. Thanks everybody

Answer Source

This should do the work, and hopefully be quite okay regarding the performance:

public List<String> getEqualsPart(List<String>[] listsToCheck) {
    if (listsToCheck.length == 0) {
        return Collections.emptyList();
    int minLength = getShortesListLength(listsToCheck);
    if (minLength == 0) {
        return Collections.emptyList();
    return getEqualPartsForIndex(listsToCheck, 0, minLength, new ArrayList<String>());


private int getShortesListLength(List<String>[] listsToCheck) {
    int min = Integer.MAX_VALUE;
    for (List<String> currentList : listsToCheck) {
        min = Math.min(min, currentList.size());
    return min;

private List<String> getEqualPartsForIndex(List<String>[] listsToCheck, int index, int minLength,
        List<String> result) {
    if (index == minLength) {
        return result;
    Set<String> setForIndex = new HashSet<>(); -> setForIndex.add(list.get(index)));
    if (setForIndex.size() > 1) {
        return result;
    } else {
        return getEqualPartsForIndex(listsToCheck, index + 1, minLength, result);

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download