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.

Never need to use a map to store identical Object as key and value, use a List — azro
– azro, Commented Mar 10, 2018 at 21:13

Eran · Accepted Answer · 2018-03-10 23:02:26Z

5

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

edited Mar 10, 2018 at 23:02

answered Mar 10, 2018 at 21:16

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

anna Over a year ago

Thank you so much, the program work faster, but i still get run time exceeded

Eran Over a year ago

@anna How many inputs are you supposed to process in less than 1 second?

anna Over a year ago

may be there is another an optimized algorithm to solve this task?

Eran Over a year ago

@anna there aren't any substantial optimizations to make (i.e. optimizations that would improve the asymptotic running time), but there are some minor improvements to make - for example, you can call remove without calling contains first.

Eran Over a year ago

@anna OK, here's another suggestion - instead of multiple println statements, you can append the outputs to a StringBuilder and have one System.out.println(sb.toString()); in the end to print the full output.

|

Collectives™ on Stack Overflow

How optimize code (java)

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related