How optimize code (java)

Question

I have a task. When a user registers on the site, his id can be his favorite number. But if there is already a user with such an id, then the id of this user becomes the smallest free number following his favorite number. But when the tourist leaves the site, his identifier ceases to be occupied, and the next user can occupy his id. For example:

Input:
first line value `n` is amount of users
the next `n` lines contain two values: first value can be 1  if user register on site or 2 if user leave site
 second value is favorite number (1<=x<=1000000000)
Input:
7
1 10
1 10
1 10
1 11
1 20
2 11
1 11

Output:
10
11
12
13
20
11

Here is my code:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
 public static final Scanner in= new Scanner(System.in);
 public static final int SIZE = 2;
 public static final int MAXNUMBER = 1000000000;
    public static void main(String[] args) {
        int t = Integer.parseInt(in.nextLine());
        Map<Integer, Integer> favoriteNumbers = new HashMap<>();
        int []a = new int[SIZE];
        while(t-- > 0) {
            for(int i=0; i<SIZE; i++) {
                a[i] = in.nextInt();
            }
            if(a[0] == 1 && !favoriteNumbers.containsValue(a[1])) {
                System.out.println(a[1]);
                favoriteNumbers.put(a[1], a[1]);
            }
            else if (a[0] == 1 && favoriteNumbers.containsValue(a[1])) {
                for(int i= (a[1] + 1); i<MAXNUMBER; ) {
                    if(!favoriteNumbers.containsValue(i)) {
                        System.out.println(i);
                        favoriteNumbers.put(i, i);
                        break;
                    }
                    i++;
                }
            } else if(a[0] == 2 && favoriteNumbers.containsValue(a[1])){
                favoriteNumbers.remove(a[1], a[1]);
            }
        }
    }
}

It's work correctly, but I get run time exceeded. The maximum execution time should be 1 second. Please help me how I can optimize code and speed up runtime.

Answer 1

favoriteNumbers.containsValue(a[1]) takes linear time (since finding a value in a HashMap requires iterating over all the values). favoriteNumbers.containsKey(a[1]) would take constant time.

Of course, since the key and value of your map are identical, you should use HashSet instead of HashMap, and once you change favoriteNumbers to a HashSet, favoriteNumbers.contains(a[1]) would take constant time.

Here's an optimized version using HashSet. Edit:

import java.util.*;

public class Main {
    public static final Scanner in= new Scanner(System.in);
    public static final int SIZE = 2;
    public static final int MAXNUMBER = 1000000000;

    public static void main(String[] args) {
        int t = Integer.parseInt(in.nextLine());
        StringBuilder sb = new StringBuilder("");
        Set<Integer> favoriteNumbers = new HashSet<>();
        int []a = new int[SIZE];
        while(t-- > 0) {
            for(int i=0; i<SIZE; i++) {
                a[i] = in.nextInt();
            }
            if(a[0] == 1) {
                for(int i = a[1]; i < MAXNUMBER; i++) {
                    if (favoriteNumbers.add(i)) {
                        sb.append(i + "\n");
                        break;
                    }
                }
            } else if(a[0] == 2) {
                favoriteNumbers.remove(a[1]);
            }
        }
        System.out.println(sb.toString());
    }
}