3

I have 2 ArrayLists that have a Array of Strings as a "component". I want to find the "components" whose first element is the same in both ArrayLists. To be more clear:

ArrayList One
first component => {"0", "zero"}
second component => {"1", "one"}
ArrayList Two
first component => {"1", "uno"}
second component => {"2", "two"}

I would like to loop through ArrayList Two and find {"1","uno"}. So far I have a nested loop that loops through the first array and then checks the current component to each component in ArrayList Two. 

    for(int i=0; i<One.size(); i++)
    {
        for(int j=0; j<Two.size(); j++)
        {
            if( fileOne.get(i)[0].equals( Two.get(j)[0] ) )
            {
                System.out.print( Two.get(j)[0]+" " );
                System.out.print( Two.get(j)[1] );
                System.out.println();
            }
        }
    }

I think there should be a better solution. Any help

Improve this question

4 Answers 4

Reset to default
2

Use a HashSet.

Set<String> set = new HashSet<String>()
for(int i=0; i<One.size(); i++) {
  set.add(fileOne.get(i)[0]);
}

for(int i=0; i<Two.size(); i++) {
  String component[] = Two.get(j)
  if(set.contains(component[0])) {
    System.out.print( component[0]+" " );
    System.out.print( component[1] );
    System.out.println();
   }
}

Note: A List would not work in this case, because lookups in Lists are O(N). Lookups in HashSets are O(1), so building the set (first loop) is O(N). Then going through your second array is O(M) and each lookup is O(1).

Overall, this becomes O(N) + ( O(M) * O(1) ) = O(N+M)

Edit: for Ted's comments.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This is probably a more memory-efficient solution than mine. To get OP's desired output, though, change the body of the if to System.out.println( Two.get(j)[0]+" "+Two.get(j)[1] );. (A temporary variable here would help. :-) )
2

You might try a hashmap. Initialize it from the first ArrayList by mapping the first element of each component to the component (or the index of the component). Then for each component of the second ArrayList, you can look up by the first element of each component to find the matching component (or discover that there isn't one when it returns null).

Improve this answer

3 Comments

Hashing entire list = O(1) * n. Looking up all elements = O(1) * m. So I guess unless I missed something, Ted's solution is O(n + m) is that correct? Then again hashing is similar to sorting, in that it allows faster lookups..
@Kyle - I believe it is O(n+m), just like Reverend Gonzo's solution.
Yeah, this is essentially the same as mine.
1

Use two hashsets and the method retainAll such that:

One.retainAll(Two)

Complexity wise is better - only O(n+m) against your O(n*m). And in terms of readability and maintainability is also better. Notice that retainAll will modify the hashset One if you don't want behavior make a third copy.

Improve this answer

2 Comments

The elements do not need to be the same though. Each element is an Array of Strings, and I only want the first element in the Array of Strings to match.
That's not a problem. Define a Class that contains the array and implement the methods hashCode and equals in such a way that only tests the first element of the array. Then create instances of this Class and use them inside the hashsets.
-1

(edited in response to Ted's comment)

Without initialization work such as sorting/hashing, or maintaining a sorted/hashed list, there is no better solution, an optimal solution is O(n*m) which yours is. That's the optimal solution because you have to compare every element to every other element.

I should also mention that in certain scenarios, it may be wiser to keep the list sorted. Then instead of comparing every element you could use a binary search or something. But without sorting your list first, yes you have to compare all elements. I believe the best possible sorting time is O(nlgn). Then after that sort process you'd still have to search the sorted list for your element, but searching a sorted list can be faster than searching an unsorted one.

Improve this answer

8 Comments

There's no need to compare every element to every other one. Indexing data structures can work wonders to decompose this problem into one that is O(n+m). Even simply sorting both arrays and then using that to advantage will give better performance than O(n*m).
There most definitely is a better solution. Use hashes.
@ted, @reverend .. see my comment on Ted's post. I was indicating that without doing extra "initialization" work, he could not do better. I should have mentioned hashing as well, but didn't think of it.. I think the fact that I mentioned sorting will yield better performance, is basically the same thing.
This quote: "An optimal solution is O(n*m)" is outright wrong. Sorting it is not the same as hashing it.
@reverend I know the difference between sorting and hashing. I was saying they are similar only in the respect that they allow for faster lookups, which is true. (But yes, that quote was outright wrong, I agree.. I edited the post so that OP does not see inaccurate info)
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.