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;
}

• Nitin: thanks Yuushi, Is it any other way without using hashing?
• Yuushi: Well, you can use a TreeSet, which (by default) uses natural ordering to search for elements (which is O(log n) instead of amortized O(1)). Is there any real reason you want to avoid hashing?
• Nitin: thanks Yuushi, I only have doubt if it support large datas?
• bowmore: You can break early from the loop if Set.add()returns false
• Yuushi: O(n), not that I can think of. There is an O(n log n) solution: sort the original array, and then loop through it, checking adjacent elements. This could potentially be better if memory is an issue.

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₍₁₎

• Nitin: thanks njZk2 and sybOrg. I did just small modification in sorting approach. I sort through merge sort(recursive approach) as considering large data and while sorting i compare the element with flag. I updated the code. Please review the same and provide suggestion.