compare two arraylists and get position of common elements

[Sergio Sa]

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?

import java.util.ArrayList;

public class ConfrontaArrayList {
	public static void main(String[] args)
	{
		ArrayList<String> arrayList = new ArrayList<String>();
		ArrayList<String> subSetArrayList = new ArrayList<String>();
		
		arrayList.add("inizio");
		arrayList.add("stringa");
		arrayList.add("uno");
		arrayList.add("due");
		arrayList.add("tre");
		arrayList.add("fine");
		arrayList.add("stringa");
		
		subSetArrayList.add("uno");
		subSetArrayList.add("due");
		subSetArrayList.add("tre");
		
		System.out.print("Elementi di arrayList: ");
		for (String stringa : arrayList) System.out.print(stringa + " ");
		System.out.print("\nElementi di subSetArrayList: ");
		for (String stringa : subSetArrayList) System.out.print(stringa + " ");
	
		for (int i=0; i<subSetArrayList.size(); i++)
		{
			for (int j=0; j<arrayList.size(); j++)
			{
				// ?????????????????
			}
		}
	}
}

[Winston Gutkowski]

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]

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]

Welcome to JavaRanch Sergio Sa

[Winston Gutkowski]

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

[Edit] Ooops. Thought you were OP. My comments still stand though.

[Seetharaman Venkatasamy]

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]

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.

[Edit] 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]

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:
[Edit] 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]

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]

I have resolved with this code:

int startIndex = Collections.indexOfSubList(arrayList, subSetArrayList); 
int endIndex = startIndex + subSetArrayList.size() - 1;

[Winston Gutkowski]

Sergio Sa wrote:I have resolved with this code:

int startIndex = Collections.indexOfSubList(arrayList, subSetArrayList); 
int endIndex = startIndex + subSetArrayList.size() - 1;

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

Winston