java - 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 want find element "milk".

i 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 make faster putting elements map key.

//put elements 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 , see if key "milk" found if(m.contains("milk")) { return true; } 

but figured still n^2 (i.e. loop inside of loop, number of rows added mainlist row3['item1', 'item2', 'item3'], iteration increments in n^2)

how can optimize without n^2 ?

neither algorithm n^2 since visit elements once. however, first algorithm, o(n) each lookup, second algorithm o(n) populate map , o(1) each subsequent lookup.