Data Structure for faster contains() operation?

Question

In the problem , I parse the input (integer) and simultaneously check if it exists in the data structure , if not then add it.

Input is - 2 integers separated by space of size >=1 and <= 1000000

I tried using HashMap , TreeMap (put() and containsValue() method)- but it seems they are taking too much time. (5 out of 10 test cases are exceeding time limit)

When using ArrayList(add() and contains() method) - (4 out of 10 test cases exceeded the time limit)

These operations are to be performed inside 2nd for loop , inside an if condition.

iterations may varies as follows : -

1st for loop - 1 to 10

2nd for loop - 1 to 100000

so i guess for higher order iteration in 2nd loop it exceeds time limit.

Is there any other way i could perform this task in lesser time .

Problem :

A Monk encounters N ponds and at each pond a fooditem(input 1) and a pokemon(input 2) is found .

The monk can feed the item at the i'th pond to the Pokemon at the pond if the type matches. Monk may have to carry some food items with him before leaving so as to feed all the Pokemons. Help him find the number of items he must carry, to be to able to pass through the land safely.

Explanation

At First Pond he gets item of type1 and feeds it to the Pokemon of type1.

At Second Pond he gets item of type 2 and feeds it to the Pokemon of type2.

At Third Pond he gets item of type 3 ,but the Pokemon is of type4 . Hence, he has to bring a food item of type 4 with him.

At Fourth Pond he gets item of type 4. He already has a item of type 3 and feeds it to the Pokemon.

At Fifth Pond he gets items of type 2. He already has a item of type 4 and feeds it to the Pokemon at this pond

class TestClass {
public static void main(String args[] ) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int T = Integer.parseInt(br.readLine());
    if(T<=10 && T>=1)   {
    for (int i = 0; i < T; i++) {
       int count=0;
       int numOfPonds = Integer.parseInt(br.readLine());
        if(numOfPonds<=100000 && numOfPonds>=1){  
       String[] str ;
       Map m = new HashMap();
        //List l = new ArrayList();

        for(int j=0 ; j< numOfPonds ;j++)
                {   
                    str = br.readLine().split(" ");
                    int foodType = Integer.parseInt(str[0]);
                    int PokeType = Integer.parseInt(str[1]);
                    if(foodType<=1000000 && PokeType<=1000000 && foodType>=1 && PokeType>=1 && foodType != PokeType){

                        m.put(j,foodType);

                    //l.add(foodType);

                        //if(!(l.contains(PokeType)))
                    if(!(m.containsValue(PokeType)))                        
                                    count++;

                    //else if(l.contains(PokeType))
                    else if(m.containsValue(PokeType))
                        {
                            m.values().remove(PokeType);
                            //  l.remove(Integer.valueOf(PokeType));
                            }

                    }
                }
        }
       System.out.println(count);
      }
    }
    }
}

Answer 1

Following is the code that passed all the test cases within the time limit.

As mentioned by Codebender and JimN , I implemented containsKey() method that proved to be faster than containsValue() .

Plus , for duplicates , incremented and changed the values in Map.

class TestClass {
public static void main(String args[] ) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int T = Integer.parseInt(br.readLine());
if(T<=10 && T>=1)   {
for (int i = 0; i < T; i++) {
   int count=0;
   int numOfPonds = Integer.parseInt(br.readLine());
    if(numOfPonds<=100000 && numOfPonds>=1){  
   String[] str ;

Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int j=0 ; j< numOfPonds ;j++)
            {   
                str = br.readLine().split(" ");
                int foodType = Integer.parseInt(str[0]);
                int PokeType = Integer.parseInt(str[1]);

                if(foodType<=1000000 && PokeType<=1000000 && foodType>=1 && PokeType>=1 && foodType != PokeType){

                if(map.containsKey(foodType))
                {
                    int x = map.get(Integer.valueOf(foodType));
                    x++;
                    map.put(foodType,x);
                }
                else
                {   map.put(foodType,1);
                }

                if(!(map.containsKey(PokeType)))                        
                                count++;

                else 
                    {   int x = map.get(Integer.valueOf(PokeType));
                        x--;

                        if(x==0)
                        map.remove(PokeType);

                        else
                        map.put(PokeType,x);

                        }

                }
            }
     }
   System.out.println(count);
  }
}
}
}