How can I optimize search on array of String array?

I have String arrays of arrays.

List<String[]> mainList = new ArrayList<String[]>();

String[] row1 = {"foo", "bar", "moo"}
String[] row2 = {"cocoa", "zoo", "milk", "coffee"}

mainList.add(row1);
mainList.add(row2);

Let's say I want to find an element "milk".

I could do with N^2.

for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        String item = mainList.get(i)[x];

        if(item.equals("milk")) {
            return true; //found milk
        }
    }
}

I tried to make it faster by putting all elements as Map key.

//put all elements to map key开发者_开发问答
Map m = new HashMap<String, String>();
for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        m.put(mainList.get(i)[x], "whatever");
    }
}

//now iterate and see if key "milk" is found
if(m.contains("milk")) { return true; }

But I figured this is still N^2 (i.e. for loop inside of for loop, as the number of rows added to mainList like row3['item1', 'item2', 'item3'], the iteration increments in N^2)

how can I optimize this without N^2 ?

Neither algorithm is N^2 since you visit the elements only once. However, the first algorithm, is O(N) for each lookup, but the second algorithm is O(N) to populate the map and O(1) for each subsequent lookup.

If you know the key you are looking for a get operation for a hashmap is actually O(1)

source: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Why can't be the code as below?

        String[] row1 = {"foo", "bar", "moo"};
        String[] row2 = {"cocoa", "zoo", "milk", "coffee"};

        HashMap<String, String> mainMap = new HashMap<String, String>();
        for(String s: row1) {
            mainMap.put(s, s);
        }

        for(String s: row2) {
            mainMap.put(s, s);
        }

        System.out.println(mainMap.get("milk") != null);

Bkail beat me to this answer, but mine might provide a little more insight (even though it is the same.)

I believe you might be a little unclear on your lookup time and your construction time.

For the first example you provided, I think you have a constant construction time (is allocating a static array constant in Java?). Then, your lookup time (for every lookup) is n (for n elements, not n*n). I can see how this could be a little bit confusing with your notation, as your n elements come in two rows.

However, for your second example, you are spending n on construction. Your actual lookup is O(1), like the other answers said.

So, the important thing to consider is what you are measuring. Asymptotic notation for the lookup is what you're interested in.

Good luck!