Improve performance while Traversing List

Question

I was trying to write a Java program to compare previous records while traversing. It returns true if element exists previously, else false.

e.g.

• if elements are {"Raj","Jas","Kam","Jas"} then return true (since Jas element available previously)
• if elements are {"Raj","Jas","Kam","Tas"} then return false

I have written the below code, but its complexity is n*n, which is not good. How could I write clean code to improve the performance?

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

public class CompareList {
    private List<String> listNames;
    private List<String> listTempName = new ArrayList<>();

    public CompareList(String[] vListArray) {
        listNames = Arrays.asList(vListArray);
    }
    public CompareList(List<String> vListName) {
        listNames = vListName;
    }
    public boolean isPreviousNameExist() {
        String tempName = null;
        for (int i = 0; i < listNames.size(); i++) {
            tempName = listNames.get(i);
            if (listTempName.contains(tempName)) {
                return true;
            } else {
                listTempName.add(tempName);
            }

        }
        return false;
    }
    public static void main(String[] args) {
        String[] nameArray = {"A", "B", "C", "D", "E", "F"};
        CompareList compareList = new CompareList(nameArray);
        System.out.println("==>" + compareList.isPreviousNameExist());
    }
}

UPDATED

I have updated the code and tried using a recursive way, same way how we sort using MergeSort and find its performance better for a large number of records, compared to HashSet. I believe its complexity is O(log n).

public class NameComparator {

    private String[] listNames;

    private String[] listTempNames;

    private boolean compareFlag = false;

    private int size;
    public boolean isNameAlreadyExist(String[] vListNames) {
        this.listNames = vListNames;
        size = vListNames.length;
        this.listTempNames = new String[size];
        checkAndSort(0, size - 1);
        return compareFlag; 
    }
    private void checkAndSort(int low, int high) {

        //Use the merge sort
        }
    }
    ..............................
}

Answer 1

You can actually change the performance to O(n) by changing one line of code here (and adding a couple of imports):

import java.util.Set;
import java.util.HashSet;

...

private Set<String> listTempName = new HashSet<>();

Although this works, we can simplify the code a little bit. Effectively, you want to see if the list of elements in the given List are unique. There's a really easy way to do this: add them all to a Set. If the size of the set and the size of the list are equal, then there are no duplicates. If the sizes are different, then there must be 1 or more duplicate elements. With this, we can simplify your code to:

public boolean isPreviousNameExist() 
{
    for(String name : listNames) {
        listTempName.add(name);
    }
    return listNames.size() != listTempName.size();
}

A slight improvement based on comment by @bowmore:

public boolean isPreviousNameExist()
{
    for(String name : listNames) {
        if(!listTempName.add(name)) {
            return true;
        }
     }
     return false;
}

Answer 2

Your complexity is indeed O_(n²) because you traverse a list bounded by n for each n elements of your list.

You can reduce this list to O_{(n * log(n))} quite easily:

• Sort your array -> O_{(n * log(n))}
• Compare each element with the next one listNames.get(i).equals(listNames.get(i+1)) -> O_(n)

Total is O_{(n * log(n))}

---

Edit:

If you are really interested on the true/false result, there is a pretty one-liner solution :

return listNames.size() == new HashSet(listNames).size();

The HashSet will filter duplicate elements, hence will be smaller if there are any duplicates. It runs in O_(n), as insertion in a HashSet is O₍₁₎