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

Slung

Using a binary tree structure may be your best bet depending on the values being input. That'll run in O(logn) on average – Gine

What not use a HashSet<Integer> if you only storing a number – Axolotl

@user2341963 duplicate entries are to be allowed – Slung

In the problem description you're saying check if it exists, if not then add. Doesn't that mean duplicate entries are not allowed? – Axolotl

if it exists then there is another condition , where it may or may not be added . – Slung

Use a boolean array with 1000000 elements, each element indicated whether the index value exist or not. – Stickle

Why do you search for containsValue(). Try to keep the Integer as a key in HashMap and use containsKey(). That will be much faster. – Deform

Sounds like you're using an inefficient method to construct your data structure and then probably search. Show your code. – Barreto

@CodeBender Why in the world reinvent HashSet? – Barreto

@chrylis, because he needs duplicate values... He can keep integer as key.. and no of times it occurred as value... Read the comments above... – Deform

ok i'll add the code , and explain the question in a little more detail – Slung

if(!(m.containsValue(PokeType))) ... else if(m.containsValue(PokeType)) ... Why bother search twice? – Stickle

okay consider it else -_- – Slung

And HashMap.containsValue performs linear search. You should reconsider what the key type should be. – Stickle

Map.containsValue() is very expensive -- it must traverse the entire map. Instead, invert the map so that you can use Map.containsKey(); maps are optimized for this type of operation, so this is very fast. – Schach

@Stickle tried TreeMap also , i guess it uses binary search right ? still same result – Slung

You're missing the point. Searching for values in a map is expensive. Searching for keys in a map is cheap. – Schach

so i'll try using containsKey() then , thanks @Schach – Slung

Don't forget to reverse the parameter order when calling m.put(). – Stickle

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

Slung

Answer 2

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

Shotwell

Answer 3

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

Facient