3
\$\begingroup\$

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
        }
    }
    ..............................
}
\$\endgroup\$
7
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ thanks Yuushi, Is it any other way without using hashing? \$\endgroup\$ – sun007 Jan 29 '14 at 7:07
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Yuushi Jan 29 '14 at 7:11
  • \$\begingroup\$ thanks Yuushi, I only have doubt if it support large datas? \$\endgroup\$ – sun007 Jan 29 '14 at 7:14
  • 5
    \$\begingroup\$ You can break early from the loop if Set.add()returns false \$\endgroup\$ – bowmore Jan 29 '14 at 7:21
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Yuushi Jan 29 '14 at 7:57
2
\$\begingroup\$

Your complexity is indeed O(n2) 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(1)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – sun007 Jan 30 '14 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.