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

You can use a combination of a bloom filter and a Set<T>.

A Bloom filter is a space-efficient probabilistic data structure ... that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set".

The algorithm:

1. First query the bloom filter, if it return "definitely not in set" then the element is new.
2. If the bloom filter returns "possibly in set" then call Set<T>.contains() to be sure about containment.

Bloom filter Java implementation: https://guava.dev/releases/23.0/api/docs/com/google/common/hash/BloomFilter.html
Related article about usage: https://www.baeldung.com/guava-bloom-filter

Answer 2

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);
  }
}
}
}

Answer 3

Do not fully know what you are trying to do other than looking at your code. But this will give you quickest response . As far as finding the value in HashSet goes it will be O(1) .

Try this below

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class SalesTracking {
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();
       Set m = new HashSet();
        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.add(foodType);
                    if(!(m.contains(PokeType)))                        
                                    count++;
                    else if(m.contains(PokeType))
                        {   m.remove(PokeType);

                        }

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