Search An ArrayList of ArrayLists

Question

What is the most efficient way to search for a single element in an ArrayList of ArrayLists? Given the following:

ArrayList<ArrayList<Integer>> intList = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a = new ArrayList<>();
a.add(1);
a.add(2);
ArrayList<Integer> b = new ArrayList<>();
b.add(3);
b.add(4);
intList.add(a);
intList.add(b);

How would I search to see if the ArrayList intList contains a specific Integer, like 3?

no efficient solution that i can think of. maybe if you described the bigger problem a more efficient data structure could be found? — radai, Dec 16 '13 at 17:57
[The ideas here](http://stackoverflow.com/questions/3477442/algorithm-efficient-way-to-search-an-integer-in-a-two-dimensional-integer-array) will probably help — Dan Temple, Dec 16 '13 at 17:59
You can try looping through main list and using `contains()` method in inner `ArrayList`. — PM 77-1, Dec 16 '13 at 18:02
That question is totally different from this one. It asks for a way to look into a matrix (not a list of lists) which respects certain criterias, like increasing monotonically. — Raffaele Rossi, Dec 16 '13 at 18:03
It will need `O(n ^ 2)` if there is no sequence hasn't already maintained. Now, defined what do you mean by efficient: time cost or shorter approach(<-- some people asks for this too)? — Sage, Dec 16 '13 at 18:04
Are the `List`s sorted? If so, then you can at least do a binary search on each one to improve performance. — rob, Dec 16 '13 at 18:17
@rob: nope, but you can use http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html — MemLeak, Dec 16 '13 at 18:19
@MemLeak how do you know they aren't sorted? Unless I missed something, there isn't anything in the question or comments to suggest that they are not sorted. — rob, Dec 16 '13 at 18:23
@rob: I think i missunderstoud your question, i though you mean a sorting like a Hash-Based Collection will do. Sorry about that — MemLeak, Dec 16 '13 at 21:35

score 4 · Accepted Answer · answered Dec 16 '13 at 18:01

4

Just iterates trough all the lists and ask if any of them contain your value.

public boolean contains(int x, ArrayList<ArrayList<Integer>> listOfLists) {
    for (ArrayList list: listOfLists) {
        if (list.contains(x)) return true;
    }
    return false;
}

However, I agree with radai. There is probably the need for a more efficient data structure rather than an efficient algorithm

answered Dec 16 '13 at 18:01

Raffaele Rossi

1,079
5
11

Thanks. I agree I can make a more efficient data structure, but in a pinch, this is fine. Wasn't sure if there was a function I wasn't aware of. – Adam_G Dec 16 '13 at 18:22
@Adam_G for the general case where the lists of integers are unsorted, this is the best you can do. However, if each `List` happens to be populated with a monotonically increasing sequence as shown in your example, you can improve performance from O(n^2) to O(n log n). And if no two `List`s have overlapping ranges (again, as in your example), you can improve your search performance to O(log n). – rob Dec 16 '13 at 22:14

Search An ArrayList of ArrayLists

1 Answers1