Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# compare two arraylists and get position of common elements

Sergio Sa
Greenhorn
Posts: 2
• 1
I have two arraylists and the second one is a subset of the first.
I want to know the initial and final position in the first arraylist of elements in the subset (in my example the position in arrayList of: uno, due, tre)

How to modify this code?

Winston Gutkowski
Bartender
Posts: 10111
56
Sergio Sa wrote:I want to know the initial and final position in the first arraylist of elements in the subset (in my example the position in arrayList of: uno, due, tre)
How to modify this code?

Well first, ShowSomeEffort (←click). What have you tried?

One tip for you: You say that you "want to know the initial and final position in the first arraylist of elements in the subset", yet your loops don't suggest that that's what you're doing. How do you think you might want to change them?

Winston

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Here is my Algorithm:

1. scan the Higher Length ArrayList

2. put the element index into Hashtable as key = element and value = position(negate the index)

3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative

4. now scan the Hashtable values which is positive and find the first index and last index.

time complexity will be approximately O(n) though...[scaning first list O(n)+2nd List O(n)+build hash table O(n)+ hash function O(1)+scanning hashtable O(n) => O(n)]

you can modify the algorithm which ever way you like ...

If you go for brute force method as using 2 nested for loop then time complexity will be O(n power of 2).

Note: Correct me If I am Wrong

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Welcome to JavaRanch Sergio Sa

Winston Gutkowski
Bartender
Posts: 10111
56
Seetharaman Venkatasamy wrote:1. scan the Higher Length ArrayList

Fine so far.

2. put the element index into Hashtable as key = element and value = position(negate the index)
3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative
4. now scan the Hashtable values which is positive and find the first index and last index.

Overly complex. Also, changing keys in collections is not usually a good idea (and in a Hashtable may be disastrous).

time complexity will be approximately O(n) though...[scaning first list O(n)+2nd List O(n)+build hash table O(n)+ hash function O(1)+scanning hashtable O(n) => O(n)]

Ah, you never said you were looking for the fastest algorithm, just an algorithm.

you can modify the algorithm which ever way you like ...

No you can't.

My advice: Keep it simple, and look at the problem as you originally stated it. You are looking for the first and last position; all that storing of elements is just a red herring (and actually unnecessary).

Give it another try; if you still have issues, come back.

Winston

 Ooops. Thought you were OP. My comments still stand though.

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Winston Gutkowski wrote:
2. put the element index into Hashtable as key = element and value = position(negate the index)
3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative
4. now scan the Hashtable values which is positive and find the first index and last index.

Overly complex. Also, changing keys in collections is not usually a good idea (and in a Hashtable may be disastrous).

since both array has an unique(means same Objects) object, I dont see any complex here. I didnt talk about changing keys

Winston Gutkowski
Bartender
Posts: 10111
56
Seetharaman Venkatasamy wrote:since both array has an unique(means same Objects) object, I dont see any complex here. I didnt talk about changing keys

Then what's the business about "If you find the same element Hashtable already mark the element value/index of the element as positive from negative"?

I agree that if speed is an overriding concern and the lists are big, it might be worth loading one of them into a hashed collection (although I'd use a HashMap or HashSet myself), but the fact is that you don't need to do it.

 Another consideration: What if the Lists contain duplicate elements; how should they be matched? Sergio hasn't said, but a HashMap will not allow duplicates.

Winston

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Winston Gutkowski wrote:
Then what's the business about "If you find the same element Hashtable already mark the element value/index of the element as positive from negative"?

Might be, I didnt explain it well. what I was saying is that find the entry using key (which is element) and its value is -index. and make it possitive.

Winston Gutkowski wrote:
 Another consideration: What if the Lists contain duplicate elements; how should they be matched? Sergio hasn't said, but a HashMap will not allow duplicates.
Winston

<edit>
Yeah, this may be bit complex. when I go my home back . definitely post the solution
</edit>

Winston Gutkowski
Bartender
Posts: 10111
56
Seetharaman Venkatasamy wrote:Yeah, this may be bit complex. when I go my home back . definitely post the solution

Could I suggest that you do it in a different thread then? The idea here is to guide people to a solution, not hand it to them; and Sergio still hasn't come up with any ideas of his own yet.

Winston

Sergio Sa
Greenhorn
Posts: 2
I have resolved with this code:

Winston Gutkowski
Bartender
Posts: 10111
56
Sergio Sa wrote:I have resolved with this code:

Seems reasonable. It's worth noting that most "sublist" methods make the 'endIndex' value exclusive though.

Winston